【王道数据结构】二叉树创建、遍历及线索化

【王道数据结构】二叉树创建、遍历及线索化

一、二叉树层次建树及遍历（先序中序后序及层序遍历）

• function.h文件

/
// Created by 斋心 on 2023/5/22.
//#ifndef TREE_FUNCTION_H
#define TREE_FUNCTION_H#include<stdio.h>
#include<stdlib.h>typedef char BiElemType;
//二叉树结构体类型申明
typedef struct BiTNode{BiElemType c;//结点数据struct BiTNode *lchild;//结点左孩子指针struct BiTNode *rchild;//结点右孩子指针
}BiTNode,*BiTree;//创建二叉树辅助队列结构体类型申明
typedef struct tag{BiTree p; //辅助队列的结点数据是二叉树结点地址（指针）struct tag *pnext;
}tag_t,*ptag_t;//队列（链式队列）结点的结构体类型申明
typedef BiTree ElemType; //存储树节点的指针
typedef struct LinkNode{ElemType data;struct LinkNode *next;
}LinkNode; //链表结点结构类型申明//层次遍历二叉树辅助队列结构体类型申明
typedef struct{LinkNode *front,*rear; //链表头，链表尾
}LinkQueue; //先进先出，从队尾入队，队头出队//申明要在main.cpp中使用的queue函数
void InitQueue(LinkQueue &Q);
void EnQueue(LinkQueue &Q,ElemType x);
bool DeQueue(LinkQueue &Q,ElemType &m);
bool IsEmpty(LinkQueue Q);#endif //TREE_FUNCTION_H

• queue.cpp文件

//
// Created by 斋心 on 2023/5/25.
//#include "function.h"//初始化队列,带头结点的链表
void InitQueue(LinkQueue &Q){Q.front&#ar=(LinkNode *)malloc(sizeof(LinkNode));Q.front->next=NULL;//初始为空
}//入队
void EnQueue(LinkQueue &Q,ElemType x){LinkNode *s=(LinkNode *)malloc(sizeof(LinkNode));s->data=x;s->next=NULL;//本句不可省略Q.rear->next=ar=s;
}//出队
bool DeQueue(LinkQueue &Q,ElemType &m){ //Q.rear可能发生改变ar==Q.front){ //判断队列是否为空 //因为是带头结点的单链表，所以判断是rear=frontreturn false;}LinkNode *q=Q.front->next;//待删除结点m=q->data;Q.front->next=q->next;ar==q){ //判断待删除结点是否为最后一个结点Q.rear=Q.front;}free(q);return true;
}//判断队列为空
bool IsEmpty(LinkQueue Q){ar==Q.front){return true;}return false;
}

• main.cpp文件

