【数据结构与算法】二叉树的遍历和线索二叉树

深藏阁楼爱情的钟 2024-04-26 02:24 240阅读 0赞

> ? 本文由 [程序喵正在路上][Link 1] 原创，CSDN首发！  
> ? 系列专栏：[数据结构与算法][Link 2]  
> ? 首发时间：2022年10月30日  
> ? 欢迎关注?点赞?收藏?留言?  
> ? 一以贯之的努力 不得懈怠的人生

#### 阅读指南 ####

*  二叉树的先 / 中 / 后序遍历
 *   *  先序遍历
     *  中序遍历
     *  后序遍历
     *  快速求遍历序列
     *  求树的深度
 *  二叉树的层序遍历
 *   *  算法思想
     *  代码实现
 *  由遍历序列构造二叉树
 *  线索二叉树
 *   *  线索二叉树的存储结构
 *  二叉树的线索化
 *   *  中序线索化
     *  先序线索化
     *  后序线索化
 *  线索二叉树找前驱后继
 *   *  中序线索二叉树找中序后继
     *  中序线索二叉树找中序前驱
     *  先序线索二叉树找先序后继
     *  先序线索二叉树找先序前驱
     *  后序线索二叉树找后序前驱
     *  后序线索二叉树找后序后继

## 二叉树的先 / 中 / 后序遍历 ##

二叉树的递归特性：

*  要么是个空二叉树
 *  要么就是由 “根节点 + 左子树 + 右子树” 组成的二叉树

先序遍历：根左右（NLR）  
中序遍历：左根右（LNR）  
后序遍历：左右根（LRN）

我们来看一个简单的例子：  
![在这里插入图片描述][f76e6c96c9cf4e2aa7611cd3d0fcf731.png]

对上面这棵树进行前面说到的三种遍历：

*  先序遍历： A B D E C F G A B D E C F G ABDECFG
 *  中序遍历： D B E A F C G DBEAFCG DBEAFCG
 *  后序遍历： D E B F G C A DEBFGCA DEBFGCA

### 先序遍历 ###

先序遍历的操作过程如下：

1.  若二叉树为空，则什么也不做
2.  若二叉树非空：  
    ① 访问根结点  
    ② 先序遍历左子树  
    ③ 先序遍历右子树

//先序遍历
    void PreOrder(BiTree T) {
        
    	if (T) {
        
    		visit(T);  				//访问根结点
    		PreOrder(T->lchild);	//递归遍历左子树
    		PreOrder(T->rchild);	//递归遍历右子树
    	}
    }

### 中序遍历 ###

先序遍历的操作过程如下：

1.  若二叉树为空，则什么也不做
2.  若二叉树非空：  
    ① 先序遍历左子树  
    ② 访问根结点  
    ③ 先序遍历右子树

//中序遍历
    void InOrder(BiTree T) {
        
    	if (T) {
        
    		InOrder(T->lchild);		//递归遍历左子树
    		visit(T);  				//访问根结点
    		InOrder(T->rchild);		//递归遍历右子树
    	}
    }

### 后序遍历 ###

//后序遍历
    void PostOrder(BiTree T) {
        
    	if (T) {
        
    		PostOrder(T->lchild);		//递归遍历左子树
    		PostOrder(T->rchild);		//递归遍历右子树
    		visit(T);  					//访问根结点
    	}
    }

### 快速求遍历序列 ###

![在这里插入图片描述][45eab8682c0743bfaef7df0c9991876c.png]

上图是以下列规则画出来的线路：

我们脑部空结点，首先从根结点出发，画一条路，如果左边还有没走的路，优先往左边走，走到路的尽头（空结点）就往回走；如果左边没路了，就往右边走；如果两边都没路，就往上面走

我们惊奇地发现，第一次路过的路线就是先序遍历的序列，第二次路过的路线就是中序遍历的序列，第三路过的路线就是后序遍历的序列

### 求树的深度 ###

int treeDepth(BiTree T) {
        
    	if (!T) return 0;
    	else {
        
    		int l = treeDepth(T->lchild);
    		int r = treeDepth(T->rchild);
    		//树的深度=Max(左子树深度, 右子树深度)+1
    		return l > r ? l + 1 : r + 1;
    	}
    }

