二叉树插入(按顺序排序) [英] Binary Tree insertion (in order sorted)

问题描述

我已经在互联网上搜寻有关此问题的帮助，但我需要帮助.对于二叉树来说，这并不是一个普通的插入问题，因为我们不能直接使用树结构本身.我的教授写道，他本人并给了我们一些函数，可以用来编写与二叉树有关的函数.因此，我不能使用节点，指针和事物.这也是在C ++中.

I've scoured the internet for help on this problem but I need help. This isn't exactly an ordinary insertion problem for a binary tree, since we don't get to work directly with the tree structure itself. My prof wrote that himself and has given us functions we can use to write functions pertaining to binary trees. As such, I can't use nodes and pointers and things. Also this is in C++.

无论如何，这是我必须编写的递归函数的描述(以及我开始尝试解决该问题的方法).请注意，它会完全返回一棵新树，实际上不会向现有树中添加任何内容.

Anyway, so here is the description of the recursive function I have to write ( along with my starting attempt at working with the problem). Notice it returns a new tree entirely, it does not actually add something to the existing tree.

tree_t insert_tree(int elt, tree_t tree)
{
    /* 
    // REQUIRES; tree is a sorted binary tree
    // EFFECTS: returns a new tree with elt inserted at a leaf such that 
    //          the resulting tree is also a sorted binary tree.
    //
    //          for example, inserting 1 into the tree:
    //
    //                           4
    //                         /   \
    //                        /      \
    //                       2        5
    //                      / \      / \
    //                         3 
    //                        / \
    //
    // would yield
    //                           4
    //                         /   \
    //                        /      \
    //                       2        5
    //                      / \      / \
    //                     1   3 
    //                    / \ / \
    // 
    // Hint: an in-order traversal of a sorted binary tree is always a
    //       sorted list, and there is only one unique location for
    //       any element to be inserted.
    */

if (elt < elt(tree_left(tree)){
    return insert_tree(tree_left(left));
} else {
    return insert_tree(tree_right(right));
}
}

这是我们可以使用的功能:

And here are the functions we can use:

extern bool tree_isEmpty(tree_t tree);
    // EFFECTS: returns true if tree is empty, false otherwise

extern tree_t tree_make();
    // EFFECTS: creates an empty tree.

extern tree_t tree_make(int elt, tree_t left, tree_t right);
    // EFFECTS: creates a new tree, with elt as it's element, left as
    //          its left subtree, and right as its right subtree

extern int tree_elt(tree_t tree);
    // REQUIRES: tree is not empty
    // EFFECTS: returns the element at the top of tree.

extern tree_t tree_left(tree_t tree);
    // REQUIRES: tree is not empty
    // EFFECTS: returns the left subtree of tree

extern tree_t tree_right(tree_t tree);
    // REQUIRES: tree is not empty
    // EFFECTS: returns the right subtree of tree

extern void tree_print(tree_t tree);
    // MODIFIES: cout
    // EFFECTS: prints tree to cout.

推荐答案

插入零元素树很容易:

return tree_make(elt, tree_make(), tree_make());

插入单元素树也很容易:

Inserting into a one-element tree is also easy:

tree_t new_node = tree_make(elt, tree_make(), tree_make());
if(elt < tree_elt(tree))
    return tree_make(tree_elt(tree), new_node, tree_right(tree));
else
    return tree_make(tree_elt(tree), tree_left(tree), new_node);

通常，要插入新元素，您需要以这种方式重新创建其所有父元素.

In general, to insert a new element, you'll need to recreate all of its parents in this manner.

第2部分:递归

我们有基本情况(零元素树).而且我们知道如何将新的子树附加到现有树的根上.

We have our base case (a zero-element tree). And we know how to attach a new subtree to the root of our existing tree.

那么如何获得新的子树?好吧，我们将元素插入当前子树怎么样?

So how to get the new subtree? Well, how about we just insert the element into the current subtree?

以下代码将始终在树的最左侧附加新元素，但是一旦您理解它，对它来说应该是微不足道的:

The following code will always attach the new element at the far left of the tree, but that should be trivial to correct once you understand it:

tree_t tree_insert(int elt, tree_t tree)
{
    if(tree_empty(tree)) //base case
        return tree_make(elt, tree_make(), tree_make());
    else
        return tree_make( // make a new node
            tree_elt(tree) // with the same value as the current one
            tree_insert(elt, tree_left(tree)) //insert into the left subtree
            tree_right(tree) // keep the right subtree the same
            );
}

这篇关于二叉树插入(按顺序排序)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！