通过递归实现 C++ 对 BST 的插入

Question

我正在递归地在 BST 上插入一个节点，我在下面找到了一个实现（检查下面代码中的 rinsert() 函数）。递归函数return是新插入节点的指针。

如果插入节点假设为一棵树的高度为4的叶节点。从高度 3 到根的路径上的所有节点不应该引用一些垃圾指针吗？

您还可以找到一个 test() 函数，当该函数未运行进入显式 return 语句时，它实际上 return 是一个垃圾指针。

当我运行使用 rinsert() 进行中序遍历时，我得到的 BST 没有任何垃圾值。谁能帮我理解 rinsert() 函数中发生了什么？

struct Node  {
    Node* left;
    Node* right;
    int key;

    Node(int key) {
        this->key = key;
        left = NULL;
        right = NULL;
    }
};

class BST {

    Node* root;

    public:
        BST(int key) {
            root = new Node(key);
        }

        Node* rinsert(Node* cur, int key) {
            if (!cur) return new Node(key);

            if (key < cur->key)
                cur->left = rinsert(cur->left, key);
            else 
                cur->right = rinsert(cur->right, key);
        }

        void inorder(Node* node) {
            if (node == NULL) return;
            inorder(node->left);
            cout<<node->key<<" ";
            inorder(node->right);
        }

        Node* getRoot() {
            return root;
        }
};


// function to return garbage pointer
Node* test() {
    if (0) return new Node(2);
}

int main() {
    BST bst = BST(2);
    bst.rinsert(bst.getRoot(), 3);
    bst.rinsert(bst.getRoot(), 1);
    bst.rinsert(bst.getRoot(), 0);
    bst.rinsert(bst.getRoot(), 7);
    bst.rinsert(bst.getRoot(), 8);
    bst.rinsert(bst.getRoot(), 4);
    bst.rinsert(bst.getRoot(), 9);
    bst.inorder(bst.getRoot());

    // is it really a garbage pointer?
    Node* t = test();
    cout<<endl;
    cout<<t->key;
}

输出：

0 1 2 3 4 7 8 9
253425920

Answer 1

是的，该函数存在错误，因为尽管它承诺 return Node* 但并非在所有情况下都如此。

正确的代码（未经测试）是

    Node* rinsert(Node* cur, int key) {
        if (!cur) return new Node(key);

        if (key < cur->key)
            cur->left = rinsert(cur->left, key);
        else 
            cur->right = rinsert(cur->right, key);
        return cur;                                 // new code
    }

缺少 return 语句意味着发布的代码调用 undefined behaviour。不幸的是，未定义的行为并不意味着程序无法运行，也不意味着该函数将 return 一个垃圾指针。只是碰巧，在这种情况下，正确的指针恰好在正确的寄存器中，以使 return 值正确。所以代码'works'。在不同的编译器上（甚至不同的一天），你可能就没那么幸运了。

通过递归实现 C++ 对 BST 的插入

Implementing insert on BST by recursion for c++

c++

pointers

recursion

tree

binary-search-tree