## 二叉树的层序遍历 ##

### 算法思想 ###

层序遍历就是一层一层地对二叉树进行遍历

![在这里插入图片描述][982db6b9f37344a5b83144a4e4919551.png]

1.  初始化一个辅助队列
2.  根结点入队
3.  若队列非空，则队头结点出队，访问该结点，并将其左、右孩子插入队尾（如果有的话）
4.  重复第  3 3 3 步直到队列为空

### 代码实现 ###

//二叉树的结点
    typedef struct BiTNode {
        
    	char data;
    	struct BiTNode *lchild, *rchild;
    }BiTNode, *BiTree;
    
    //链式队列结点
    typedef struct LinkNode {
        
    	BiTNode *data;
    	struct LinkNode *next;
    }LinkNode;
    
    typedef struct {
        
    	LinkNode *front, *rear;		//队头队尾
    }LinkQueue;
    
    //层序遍历
    void LevelOrder(BiTree T) {
        
    	LinkQueue Q;					//初始化辅助队列
    	InitQueue(Q);					
    	BiTree p;
    	EnQueue(Q, T);					//让根结点入队
    	while (!IsEmpty(Q)) {
        			//队列不空则循环
    		DeQueue(Q, p);				//队头结点出队
    		visit(p);					//访问出队结点
    		if (p->lchild) {
        
    			EnQueue(Q, p->lchild);	//左孩子入队
    		} 
    		if (p->rchild) {
        
    			EnQueue(Q, p->rchild);	//右孩子入队
    		} 
    	}
    }

## 由遍历序列构造二叉树 ##

如果只给出一棵二叉树的前 / 中 / 后 / 层 序遍历中的一种，我们是不能唯一确定一棵二叉树的

只有给出下列遍历序列，我们才能确定唯一的二叉树

*  前序 + 中序遍历序列
 *  后序 + 中序遍历序列
 *  层序 + 中序遍历序列

注意：其中都有中序遍历序列，这是因为我们可以通过前序、后序和层序遍历序列来找到根结点，并根据中序序列划分左右子树，再找到左右子树根结点，这样才能确定唯一的一棵二叉树

## 线索二叉树 ##

在一棵普通的二叉树中，如何找到指定结点  p p p 在中序遍历序列中的前驱和后继呢？

思路：

从根结点出发，重新进行一次中序遍历，指针  p p p 记录当前访问的结点，指针  p r e pre pre 记录上一个被访问的结点

*  当  q = = p q==p q==p 时， p r e pre pre 为前驱
 *  当  p r e = = p pre==p pre==p 时， q q q 为后继

这样查找的缺点就是很不方便，遍历操作必须从根开始

所以线索二叉树出现了

在  n n n 个结点的二叉树中，有  n + 1 n+1 n\+1 个空链域，我们可以利用这些空链域来记录前驱和后继的信息

### 线索二叉树的存储结构 ###

下面是一棵中序线索二叉树，我们也可以将其称为线索链表

![在这里插入图片描述][ad0864d4691247d292a0fb89fb1f6df2.png]

//线索二叉树结点
    typedef struct ThreadNode{
        
    	ElemType data;
    	struct ThreadNode *lchild, *rchild;
    	int ltag, rtag;		//左、右线索标志
    }ThreadNode, *ThreadTree;

说明：

*   t a g = 0 tag=0 tag=0 时，表示指针指向孩子
 *   t a g = 1 tag=1 tag=1 时，表示指针是“线索”

添加了  t a g tag tag 后，中序线索二叉树就变成下面这样

![在这里插入图片描述][3add0ea5d6d74d92aba68726871c362f.png]

依次类推，我们也可以很容易地得到先序线索二叉树和后序线索二叉树

注意：

*  先序线索二叉树 —— 线索指向先序前驱、先序后继
 *  中序线索二叉树 —— 线索指向中序前驱、中序后继
 *  后序线索二叉树 —— 线索指向后序前驱、后序后继

## 二叉树的线索化 ##

### 中序线索化 ###

**首先，我们来看一下怎么暴力找到中序前驱？**

