c++ - 为什么 parent->left 不持久

Question

Bellow 是在二叉树中插入的代码。问题是在插入 head 之后，对于第二个输入，函数 insert 被递归调用，输入为 parent->left 或 parent->right ，然后它是设置为 item 。从插入函数返回后，parent->left 或 parent->right 的值(无论哪种情况)保持为 NULL，并且没有节点分配给 head 的左侧或右侧。

#include<iostream>
#include<string>

using namespace std;

typedef struct Tnode{
    string word;
    int count;
    Tnode* left;
    Tnode* right;
}; 

static  Tnode *head=NULL ;

Tnode* getNode(string const& iData)
{
    Tnode* pNewNode = new Tnode();
    pNewNode->word = iData;
    pNewNode->count = 0;
    pNewNode->left = NULL;
    pNewNode->right = NULL;
    return pNewNode;
}

void insert_in_tree(Tnode* parent,Tnode *item)
{
    item->count++;
    if ( head== NULL )
    {
        head=item;
        cout<<"Inserting head "<<head->word<<endl;
        return;
    }
    else
    {
        if (item->count==1) parent=head;
        if( parent == NULL )
        { 
            parent=item;
            cout<<"Inserting "<<parent->word<<"count is "<<parent->count<<endl; 
            return;
        }
        else
        {
            if(item->word < parent->word ) 
            {
                insert_in_tree(parent->left,item);
                cout<<"inserted in left of "<<parent->word<<endl;
            }
            else 
            {
                insert_in_tree(parent->right,item);
                cout<<"inserted in right of "<<parent->word<<endl;
            }
        }
   }
}

void print_elements(Tnode *tree)
{
    if(tree!=NULL)
    {
        print_elements(tree->left);
        cout<<tree->word<<endl;
        print_elements(tree->right);
    }
}

int main()
{
    string x;

    while(cin>>x) 
    {
        Tnode * node=getNode(x);
        insert_in_tree(NULL,node);
    }
    if(!cin.eof()) cout<<"Error"<<endl;
    else print_elements(head);

    return 0;
}

Answer 1

当你进行递归调用时，你只是将 parent->left/parent->right 的指针值传递给被调用的方法，而不是 where this值被存储。因此，当该方法执行 parent = item 时，它只修改其本地 parent 参数变量，而不修改父节点中的原始成员。

要实现您所追求的行为，您必须将parent 声明为指向Tnode* 的指针或引用。这也会给您带来好处，即处理 head 不再需要单独检查。

编辑:顺便说一下，parent 不是一个好的参数名称，因为它实际上不包含对父节点的引用。