时间戳

首页 > 解决方案 > 在 BST 中插入一个具有全局根的节点

c++ - 在 BST 中插入一个具有全局根的节点

问题描述

struct node{
    int data;
    struct node*left,*right;
};

node* root;   //global root

node* getNode(int item)
{
    node* new_node = new node;
    new_node->data = item;
    new_node->left=new_node->right=NULL;
    return new_node;
}

node* insert(node* localroot, int item)
{

    if(localroot == NULL){
        localroot = getNode(item);
    }
    else if(item < localroot->data)
        localroot->left = insert(localroot->left, item);
    else if(item > localroot->data)
        localroot->right = insert(localroot->right, item);
    root = localroot;
    return root;   //Why do I have to return root if it is global? 
                   //without this output is wrong
}

void inorder(node* root)
{
    if(root != NULL){
        inorder(root->left);
        std::cout << root->data << ' ';
        inorder(root->right);
    }
}

void postorder(node* root)
{
    if(root != NULL){
        postorder(root->left);
        postorder(root->right);
        std::cout << root->data << ' ';
    }
}

int main()
{
    insert(root, 15);
    insert(root, 9);
    insert(root, 2);
    insert(root, 1);
    insert(root, 4);
    insert(root, 18);

    std::cout<<"inorder traversal of tree is: ";
    inorder(root);
    std::cout << "\nPostOrder: ";
    postorder(root);

    return 0;
}

通常在 main 我们调用 insert like root = insert(root, 10);（其中 root 在 main() 中声明）。
我想声明 root 全局，但插入函数不能为 void 它必须返回 node* 值我可以得到解释。
如果有更好的方法请分享（实际上我想让 insert 成为 void 类型）。
问候，

标签： c++recursioninsertbinary-search-treefunction-definition

解决方案

您编写的方式insert要求它始终返回它修改或创建的节点。这确保insert在没有子节点的节点上设置正确的成员（左或右）。

您可以通过传入对要设置的指针的引用来重写root为纯粹的命令：

void insert(int item, node*& localroot = root) {
    if (localroot == nullptr) {
        localroot = getNode(item);
        return;
    }

    if (item == localroot->data) {
        return;
    } else if(item < localroot->data) {
        insert(item, localroot->left);
    } else if(item > localroot->data) {
        insert(item, localroot->right);
    }
}

要实现的关键点是赋值localroot将反映在数据结构中，所以：

  • 当您第一次调用insert(item)时，是一个空指针localroot的引用。root因此，第一个子句适用并且您localRoot用新节点覆盖。因为localRoot是对 的引用root，所以也会更新。
  • 在随后的插入调用中，您将沿着树向下直到您最终到达节点 N，您必须进一步向下，但子节点是 nullptr。当您现在下降时，localRoot绑定到N->leftor N->right，并且第一个子句将再次使用指向新创建节点的指针覆盖该值。

如果默认参数对你来说太神奇了，拆分成两个函数：

void insert_helper(int item, node*& localroot) {
    // as above
}

void insert(int item) {
    insert_helper(item, root);
}

推荐阅读