//辅助全局变量，用于查找结点 p 的前驱
    BiTNode *p;				//p 指向目标结点
    BiTNode *pre = NULL;	//pre 指向当前访问结点的前驱
    BiTNode *final = NULL;	//final 用于记录最终结果
    
    //访问结点 q
    void visit(BiTNode *q) {
        
    	if (q == p) {
        		//当前访问结点刚好是结点 p
    		final = pre;	//找到 p 的前驱
    	} else {
        
    		pre = q;		//pre 指向当前访问的结点
    	}
    }
    
    //查找中序前驱
    void findPre(BiTree T) {
        
    	if (T) {
        
    		findPre(T->lchild);		//递归遍历左子树
    		visit(T);  				//访问根结点
    		findPre(T->rchild);		//递归遍历右子树
    	}
    }

学习上面的思想，我们可以得到中序线索化的代码

//线索二叉树结点
    typedef struct ThreadNode{
        
    	ElemType data;
    	struct ThreadNode *lchild, *rchild;
    	int ltag, rtag;		//左右线索标志
    }ThreadNode, *ThreadTree;
    
    //全局变量 pre, 指向当前访问结点的前驱
    ThreadNode *pre = NULL;
    
    void visit(ThreadNode *q) {
        
    	if (!q->lchild) {
        	//左子树为空, 建立前驱线索
    		q->lchild = pre;
    		q->ltag = 1;
    	}
    
    	if (pre != NULL && pre->rchild == NULL) {
        	//建立前驱结点的后继线索
    		pre->rchild = q;	
    		pre->rtag = 1;
    	}
    	pre = q;
    }
    
    //中序遍历二叉树, 一边遍历一边线索化
    void InThread(ThreadTree T) {
        
    	if (T) {
        
    		InThread(T->lchild);	//中序遍历左子树
    		visit(T);				//访问根结点
    		InThread(T->rchild);	//中序遍历右子树
    	}
    }
    
    //中序线索化二叉树T
    void CreateInThread(ThreadTree T) {
        
    	pre = NULL;				//pre 初始化为 NULL
    	if (T) {
        				//非空二叉树才能线索化
    		InThread(T);		//中序线索化二叉树
    		if (!pre->rchild) {
        
    			pre->rtag = 1;	//处理遍历的最后一个结点
    		}
    	}
    }

另一种写法

//中序线索化
    void InThread(ThreadTree p, ThreadTree &pre) {
        
    	if (p) {
        
    		InThread(p->lchild, pre);		//递归，线索化左子树
    
    		if (!p->lchild) {
        				//左子树为空，建立前驱线索
    			p->lchild = pre;
    			p->ltag = 1;
    		}
    		if (pre && !pre->rchild) {
        		//建立前驱结点的后继线索
    			pre->rchild = p;
    			pre->rtag = 1;
    		}
    		
    		pre = p;						//标记当前结点称为刚刚访问过的结点
    		InThread(p->rchild, pre);		//递归，线索化右子树
    	}
    }
    
    //中序线索化二叉树T
    void CreateInThread(ThreadTree T) {
        
    	ThreadTree pre = NULL;
    	if (T) {
        					//非空二叉树才进行线索化
    		InThread(T, pre);		//线索化二叉树
    		pre->rchlid = NULL;		//处理遍历的最后一个结点
    		pre->rtag = 1;
    	}
    }

### 先序线索化 ###

//线索二叉树结点
    typedef struct ThreadNode{
        
    	ElemType data;
    	struct ThreadNode *lchild, *rchild;
    	int ltag, rtag;		//左右线索标志
    }ThreadNode, *ThreadTree;
    
    //全局变量 pre, 指向当前访问结点的前驱
    ThreadNode *pre = NULL;
    
    void visit(ThreadNode *q) {
        
    	if (!q->lchild) {
        	//左子树为空, 建立前驱线索
    		q->lchild = pre;
    		q->ltag = 1;
    	}
    
    	if (pre != NULL && pre->rchild == NULL) {
        	//建立前驱结点的后继线索
    		pre->rchild = q;	
    		pre->rtag = 1;
    	}
    	pre = q;
    }
    
    //先序遍历二叉树, 一边遍历一边线索化
    void PreThread(ThreadTree T) {
        
    	if (T) {
        
    		visit(T);				//访问根结点
    		if (T->ltag == 0) {
        		//lchild 不是前驱线索
    			PreThread(T->lchild);	//中序遍历左子树
    		}
    		PreThread(T->rchild);	//中序遍历右子树
    	}
    }
    
    //先序线索化二叉树T
    void CreatePreThread(ThreadTree T) {
        
    	pre = NULL;				//pre 初始化为 NULL
    	if (T) {
        				//非空二叉树才能线索化
    		PreThread(T);		//先序线索化二叉树
    		if (!pre->rchild) {
        
    			pre->rtag = 1;	//处理遍历的最后一个结点
    		}
    	}
    }

