引入

上一节，我们试着解决了树在存储时空间浪费和没法找到双亲结点的问题，这一节，我们着重看一下如何用代码实现。这篇难度有一点大，请务必沉住气，认真仔细。

思路拆解

我们一步一步的拆解代码来看看。

创建树结构体

我们首先声明我们重新设计的线索二叉树结点

  • char data 存放结点数据
  • 左孩子、右孩子这个不用细说了吧，
  • Ltag 和 Rtag 主要是判断左孩子和右孩子究竟是指向左右孩子还是前驱后继
  • 我们定义结构体的时候，使用了 typedef
  • 后面所有的 BiTNode 你可以理解为 struct BiTNode，代表该结构体
  • 后面所有的 BiTree 你可以理解为 struct BiTNode *，代表结构体指针
  • 注意上面有个星号哈！
#include <stdio.h>
#include <stdlib.h>
#define LEN sizeof(struct BiTNode)

typedef enum{link,thread} NodeState;
typedef struct BiTNode{
    char data;
    struct BiTNode *Lchild;
    struct BiTNode *Rchild;
    NodeState Ltag;
    NodeState Rtag;
}BiTNode,*BiTree;

创建二叉树

我们刚才重新设计了结点，现在开始生成树，首先接收数据

  • **重点：**我们这里的形参，是 BiTree *tempTree
  • BiTree *tempTree 你可以理解为 struct BiTNode **tempTree
  • 就是一个指向二叉树结点的结构体的指针的指针。
  • 然后 tempC 是用来存放输入的结点 data 的
  • 我们使用 scanf 来接收数据

然后我们判断 scanf 中的数据

  • 如果输入的是 # 号，表示结点为空，我们就把结点设置为 NULL
  • 这里注意，我们是将*tempTree设置为 NULL，不是** tempTree
  • 是1个星号的，1个星号表示的是结点结构体的指针

如果scanf 中接受的不是#号

  • 先创建动态存储空间，1个星号表示的是结点结构体的指针
  • 所以给1个星号表示的是结点结构体的指针创建动态存储空间
  • (*tempTree)这里为什么加括号呢？学过指针都知道！
  • *tempTree 表示的是 tempTree 中地址指向的数据
  • 既然 tempTree 存储的是指针的指针，所以把 tempTree 加一个星号
  • 表示 tempTree 中结点的地址，也就是结点结构体的开始地址
  • 我们先给 data 赋值为 tempC
  • 然后默认左右 tag 是 Link，也就是链接状态
  • 后面如果遇到子树为空，我们会修正 tag 的内容
  • 然后利用递归，创建左子树和右子树
void Create(BiTree *tempTree){
    char tempC;
    scanf("%c",&tempC);
    if(tempC=='#'){
        *tempTree=NULL;
    }else{
        *tempTree=(BiTree)malloc(LEN);
        (*tempTree)->data=tempC;
        (*tempTree)->Ltag=link;
        (*tempTree)->Rtag=link;
        Create(&(*tempTree)->Lchild);
        Create(&(*tempTree)->Rchild);
    }
}

给二叉树添加线索

我们生成了一个二叉树，这棵二叉树的每个结点都有 Ltag 和 Rtag，该如何利用呢

  • 我们这一步就是给哪些没有前驱、后继的结点，修改 Ltag 和 Rtag 状态。
  • pre 是一个结点结构体指针的全局变量，保存根的前驱
  • 然后我们传入二叉树，给二叉树添加线索
  • 利用中序遍历，左中右的方式，递归遍历这棵树。

判断根节点左子树的情况

  • 在根节点时，判断根节点左右子树的状态，记住有右必有左
  • 先判断左子树，如果为空，那么这个结点的 Lchild 改为前序的地址
  • Ltag 改为 thread，表示这个 Lchild 是线索
  • 这里的 Lchild 是 pre，pre 等下会存储每个结点的前驱。

判断根节点右子树的情况

  • 怎么判断右子树呢？如果只有左没有右呢？
  • 所以判断 pre 的右子树，只要当前结点的前一结点的右子树为空
  • 那么就改变 Rtag 状态为线索
  • Rchild 右孩子为当前结点
  • 也就是当前结点前驱没有右子树，那么前驱的右孩子指向当前结点。
  • 记得最后把当前的地址个 pre，这样指针才能向后走，pre 才能保存前驱结点
BiTree pre;

void Inthread(BiTree t){
    if(t){
        Inthread(t->Lchild);
        
        if(!t->Lchild){
            t->Ltag=thread;
            t->Lchild=pre;
        }
        
        if(!pre->Rchild){
            pre->Rtag=thread;
            pre->Rchild=t;
        }
        
        pre=t;
        
        Inthread(t->Rchild);
    }
}

根结点的前驱

