二叉树插入（按顺序排序）

Question

二叉树插入（按顺序排序）

3

我已经在互联网上搜寻了关于这个问题的帮助，但我需要帮助。这不是一个普通的二叉树插入问题，因为我们不能直接使用树结构本身来工作。我的教授自己写了这个，并给了我们可以用来编写与二叉树相关的函数的函数。因此，我不能使用节点和指针等。此外，这是使用C++编写的。

无论如何，这里是我必须编写的递归函数的描述（以及我开始尝试解决该问题的方式）。请注意，它返回一个全新的树，而不是实际向现有树添加内容。

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));
}
}

以下是我们可以使用的函数：

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.

- Slims

我希望我在大学的第一年就知道StackOverflow。我实际上不得不自己弄清楚这个问题。你有具体的问题吗？你的开头看起来可能无法编译，因为你没有尝试传递到tree_left和tree_right的左侧或右侧变量。 - Joe

这并不是要编译。那只是我的思路。但我完全被难住了。我已经在这个项目上工作了好几天，这是我需要编写的最后两个函数之一，所以我的大脑已经崩溃了。我需要一个正确方向的推动。 - Slims

这是我见过的最恶心的API之一。你的教授声称那是C++？ - Puppy

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Anon. · Accepted Answer

在零元素树中插入元素很容易：

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

插入到一个元素树中也很容易：

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);

一般来说，要插入一个新元素，你需要以这种方式重新创建所有的父元素。

第二部分：递归

我们有了基础情况（零元素树）。我们也知道如何将一个新子树附加到现有树的根上。

那么如何得到新的子树呢？我们只需将元素插入当前子树即可。

以下代码总是将新元素附加到树的最左侧，但一旦你理解了它，这应该很容易纠正：

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
            );
}