问题:如下面一颗树形结构,如何删除节点C?

            T                             T
          /    \                         /   \
        A      E                     A     E
       /   \              ->       /   \     
     B     C                     B      D   
           /
         D

首先树节点的结构体:

typedef struct Node{
  int data;
  struct Node *lc,*rc;
} Node, *Tree;

 

初始化节点:

Tree createNode(int n){
  Tree T = malloc(sizeof(Node));
  T->data = n;
  T->lc = T->rc = NULL;
  return T;
}

 

创建一颗上图所示的树

  Tree T = createNode(70);
  Tree A = createNode(30);
  Tree B = createNode(10);
  Tree C = createNode(50);
  Tree D = createNode(40);
  Tree E = createNode(90);

  T->rc = E;
  T->lc = A;
  A->lc = B;
  A->rc = C;
  C->lc = D;

 

现在我想删除C节点

 

通过中序输出后的效果要达到如下:

删除前:  10 30 40 50 70 90

删除后:  10 30 40 70 90

 

该怎么做?

 

先从简单的开始,如果我要删除D,即删除没有左右孩子的节点。

能想到的就是直接把指针D 赋值为NULL。

D = NULL;

但是结果是错的,分析一下,指针D 原本指向值为40的结构体,赋值D 为NULL后只是

影响的是指针D,但是结构体还是依然存在在那里

 

 

所以说让指针D 为空是不会影响原来的树形结构体,那如何删除D节点呢? 很简答,看上图

让 值为 50 的那个节点的 lc 指针为空,就会影响整个树形结构了

C->lc = NULL;

成功了。

 

还没完。

 

现在通过函数来删除节点

void delete(Tree T){
  T = NULL;
}

然后将D节点的父亲的左孩子指针传进去来删除D

delete(C->lc);

结果是失败的,为什么?明明在没有函数时,这种方法是可以的呀

为什么左孩子指针当做参数传递进去就失效了呢?

这是因为形参中声明了一个 Tree T 的指针来保存结构体的地址

也就是说,形参的指针T 不再是父节点的那个左孩子指针了,

传进的是结构体的地址,并指针的地址。为了避免有新指针生成指向结构体

解决办法就是 把左孩子指针lc 的地址进去。

修改delete函数如下:

void delete(Tree *T){
  *T = NULL;
}

删除D节点:

  delete(&D);      //这种D指针是为空了,但是树形结构没有改变,前面探讨过

  delete(&(C->lc));    //这种可删除节点改变树形结构,但需要其父节点指针 来 定位到此左孩子的指针

 

 

回到最初的问题,如何删除节点C,其实我们现在知道如何改变树形结构,

那么这个问题就解决了,只需要把NULL换成其孩子的指针地址即可。

void delete(Tree *T){
  *T = (*T)->lc
}

然后传递 C节点的父节点 A 的右孩子指针进去(必须),就可以改变树形结构了 delete(&(A->rc))

如果只是传递C的地址进去 delete(&C),那么只改变的是指向C,不影响树的结构,大家可以试试

 

思考一下

有没有办法不依靠父节点,只需要传入节点,就对他删除,修改

且其他所有指向它的都会收到影响,而不是又生成一个新的副本

 

对于删除操作,干脆把结构体 free掉有没有用呢?

对于修改操作,既然不传递父节点指向自己的指针,我可否干脆直接修改结构体里面的data值来达到效果呢?

大家可以尝试一下

版权声明:本文为demonxian3原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://www.cnblogs.com/demonxian3/p/8377921.html