我们知道，根结点是没有双亲的，那么怎么获得根结点的前驱呢？

  • 创建一个 p ，模拟根的前驱，让根的前驱指向这个 p
  • 先创建一个 p，星号的道理和创建树的时候相同，就不解释了。
  • Rtag 因为指向自己，所以为 thread 线索
  • Ltag 因为等下要指向树本身，所以为 link
  • 然后让 Rchild 指向子集
  • 判断树是不是空的，如果是空的，那没得玩，左右子树都指向 p 自己
  • 如果不是空的，那就让左子树指向树根
  • pre 就能获取根的前驱了，就是 p
  • 然后从这里调用给二叉树加线索的函数
  • 因为给二叉树加线索，需要用到根的前驱。

记得收尾

  • 最后，我们让这棵树连成圈
  • 让 pre，也就是最后一个结点的前驱的右孩子指向 P，也就是根的前驱
  • 让后 p 的右孩子指向 pre
  • 这样，就连起来了
void Inorderthread(BiTree t , BiTree *p){
    *p=(BiTree)malloc(LEN);
    (*p)->Rtag=thread;
    (*p)->Ltag=link;
    (*p)->Rchild=*p;
    if(!t){
        (*p)->Lchild=*p;
    }else{
        (*p)->Lchild=t;
        pre=*p;
        Inthread(t);

        pre->Rtag=thread;
        pre->Rchild=*p;
        (*p)->Rchild=pre;
    }
}

两种遍历方式

用递归的时候注意，要在加线索之前使用，否则树都连起来就会出错。

###递归中序遍历，不多说了，需要的话看前面


void Inthreading(BiTree t){
    if(t){
        Inthreading(t->Lchild);
        printf("%c",t->data);
        Inthreading(t->Rchild);
    }
}

迭代中序遍历，就是利用 while 循环遍历

同样是左中右

  • 如果 p=t->Lchild,那就证明转了一圈了。
  • 然后判断最左边的结点，输出
  • 判断右边结点是否是叶子，也输出
  • p 向右孩子移动一位
  • 直到转完所有的结点
void Inorderthreading(BiTree t){
    BiTree p;
    p=t->Lchild;
    while(p!=t){
        while(p->Ltag==link){
            p=p->Lchild;
        }
        printf("%c",p->data);
        while(p->Rtag==thread && p->Rchild!=t){
            p=p->Rchild;
            printf("%c",p->data);
        }
        p=p->Rchild;
    }
}

主调函数

这个其实没什么好讲的，就是星号和顺序的问题

  • 星号请注意，因为传过去的是指针的地址，所以要加&符号
  • 顺序请注意，先使用递归输出，再增加线索，最后用迭代循环输出
  • 原因是增加线索后，树连起来了，递归没法结束。
int main(){
    BiTree t,p;
    printf("请输入结点：\n");
    Create(&t);
    printf("递归-中序遍历是：");
    Inthreading(t);
    printf("\n");
    printf("迭代-中序遍历是：");
    Inorderthread(t,&p);
    Inorderthreading(p);
    printf("\n");
    return 0;
}

主要问题

这个也绕了我好久，主要问题是

  • 指向指针的指针，出了问题！
  • 递归增加线索，出了问题！

总代码


#include <stdio.h>
#include <stdlib.h>
#define LEN sizeof(struct BiTNode)

typedef enum{link,thread} NodeState;
typedef struct BiTNode{
    char data;
    struct BiTNode *Lchild;
    struct BiTNode *Rchild;
    NodeState Ltag;
    NodeState Rtag;
}BiTNode,*BiTree;

BiTree pre;

void Create(BiTree *tempTree){
    char tempC;
    scanf("%c",&tempC);
    if(tempC=='#'){
        *tempTree=NULL;
    }else{
        *tempTree=(BiTree)malloc(LEN);
        (*tempTree)->data=tempC;
        (*tempTree)->Ltag=link;
        (*tempTree)->Rtag=link;
        Create(&(*tempTree)->Lchild);
        Create(&(*tempTree)->Rchild);
    }
}

void Inthread(BiTree t){
    if(t){
        Inthread(t->Lchild);
        
        if(!t->Lchild){
            t->Ltag=thread;
            t->Lchild=pre;
        }
        
        if(!pre->Rchild){
            pre->Rtag=thread;
            pre->Rchild=t;
        }
        
        pre=t;
        
        Inthread(t->Rchild);
    }
}

void Inorderthread(BiTree t , BiTree *p){
    *p=(BiTree)malloc(LEN);
    (*p)->Rtag=thread;
    (*p)->Ltag=link;
    (*p)->Rchild=*p;
    if(!t){
        (*p)->Lchild=*p;
    }else{
        (*p)->Lchild=t;
        pre=*p;
        Inthread(t);

        pre->Rtag=thread;
        pre->Rchild=*p;
        (*p)->Rchild=pre;
    }
}

