c++ - C++中使用全局指针实现红黑树

Question

我在以下代码中更新我的全局指针时遇到问题，

#include <iostream>

using namespace std;

struct RB{
    RB()=default;
    RB(int clr):color(clr) { }
    int color;
    RB *p,*left,*right;
    int key;
};

RB *Tnil=new RB(0);
RB *T=Tnil;
void insert(RB *T,RB *z)
{
    RB *y=Tnil;
    RB *x=T;
    while(x!=Tnil)
    {
        y=x;
        if(z->key<y->key)
          x=x->left;
        else
         x=x->right;
    }
    z->p=y;
    if(y==Tnil)
      T=z;
    else if(z->key<y->key)
      y->left==z;
    else
      y->right=z;
    z->right=Tnil;
    z->left=Tnil;
    z->color=1;
}

void print(RB *T)
{
    if(T==Tnil)
      return;
    print(T->left);
    cout<<T->key;
    print(T->right);
}

int main()
{
  for(int i=1;i<10;++i)
  {
    RB *x=new RB;
    x->key=i;
    insert(T,x);

  }
   print(T);
}

问题是，我的 insert 函数中的比较 y==Tnil 计算结果为 false，而我预期它为 true。结束该函数后，T 再次变为等于 Tnil，因此不会插入任何内容。有帮助吗？

Answer 1

你想更新全局T。
因此，您应该传递全局 T 的引用以插入:

替换

void insert(RB *T,RB *z)

与

void insert(RB * & T,RB *z)

(否则只会更新全局指针 T 的拷贝)

也如 ComicSansMS 所述在你的例子中

y->left==z 

应该替换为

y->left=z

最好的，

jack