### 后序线索化 ###

//线索二叉树结点
    typedef struct ThreadNode{
        
    	ElemType data;
    	struct ThreadNode *lchild, *rchild;
    	int ltag, rtag;		//左右线索标志
    }ThreadNode, *ThreadTree;
    
    //全局变量 pre, 指向当前访问结点的前驱
    ThreadNode *pre = NULL;
    
    void visit(ThreadNode *q) {
        
    	if (!q->lchild) {
        	//左子树为空, 建立前驱线索
    		q->lchild = pre;
    		q->ltag = 1;
    	}
    
    	if (pre != NULL && pre->rchild == NULL) {
        	//建立前驱结点的后继线索
    		pre->rchild = q;	
    		pre->rtag = 1;
    	}
    	pre = q;
    }
    
    //后序遍历二叉树, 一边遍历一边线索化
    void PostThread(ThreadTree T) {
        
    	if (T) {
        
    		PostThread(T->lchild);	//中序遍历左子树
    		PostThread(T->rchild);	//中序遍历右子树
    		visit(T);				//访问根结点
    	}
    }
    
    //后序线索化二叉树T
    void CreatePostThread(ThreadTree T) {
        
    	pre = NULL;				//pre 初始化为 NULL
    	if (T) {
        				//非空二叉树才能线索化
    		PostThread(T);		//后序线索化二叉树
    		if (!pre->rchild) {
        
    			pre->rtag = 1;	//处理遍历的最后一个结点
    		}
    	}
    }

## 线索二叉树找前驱后继 ##

### 中序线索二叉树找中序后继 ###

在中序线索二叉树种找到指定结点  p p p 的中序后继  n e x t next next

思路：

*  若  p p p\-> r t a g = = 1 rtag==1 rtag==1，说明  p p p 的右孩子指针是 “线索”，则  n e x t = p next=p next=p\-> r c h i l d rchild rchild
 *  若  p p p\-> r t a g = = 0 rtag==0 rtag==0，则  n e x t next next 为  p p p 的右子树中最左下的结点

//找到以 p 为根的子树中，第一个被中序遍历的结点
    ThreadNode *FirstNode(ThreadNode *p) {
        
    	//循环找到最左下结点（不一定是叶子结点）
    	while (p->ltag == 0) p = p->lchild;
    	return p;
    }
    
    //在中序线索二叉树中找到结点 p 的后继结点
    ThreadNode *NextNode(ThreadNode *p) {
        
    	//右子树最左下结点
    	if (p->rtag == 0) return FirstNode(p->rchild);
    	else return p->rchild;		//rtag==1直接返回后继线索
    }
    
    //对中序线索二叉树进行中序遍历（利用线索实现的非递归算法）
    void Inorder(ThreadNode *T) {
        
    	for (ThreadNode *p = FirstNode(T); p != NULL; p = NextNode(p)) {
        
    		visit(p);
    	}
    }

### 中序线索二叉树找中序前驱 ###

在中序线索二叉树种找到指定结点  p p p 的中序前驱  p r e pre pre

思路：

*  若  p p p\-> l t a g = = 1 ltag==1 ltag==1，说明  p p p 的左孩子指针是 “线索”，则  p r e = p pre=p pre=p\-> l c h i l d lchild lchild
 *  若  p p p\-> l t a g = = 0 ltag==0 ltag==0，则  p r e pre pre 为  p p p 的左子树中最右下的结点

