插入二叉树（不是 BST）不起作用

Question

在下面的代码中，我编写了一个二叉树的插入函数。但是在每次调用之后它不会向树中插入任何节点。我已经检查了插入二叉树的算法。我认为存在一些指针问题，但无法弄清楚为什么会这样。在 c++ 中，函数更改指针或将其分配给另一个指针是否有任何限制？

//binary tree implementation

#include<iostream>
#include<queue>

using namespace std;

//node class with a constructor 
struct NODE {
    int data;
    NODE *lc,*rc;

    NODE() {
        lc=rc=NULL;
    }
};

//tree class with a constructor
struct TREE {
    NODE *root;

    TREE() {
        root = NULL;
    } 
};

//insertion in a binary tree
//uses queue to keep track of nodes level wise   

void insertNode(NODE *r, int key) {
    NODE *newNode = new NODE;    //getting a new node
    newNode->data = key;         //setting the value of the node to key

    if(!r) {                     //if r is NULL
        //then this is where the new node to be inserted
        r = newNode;
        return;
    }

    queue<NODE*> q;              //Creating a queue of NODE* to store the
    q.push(r);                   //node at each level ,push r to the queue.
    while(!q.empty()) {          //Using a level order traversal
                                //to insert a node to the binary tree.  
        NODE *temp = q.front();  //And inserting the element wherever we
        q.pop();                 //found the node whose left or right child
        if(temp->lc)             //is NULL 
            q.push(temp->lc);    ///If temp has a left child then push it 
        else {                   ///into the queue
                                 ///else insert the node here
            temp->lc = newNode;
            return;
        }
        if(temp->rc)             ///If temp has a right child the push it
            q.push(temp->rc);    ///into the queue
        else {                   ///else insert the node here
             temp->rc = newNode;
             return;
        }
    }
}

//inorder traversal of the tree
void inorder(NODE *r) {
    if(r) {
        inorder(r->lc);
        cout<<r->data<<" ";
        inorder(r->rc);
    }
}

int main() {
    TREE t;
    insertNode(t.root,5);           //inserting 5 to the tree t
    insertNode(t.root,10);          //inserting 10 to the tree t
    insertNode(t.root,15);          //inserting 15 to the tree t

    inorder(t.root);     `          //Now traversing the tree.
                                    ///**But after each insertion root of 
                                    ///tree t is still empty.
                                    ///it means the pointer is not being 
                                    ///changed by the insertionNode fn 
                                    ///but cant figure this out

    return 0;
}

Answer 1

这是您代码的相关部分：

void insertNode(NODE *r, int key)
{
   r = newNode;             //inserted
   return;
}

您的参数是您传递的指针的副本。赋值会更改该副本，但不会更改函数的参数。然后副本立即被 return.

销毁

将参数更改为引用以解决此问题：

void insertNode(NODE *&r, int key)
{
   r = newNode;             //inserted
   return;
}

更好的是，由于您的函数仅在 TREE 的根节点指针上调用，因此通过引用传递 TREE。

更好的是，由于树插入属于树，所以使该函数成为TREE的成员函数。然后树将作为隐式 this 传递，您可以直接访问 root。你也会有一个更好的界面。

Answer 2

"Is there any restriction for a function on changing the pointer or assigning it with another pointer in c++? "

是的，函数参数的范围有限制（这也适用于 c 函数参数）。当您调用此代码时

insertNode(t.root,5);

t.root等于NULL，对新分配的NODE赋值正确。但是您正在更改调用 insertNode() 的指针的本地副本，因为指针参数 r 是通过值

传递的

void insertNode(NODE *r, int key) {
    NODE *newNode = new NODE;    //getting a new node
    newNode->data = key;         //setting the value of the node to key

    if(!r)  {  
        r = newNode;  // <<<<<<<
        return;
    }
    // ...

并且新创建的节点永远不会写回到 t.root。

更改您的函数签名以引用该指针

    void insertNode(NODE*& r, int key) {
                      // ^

因此它实际上会更改传递给该函数的变量。这将解决主要问题。

虽然我不得不同意，但 insertNode() 或 inorder() 的免费功能真的很奇怪。这些实际上应该是 TREE 的非静态 class 成员函数。

插入二叉树（不是 BST）不起作用

insertion in a binary tree ( not BST ) not working

c++

binary-tree

pointers