#include "function.h" //头文件的引用，注意引号//前序遍历，也叫先序遍历，也是深度优先遍历
void PreOrder(BiTree p){if(p!=NULL){printf("%c",p->c);//等同于课本中的visit函数PreOrder(p->lchild);PreOrder(p->rchild);}
}//中序遍历
void InOrder(BiTree p){if(p!=NULL){InOrder(p->lchild);printf("%c",p->c);InOrder(p->rchild);}
}//后序遍历
void PostOrder(BiTree p){if(p!=NULL){PostOrder(p->lchild);PostOrder(p->rchild);printf("%c",p->c);}
}//层序遍历
void LevelOrder(BiTree T){LinkQueue Q;//申请辅助队列InitQueue(Q);EnQueue(Q,T);//将树的根结点入队BiTree p;//存储出队的结点while(!IsEmpty(Q)){ //辅助队列非空，则将队头结点出队打印，并将其左孩子和右孩子依次入队DeQueue(Q,p);putchar(p->c);if(p->lchild){EnQueue(Q,p->lchild);}if(p->rchild){EnQueue(Q,p->rchild);}}
}int main() {//层次建树BiTree tree=NULL;//建立根结点并初始化BiTree pnew;//新的树结点BiElemType c;//用于赋值树结点数据的变量ptag_t phead=NULL,ptail=NULL,list_new=NULL,pcur;//phead和ptail是队头和队尾指针;list_new为队列结点指针；pcur指向待插入孩子的结点地址while(scanf("%c",&c)){if(c=='n'){break;//跳出while循环}//calloc申请的空间大小是1×sizeof()，并对申请变量进行初始化pnew=(BiTree)calloc(1,sizeof(BiTNode));//申请新的树结点pnew->c=c;list_new=(ptag_t)calloc(1,sizeof(tag_t));//申请新的辅助队列结点//等价于list_new=(ptag_t)malloc(sizeof(tag_t));list_new->p=NULL;list_new->pnext=NULL;list_new->p=pnew;if(NULL==tree){ //如是树的根结点，则将根结点加入树，队头和队尾结点指向第一个队列节点phead=ptail=list_new;pcur=list_new;tree=pnew;}else{ptail->pnext=list_new;ptail=list_new;if(NULL==pcur->p->lchild){pcur->p->lchild=pnew;}else if(NULL==pcur->p->rchild){pcur->p->rchild=pnew;pcur=pcur->pnext;//注意本句不要忘}}}//前序中序后序遍历printf("-----------PreOrder-----------n");PreOrder(tree);printf("n-----------InOrder------------n");InOrder(tree);printf("n-----------PostOrder----------n");PostOrder(tree);printf("n-----------LevelOrder----------n");LevelOrder(tree);return 0;
}输出结果：
abcdefg
-----------PreOrder-----------
abdecfg
-----------InOrder------------
dbeafcg
-----------PostOrder----------
debfgca
-----------LevelOrder----------
abcdefg
进程已结束，退出代码为 0

二、中序前序后序线索二叉树及其遍历

• function.h头文件

//
// Created by 斋心 on 2023/6/27.
//#ifndef INC_13_4_FUNCTION_H
#define INC_13_4_FUNCTION_H#include<stdio.h>
#include<stdlib.h>//线索二叉树结点结构体类型申明
typedef char BiElemType;
typedef struct ThreadNode{BiElemType c;//结点数据struct ThreadNode *lchild,*rchild; //左孩子，右孩子int ltag,rtag;//左前驱，右后继
}ThreadNode,*ThreadTree;//创建二叉树的辅助队列结构体类型申明
typedef struct tag{ThreadTree p;struct tag *pnext;
}tag_t,*ptag_t;#endif //INC_13_4_FUNCTION_H

• main.cpp文件

#include "function.h"//-----------------------------------------层次建树---------------------------------------------------------
//层次建树
//算法思想：设置链式辅助队列，用来存储树结点的地址，并用pcur记录当前待插入孩子结点的结点地址。
#include "function.h "BiTree CreateBiTree(BiTree &T){T=NULL;BiElemType c;BiTree pnew;ptag_t phead=NULL,ptail=NULL,listnew,pcur;int tag=0;//标志孩子结点是否已经插入，防止连续插入空结点的情形while(scanf("%c",&c)){if(c=='n'){break;}if(c=='0'){pnew=NULL;listnew=NULL;}else{pnew=(BiTree)calloc(1,sizeof(BiNode));pnew->c=c;listnew=(ptag_t)calloc(1,sizeof(tag_t));listnew->p=pnew;}if(NULL==T){phead=ptail=listnew;pcur=listnew;T=pnew;}else{if(listnew){ptail->pnext=listnew;ptail=listnew;}if(NULL==pcur->p->lchild&&tag!=1){pcur->p->lchild=pnew;tag=1;}else{pcur->p->rchild=pnew;pcur=pcur->pnext;tag=0;}}}return T;
}//-----------------------------------------前序中序后序遍历-----------------------------------------------------------//前序遍历
void PreOrder(ThreadTree T){if(T){printf("%c",T->c);PreOrder(T->lchild);PreOrder(T->rchild);}
}//中序遍历
void InOrder(ThreadTree T){if(T){InOrder(T->lchild);printf("%c",T->c);InOrder(T->rchild);}
}//后序遍历
void PostOrder(ThreadTree T){if(T){PostOrder(T->lchild);PostOrder(T->rchild);printf("%c",T->c);}
}//------------------------------------------二叉树线中序索化及其遍历------------------------------------------------------//中序线索化二叉树
//算法思想：设置遍历结点的前驱指针pre，中序遍历二叉树，遍历至待visit结点时，如该结点左孩子为空，则建立前驱线索，指向前驱结点；
//如该结点右孩子为空，则建立pre的后继线索，指向后继结点；建立线索后pre指针后移，继续中序遍历。//中序遍历二叉树并线索化，一边中序遍历一边线索化
void InThread(ThreadTree T,ThreadTree &pre){if(T){InThread(T->lchild,pre);if(T->lchild==NULL){T->lchild=pre;T->ltag=1;}if(pre!=NULL&&pre->rchild==NULL){pre->rchild=T;pre->rtag=1;}pre=T;InThread(T->rchild,pre);}
}//建立中序线索二叉树
void CreateInThread(ThreadTree T){ThreadTree pre=NULL; //前驱指针，初始化为NULLif(T){ //非空二叉树才能线索化InThread(T,pre);if(pre->rchild==NULL){ //处理最后一个结点pre->rtag=1;}}
}//遍历中序线索二叉树：找到二叉树树第一个被遍历的结点（最左下结点），然后依次遍历其后继结点//找到以T为根的子树中，第一个被中序遍历的结点，即该子树的最左下孩子结点
ThreadTree FirstInNode(ThreadTree T){while(T->ltag==0){T=T->lchild;}return T;
}//在中序线索二叉树中找到结点p的后继结点：如p->rtag=1,则p的后继结点即为其中序后继；如p->tag=0，则其后继结点为其右子树的最左下结点
ThreadTree NextInNode(ThreadTree p){if(p->rtag==0){return FirstInNode(p->rchild);//p结点的后继结点为其右子树的最左下结点}else{return p->rchild; //线索后继}
}//遍历中序线索二叉树
void InOrderThread(ThreadTree T){for(ThreadTree p=FirstInNode(T);p!=NULL;p=NextInNode(p)){printf("%c",p->c);}
}//逆向遍历中序线索二叉树:找到树最后一个被遍历的结点，然后依次遍历其前驱结点
//找到以T为根的子树中，最后一个被中序遍历的结点:子树最右下结点
ThreadTree LastInNode(ThreadTree T){while(T->rtag==0){T=T->rchild;}return T;
}//在中序线索二叉树中找到结点p的前驱结点：如p->ltag=1,则其前驱为p->lchild;如p->ltag=0，则其前驱结点为左子树最右下结点
ThreadTree PreInNode(ThreadTree p){if(p->ltag==0){ //如果结点p有左子树，则其前驱结点为左子树最右下结点return LastInNode(p->lchild);}else{return p->lchild;}
}//逆序遍历中序线索二叉树
void RevInOrder(ThreadTree T){for(ThreadTree p=LastInNode(T);p!=NULL;p= PreInNode(p)){printf("%c",p->c);}
}//----------------------------------二叉树先序线索化及其遍历-----------------------------------------------------//一边先序遍历一边线索化
void PreThread(ThreadTree T,ThreadTree &pre){if(T){if(T->lchild==NULL){T->lchild=pre;T->ltag=1;}if(pre!=NULL&&pre->rchild==NULL){pre->rchild=T;pre->rtag=1;}pre=T;if(T->ltag==0){ //先序线索化后会产生原地转圈问题，所以要有条件PreThread(T->lchild,pre);}if(T->rtag==0){ //先序线索化后会产生原地转圈问题，所以要有条件PreThread(T->rchild,pre);}}
}//建立先序线索二叉树
void CreatePreThread(ThreadTree T){ThreadTree pre=NULL;//前驱指针if(T){PreThread(T,pre);if(pre->rchild==NULL){ //处理最后一个结点pre->rtag=1;}}
}//遍历先序线索二叉树：从根结点开始，依次遍历其先序后继结点//在先序线索二叉树中找到p的后继结点：如p->rtag=1,则其后继结点为其先序后继；
// 如p->rtag=0，则分情况：如p有左子树，则其后继结点为其左孩子，如p无左子树，则其后继结点为其右孩子ThreadTree NextNode(ThreadTree p){if(p->rtag==0){if(p->ltag==0){return p->lchild;}else{return p->rchild;}}else{return p->rchild;//p结点的先序后继}
}//遍历先序线索二叉树
void PreOrderThread(ThreadTree T){for(ThreadTree p=T;p!=NULL;p= NextNode(p)){printf("%c",p->c);}
}//---------------------后序线索二叉树及其遍历--------------------------------------------------//建立后序线索二叉树
//一边遍历一边线索化
void PostThread(ThreadTree T,ThreadTree &pre){if(T){PostThread(T->lchild,pre);PostThread(T->rchild,pre);if(T->lchild==NULL){T->lchild=pre;T->ltag=1;}if(pre!=NULL&&pre->rchild==NULL){pre->rchild=T;pre->rtag=1;}pre=T;}
}//建立后序线索二叉树
void CreatePostThread(ThreadTree T){ThreadTree pre=NULL;if(T){PostThread(T,pre);if(pre->rchild==NULL){pre->rtag=1;}}
}//逆序遍历后序线索二叉树：从二叉树根结点开始，依次遍历其后序前驱结点
//在后序线索二叉树中找到p结点的前驱结点：如p->ltag=1,则前驱结点为p->lchild；
// 如p->ltag=0，则分情况：
//如p有右孩子，则p的前驱结点为其右孩子；如p无右孩子，则p的前驱结点为其左孩子ThreadTree PreNode(ThreadTree p){if(p->ltag==0){if(p->rtag==0){return p->rchild;}else{return p->lchild;}}else{return p->lchild;}
}//逆序遍历后序二叉树
void RevPostOrder(ThreadTree T){for(ThreadTree p=T;p!=NULL;p=PreNode(p)){printf("%c",p->c);}
}int main() {ThreadTree tree=NULL;//建立根结点CreateTree(tree);printf("------PreOrder--------n");PreOrder(tree);printf("n------InOrder--------n");InOrder(tree);printf("n------PostOrder-------n");PostOrder(tree);
//    CreateInThread(tree);
//    printf("n------InOrderThread------n");
//    InOrderThread(tree);
//    printf("n-------RevInOrder--------n");
//    RevInOrder(tree);
//    CreatePreThread(tree);
//    printf("n-------PreOrderThread----n");
//    PreOrderThread(tree);CreatePostThread(tree);printf("n-------RevPostOrder------n");RevPostOrder(tree);return 0;
}输出结果：
abcdef0g
------PreOrder--------
abdgecf
------InOrder--------
gdbeafc
------PostOrder-------
gdebfca
-------RevPostOrder------
acfbedg
进程已结束，退出代码为 0

三、二叉树前序中序后序非递归遍历

• function.h头文件

//
// Created by 斋心 on 2023/6/30.
//#ifndef INC_5_3_3_3_FUNCTION_H
#define INC_5_3_3_3_FUNCTION_H#include<stdio.h>
#include<stdlib.h>//二叉树结点结构体类型申明
typedef char BiElemType;
typedef struct BiNode{BiElemType c;struct BiNode *lchild,*rchild;
}BiNode,*BiTree;typedef BiTree ElemType;
//创建辅助队列结构体类型申明
typedef struct tag{ElemType p;struct tag *pnext;
}tag_t,*ptag_t;//辅助链栈的结构体结构体类型申明
typedef struct stack{ElemType data;struct stack *next;
} stack, *Lstack;//栈函数申明
void InitStack(Lstack &S);
void Push(Lstack &S,ElemType x);
void Pop(Lstack &S,ElemType &m);
void GetTop(Lstack S,ElemType &s);
bool IsEmpty(Lstack S);#endif //INC_5_3_3_3_FUNCTION_H

• stack.cpp文件

//
// Created by 斋心 on 2023/6/30.
//#include"function.h"
//带头结点的链栈初始化
void InitStack(Lstack &S){S=(Lstack)calloc(1,sizeof(stack));
}//进栈(头插法)
void Push(Lstack &S,ElemType x){Lstack snew=(Lstack)calloc(1,sizeof(stack));snew->data=x;snew->next=S->next;S->next=snew;
}//出栈(从头出栈)
void Pop(Lstack &S,ElemType &m){Lstack q=S->next;m=q->data;if(S->next!=NULL){   //栈不空，则出栈S->next=q->next;}free(q);
}//判断栈空
bool IsEmpty(Lstack S){if(S->next==NULL){return 1;}return 0;
}//读取栈顶元素
void GetTop(Lstack S,ElemType &s){if(S->next!=NULL){s=S->next->data;}
}

• main.cpp文件

#include "function.h"//层次建树
#include "function.h "BiTree CreateBiTree(BiTree &T){T=NULL;BiElemType c;BiTree pnew;ptag_t phead=NULL,ptail=NULL,listnew,pcur;int tag=0;//标志孩子结点是否已经插入，防止连续插入空结点的情形while(scanf("%c",&c)){if(c=='n'){break;}if(c=='0'){pnew=NULL;listnew=NULL;}else{pnew=(BiTree)calloc(1,sizeof(BiNode));pnew->c=c;listnew=(ptag_t)calloc(1,sizeof(tag_t));listnew->p=pnew;}if(NULL==T){phead=ptail=listnew;pcur=listnew;T=pnew;}else{if(listnew){ptail->pnext=listnew;ptail=listnew;}if(NULL==pcur->p->lchild&&tag!=1){pcur->p->lchild=pnew;tag=1;}else{pcur->p->rchild=pnew;pcur=pcur->pnext;tag=0;}}}return T;
}//前序遍历--递归算法
void PreOrder(BiTree T){if(T){printf("%c",T->c);PreOrder(T->lchild);PreOrder(T->rchild);}
}//前序遍历--非递归算法
//算法思想：借助辅助栈。① 沿着根的左孩子，依次打印结点并入栈，直到左孩子为空；
//②栈顶元素依次出栈，判断其是否有右孩子，如有，则转向右孩子，按①继续；如无，继续出栈。void PreOrderStack(BiTree T){Lstack S=NULL;InitStack(S);BiTree p=T;while(p||!IsEmpty(S)){if(p){   //如结点有左孩子，则将左孩子依次打印并入栈printf("%c",p->c);Push(S,p);p=p->lchild;}else{Pop(S,p);if(p->rchild){p=p->rchild;}else{p=NULL; //如无右孩子，则重置p指针，继续出栈}}}
}//中序遍历--递归算法
void InOrder(BiTree T){if(T){InOrder(T->lchild);printf("%c",T->c);InOrder(T->rchild);}
}//中序遍历--非递归算法
//算法思想：借助辅助栈。①沿着根的左孩子，依次入栈，直到左孩子为空；
// ②栈顶元素出栈并打印，判断其是否有右孩子：如有，则转向右孩子，继续①；如无，继续出栈。
void InOrderStack(BiTree T){Lstack S=NULL;InitStack(S);BiTree p=T;//遍历指针while(p||!IsEmpty(S)){if(p){Push(S,p);p=p->lchild;}else{Pop(S,p);printf("%c",p->c);if(p->rchild){p=p->rchild;}else{p=NULL;//如无右孩子，则重置p指针，继续出栈}}}
}//后序遍历--递归算法
void PostOrder(BiTree T){if(T){PostOrder(T->lchild);PostOrder(T->rchild);printf("%c",T->c);}
}//后序遍历--非递归算法
//算法思想：借助辅助栈。①沿着根的左孩子，依次入栈，直到左孩子为空； ②读取栈顶元素，如栈顶元素有右孩子且未被访问过，则转向右孩子，
// 按照①再将结点依次入栈；否则，将栈顶元素出栈，并访问。void PostOrderStack(BiTree T){Lstack S=NULL;InitStack(S);BiTree p=T,r=NULL;//p为遍历指针；r为临时指针，用于判断右孩子是否被访问过while(p||!IsEmpty(S)){if(p){   //如结点有左孩子，则将左孩子依次入栈Push(S,p);p=p->lchild;}else{GetTop(S,p); //读取栈顶元素if(p->rchild&&p->rchild!=r){  //如栈顶元素有右孩子且未访问过，则转向其右子树继续进行①p=p->rchild;}else{Pop(S,p);printf("%c",p->c);r=p; //标志访问过的结点p=NULL;//结点访问完后，重置p指针}}}
}int main() {BiTree tree=NULL;CreateBiTree(tree);printf("------PreOrder--------n");PreOrder(tree);printf("n------PreOrderStack----n");PreOrderStack(tree);printf("n------InOrder--------n");InOrder(tree);printf("n-------InOrderStack----n");InOrderStack(tree);printf("n------PostOrder-------n");PostOrder(tree);printf("n-----PostOrderStack-----n");PostOrderStack(tree);return 0;
}输出结果：
abcde000f00g
------PreOrder--------
abdgecf
------PreOrderStack----
abdgecf
------InOrder--------
gdbeafc
-------InOrderStack----
gdbeafc
------PostOrder-------
gdebfca
-----PostOrderStack-----
gdebfca
进程已结束，退出代码为 0