主页 / 问题 / 672049
Accepted
TorSen
Asked:2020-05-29 02:39:40 +0000 UTC2020-05-29 02:39:40 +0000 UTC

递归地向树中添加/删除元素

  • 772
class BinarySearchTree {
private:
    class Node {
    public:
        Node *left;
        Node *right;
        int info;

        Node() {
            left = right = nullptr;
        }

        ~Node() {}
    };

    Node *root;

    BinarySearchTree() {
        root = nullptr;
    }

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

实际上，树本身更高。不能写递归插入和删除。做了一个迭代版本。这里有一个问题的递归。

void Insert(Node *node, int info) {
    if (node == nullptr) {
        node = new Node();
        node->info = info;
    } else {
        if (info > root->info) {
            Insert(root->right, info);
        } else if (info < root->info) {
            Insert(root->right, info);
        };
    }
}

树用法示例：

BinarySearchTree tree = new BinarySearchTree();
tree->Insert(tree->GetNode(), 10);

但是root总是指向NULL。

c++

1 个回答

  1. Best Answer

    问题可能是您从不更改root类变量BinarySearchTree。这可以通过例如传递给函数的insert不是指向树顶部的Node *node指针 ( ) 而是指针 ( ) 的引用来解决Node *&node。

    class BinarySearchTree {
private:
    struct Node {
        Node *left = nullptr;
        Node *right = nullptr;
        int key;

        Node(int key) : key(key) {}
    };

    static void insert(Node *&node, int key) {
        if (node == nullptr) {
            node = new Node(key);
        } else {
            if (key < node->key) {
                insert(node->left, key);
            } else if (key > node->key) {
                insert(node->right, key);
            }
//          если key == node->key, то такой ключ уже есть в дереве, поэтому мы ничего не делаем
        }
    }

    Node *root = nullptr;
public:
    void insert(int key) {
        insert(root, key);
    }
};

int main() {
    BinarySearchTree tree;
    tree.insert(10);
    return 0;
}
    • 2

相关问题