void Inthreading(BiTree t){
    if(t){
        Inthreading(t->Lchild);
        printf("%c",t->data);
        Inthreading(t->Rchild);
    }
}

void Inorderthreading(BiTree t){
    BiTree p;
    p=t->Lchild;
    while(p!=t){
        while(p->Ltag==link){
            p=p->Lchild;
        }
        printf("%c",p->data);
        while(p->Rtag==thread && p->Rchild!=t){
            p=p->Rchild;
            printf("%c",p->data);
        }
        p=p->Rchild;
    }
}

int main(){
    BiTree t,p;
    printf("请输入结点：\n");
    Create(&t);
    printf("递归-中序遍历是：");
    Inthreading(t);
    printf("\n");
    printf("迭代-中序遍历是：");
    Inorderthread(t,&p);
    Inorderthreading(p);
    printf("\n");
    return 0;
}

输出结果：
请输入结点：
ABDH##I##E#J##CF#K##G##
递归-中序遍历是：HDIBEJAFKCG
迭代-中序遍历是：HDIBEJAFKCG

遍历的是上面这棵树。

带注释的总代码

我第二天一早又写了一遍，加了一些注释

#include <stdio.h>
#include <stdlib.h>
#define LEN  sizeof(struct BiTNode)

typedef enum{link,thread} Nodestate;  //着重看一下
typedef struct BiTNode{
    char data;
    struct BiTNode *Lchild;
    struct BiTNode *Rchild;
    Nodestate Ltag;
    Nodestate Rtag;
}BiTNode,*BiTree;

BiTree pre;

void Create(BiTree *tempt){
    char tempc;
    scanf("%c",&tempc);
    
    if(tempc=='#'){
        *tempt=NULL;  //因为 *temp 才是结点
    }else{
        *tempt=(BiTree)malloc(LEN);
        //先赋值
        (*tempt)->data=tempc;
        //左右孩子的默认状态是链接的
        (*tempt)->Ltag=link;
        (*tempt)->Rtag=link;
        //接着用递归的方式先输入左子树再输入右子树，这种前序遍历
        Create(&(*tempt)->Lchild);
        Create(&(*tempt)->Rchild);
    }
}

//给上面的二叉树创建线索
void Inthread(BiTree t){
    if(t){
        //因为是用中序给树增加线索，所以先递归左孩子
        Inthread(t->Lchild);
        
        if(!t->Lchild){
            //如果中间根结点左孩子为空，状态改变
            t->Ltag=thread;
            t->Lchild=pre;  //这里的 pre 记录的是 t 的前驱结点
        }
        
        if(!pre->Rchild){
            //因为没法用该结点判断右孩子，所以用前驱判断，如果右孩子为空
            pre->Rtag=thread;
            pre->Rchild=t;  //如果前驱的右孩子为空，那么前驱的左右都指向当前结点
        }
        
        pre=t;  //让前驱向后移动一位
        
        Inthread(t->Rchild);  //完成左中右的遍历过程
    }
}

//创建根的 pre

void  Inorderthread(BiTree t , BiTree *p){
    *p=(BiTree)malloc(LEN);
    //右孩子等于 thread，并且指向自己
    (*p)->Rchild=*p;
    (*p)->Rtag=thread;
    //左孩子为连通，等下指向树的根
    (*p)->Ltag=link;
    
    if(!t){
        (*p)->Lchild=*p;
    }else{
        //把 p 的左子树指向 t 树的根
        (*p)->Lchild=t;
        pre=*p;  //pre 就是这个指向根的结点
        Inthread(t);  //有了 pre，开始给树增加线索
        
        //收尾，此时 pre 是最后一个结点
        pre->Rtag=thread;
        pre->Rchild=*p;
        (*p)->Rchild=pre;
    }
}

//开始递归中序遍历
void Invisit(BiTree t){
    if(t){
        Invisit(t->Lchild);
        printf("%c",t->data);
        Invisit(t->Rchild);
    }
}

//开始迭代中序遍历
void Inthreading(BiTree t){
    BiTree p;
    p=t->Lchild;
    //如果转到 t，那么证明指回根节点了，转了一圈了
    while(p!=t){
        //如果左边是连通的，那么向下
        while(p->Ltag==link){
            p=p->Lchild;
        }
        
        printf("%c",p->data);
        
        while(p->Rtag==thread && p->Rchild!=t){
            p=p->Rchild;
            printf("%c",p->data);
        }
        
        p=p->Rchild;
    }
}

int main(){
    BiTree t,p;
    printf("请输入结点：\n");
    Create(&t);
    printf("递归-中序遍历：");
    Invisit(t);
    printf("\n");
    printf("迭代-中序遍历：");
    Inorderthread(t,&p);
    Inthreading(p);
    printf("\n");
}

尾巴

这是我的个人学习笔记，主要是应付考研复习使用，充斥着一些吐槽和个人观点，并不严谨，欢迎大家参考、指正。