//找到以 p 为根的子树中，第一个被中序遍历的结点
    ThreadNode *LastNode(ThreadNode *p) {
        
    	//循环找到最右下结点（不一定是叶子结点）
    	while (p->rtag == 0) p = p->rchild;
    	return p;
    }
    
    //在中序线索二叉树中找到结点 p 的前驱结点
    ThreadNode *PreNode(ThreadNode *p) {
        
    	//左子树最右下结点
    	if (p->ltag == 0) return LastNode(p->lchild);
    	else return p->lchild;		//ltag==1直接返回前驱线索
    }
    
    //对中序线索二叉树进行逆向中序遍历（利用线索实现的非递归算法）
    void RevInorder(ThreadNode *T) {
        
    	for (ThreadNode *p = LastNode(T); p != NULL; p = PreNode(p)) {
        
    		visit(p);
    	}
    }

### 先序线索二叉树找先序后继 ###

在先序线索二叉树种找到指定结点  p p p 的先序后继  n e x t next next

思路：

*  若  p p p\-> r t a g = = 1 rtag==1 rtag==1，则  n e x t = p next=p next=p\-> r c h i l d rchild rchild
 *  若  p p p\-> r t a g = = 0 rtag==0 rtag==0，则当  p p p 有左孩子时，先序后继为左孩子；当  p p p 没有左孩子时，先序后继为右孩子

### 先序线索二叉树找先序前驱 ###

由于在先序遍历中，左右子树中的结点只可能是根的后继，不可能是前驱，所以除非从头开始先序遍历，不然是找不到先序前驱的

如果改用三叉链表，我们就可以找到父节点，进而找到先序前驱，需要考虑的情况有：

1.  如果能找到  p p p 的父节点，且  p p p 是左孩子，那么  p p p 的父节点即为其前驱
2.  如果能找到  p p p 的父节点，且  p p p 是右孩子，其左兄弟为空，那么  p p p 的父节点即为其前驱
3.  如果能找到  p p p 的父节点，且  p p p 是右孩子，其左兄弟非空，那么  p p p 的前驱为左兄弟子树中最后一个被先序遍历的结点
4.  如果  p p p 是根结点，则  p p p 没有先序前驱

### 后序线索二叉树找后序前驱 ###

在后序线索二叉树种找到指定结点  p p p 的后序前驱  p r e pre pre

思路：

*  若  p p p\-> l t a g = = 1 ltag==1 ltag==1，说明  p p p 的左孩子指针是 “线索”，则  p r e = p pre=p pre=p\-> l c h i l d lchild lchild
 *  若  p p p\-> l t a g = = 0 ltag==0 ltag==0，如果有右孩子，则后序前驱为右孩子；如果没有右孩子，则后序前驱为左孩子

### 后序线索二叉树找后序后继 ###

由于在后序遍历中，左右子树中的结点只可能是根的前驱，不可能是后继，所以除非从头开始先序遍历，不然是找不到后继的

如果改用三叉链表，我们就可以找到父节点，进而找到后序后继，需要考虑的情况有：

1.  如果能找到  p p p 的父节点，且  p p p 是右孩子，那么  p p p 的父节点即为其后继
2.  如果能找到  p p p 的父节点，且  p p p 是左孩子，其右兄弟为空，那么  p p p 的父节点即为其后继
3.  如果能找到  p p p 的父节点，且  p p p 是左孩子，其右兄弟非空，那么  p p p 的后继即为右兄弟子树中第一个被后序遍历的结点
4.  如果  p p p 是根结点，则  p p p 没有后序后继

[Link 1]: https://blog.csdn.net/weixin_62511863?spm=1011.2421.3001.5343
[Link 2]: https://blog.csdn.net/weixin_62511863/category_11984530.html?spm=1001.2014.3001.5482
[f76e6c96c9cf4e2aa7611cd3d0fcf731.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/0e5df2cc93e2444fb232262f9dc677b7.png
[45eab8682c0743bfaef7df0c9991876c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/7daca156e3ee40f7bdacc3367b0a1dca.png
[982db6b9f37344a5b83144a4e4919551.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/0a7f5caadfe24037b4ecf3c6d7942251.png
[ad0864d4691247d292a0fb89fb1f6df2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/29165d7d20494db5ac536403cf784781.png
[3add0ea5d6d74d92aba68726871c362f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/cc7bdd256318412ea8b421f266553ecf.png