【数据结构】二叉树的存储和遍历

￡神魔★判官ぃ 2021-11-01 02:58 388阅读 0赞

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

#### 顺序存储结构 ####

二叉树的顺序存储结构是指用一组地址连续的存储单元依次**自上而下、从左到右**存储完全二叉树上的结点，即将完全二叉树上编号为 i 的结点存储在数组下标为 i−1的数组分量中，然后通过一定方式确定结点在逻辑上的父子或兄弟关系。  
   ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzU1MTAzNg_size_16_color_FFFFFF_t_70]  
空间浪费比较大

#### 链式存储结构 ####

二叉树每个结点最多两个孩子，所以设计二叉树的结点结构时考虑两个指针指向该结点的两个孩子。  
![在这里插入图片描述][20190813175811269.png]  
二叉树结点结构：

typedef struct BiTNode{
    	ElemType data;						//定义数据域
    	struct BiTNode *lchild, *rchild;	//定义左、右指针
    }BiTNode, *BiTree;

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzU1MTAzNg_size_16_color_FFFFFF_t_70 1]  
这种结构的链表由于有两个指针，所以叫**二叉链表**  
另外还可以增加指针指向该结点的双亲结点，那这时三个指针的链表就叫**三叉链表**

### 二叉树的遍历（递归） ###

遍历，是指按照某条搜索路径访问树中的每一个结点，使得每个结点**均会被访问一次**，而且**仅被访问一次**。

由二叉树的递归定义可知，遍历一棵二叉树首先需要确定对根结点、左子树和右子树的访问顺序。常见的遍历次序有先序遍历 (NLR) 、中序遍历 (LNR) 和后序遍历 (LRN) 三种。

#### 递归先序遍历 ####

若二叉树为空，则不采取操作，否则：

1.  访问根结点；
2.  先序遍历左子树；
3.  先序遍历右子树。

对应的递归算法：

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

#### 递归中序遍历 ####

若二叉树为空，则不进行操作，否则：

1.  中序遍历左子树；
2.  访问根结点；
3.  中序遍历右子树。

对应的递归算法：

void  InOrder(BiTree T){
    	if(T != NULL){
    		InOrder(T->lchild);	//递归访问左子树
    		visit(T);			//访问根结点
    		InOrder(T->rchild);	//递归访问右子树
    	}
    }

#### 递归后序遍历 ####

若二叉树为空，则不进行操作，否则：

1.  后序遍历左子树；
2.  后序遍历右子树；
3.  访问根结点。

对应的递归算法：

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

### 二叉树的遍历（非递归） ###

借助到栈

#### 非递归先序遍历 ####

Void PreOrderTraverse(BiTree b){
    	InitStack(S);
    	BiTree p=b;						 //工作指针p
    	while(p || !IsEmpty(S)){
    		while(p){
    			printf(“%c”,p->data); 	//先序先遍历结点
    			Push(S,p); 				//进栈保存
    			p=p->lchild;			//指向左孩子
    		}
    		if(!IsEmpty(S)){
    			p=Pop(S);				//出栈
    			p=p->rchild;			//指向右孩子
    		}
    	}
    }

例子：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzU1MTAzNg_size_16_color_FFFFFF_t_70 2]

过程：
    p指向A，打印A, A进栈，
    p指向B，打印B，B进栈，
    p指向D，打印D，D进栈
    p指向NULL，栈不为空，弹出栈顶D，p指向D的右孩子G
    打印G，G进栈，
    p指向NULL，栈不为空，弹出栈顶G，
    p指向NULL，栈不为空，弹出栈顶B，
    p指向NULL，栈不为空，弹出栈顶A，
    p指向C，打印C，C进栈，
    p指向E，打印E，E进栈
    p指向NULL，栈不为空，弹出栈顶E
    p指向NULL,栈不为空，弹出栈顶C，
    p指向F，打印F，F进栈
    p指向NULL，栈不为空，弹出栈顶F
    p指向NULL，栈空，结束
    打印的序列为：A B D G C E F

#### 非递归中序遍历 ####

Void PreOrderTraverse(BiTree b){
    	InitStack(S);
    	BiTree p=b; //工作指针p
    	while(p || !IsEmpty(S)){
    		while(p){ //中序先将结点进栈保存
    			Push(S,p);
    			p=p->lchild;
    	 }
    		//遍历到左下角尽头再出栈访问
    		p=Pop(S);
    		printf(“%c”,p->data);
    		p=p->rchild; //遍历右孩子
    	}
    }

#### 非递归后序遍历 ####

Void PostOrderTraverse(BiTree b){
    	InitStack(S);
    	BiTree p=b，r=NULL; //工作指针p 辅助指针r
    	while(p || !IsEmpty(S)){
    		//1.从根结点到最左下角的左子树都入栈
    		if(p){
    			Push(S,p);
    			p=p->lchild;
    		}
    		//2.返回栈顶的两种情况
    		else{
    			GetTop(S,p); //取栈顶 注意不是出栈！
    			//①右子树还未访问，而且右子树不空，第一次栈顶
    			if(p->rchild &&p->rchild !=r) 
    				p=p->rchild;
    			//②右子树已经访问或为空，接下来出栈访问结点
    			else{
    				Pop(S,p);
    				printf(“%c”,p->data);
    				r=p; //指向访问过的右子树根结点
    				p=NULL; //使p为空从而继续访问栈顶
    			}
    		}
    	}
    }

#### 层序遍历 ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzU1MTAzNg_size_16_color_FFFFFF_t_70 3]  
如图所示为二叉树的层次遍历，即按照箭头所指方向，按照层次1，2，3，4的顺序，横向遍历对二叉树中的结点进行访问。

进行层次遍历需要借助**队列**：先将二叉树根结点入队，然后出队并访问该结点，若有左子树，则将左子树根结点入队；若有右子树，则将右子树根结点入队。然后出队并对出队结点进行访问，重复上述操作直到队列为空。  
思路：**出队→访问→左右孩子入队**

二叉树的层次遍历算法：

void LevelOrder(BiTree T){
    	InitQueue(Q);				//创建空队列 Q
    	BiTree p;					//创建遍历指针 p
    	EnQueue(Q, T);				//根结点入队
    	while(! IsEmpty Q){			//队列非空则继续循环进行遍历
    		DeQueue(Q, p);			//队头元素出队
    		visit(p);				//访问出队结点
    		if(p->lchild != NULL)		//若左子树存在
    			EnQueue(Q, p->Lchild);	//左子树根结点入队
    		if(p->child != NULL)		//若右子树存在
    			EnQueue(Q, p->rchild);	//右子树根结点入队
    	}
    }

### 线索二叉树 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzU1MTAzNg_size_16_color_FFFFFF_t_70 4]  
二叉链表表示的二叉树存在大量空指针  
N个结点的二叉链表，每个结点都有指向左右孩子的结点指针，所以一共有2N个指针，而N个结点的二叉树一共有N-1条分支，也就是说存在2N-(N-1)=**N+1个空指针**。比如上图二叉树中有6个结点，那么就有7个空指针。  
![在这里插入图片描述][20190813191742652.png]

> 大量空余指针能否利用起来？

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzU1MTAzNg_size_16_color_FFFFFF_t_70 5]

指向前驱和后继的指针成为线索，加上线索的二叉链表就成为线索链表，相应的二叉树被称为**线索二叉树**  
对二叉树以某种次序遍历使其变为线索二叉树的过程就叫做**线索化**

> 如何区分指针是指向左孩子还是前驱，或者指向右孩子还是后继？

在二叉链表结点的结构基础上增加两个标志位**ltag**和**rtag**

typedef struct ThreadNode{
    	ElemType data;
    	struct ThreadNode *lchild,*rchild;
    	int ltag,rtag;
    }ThreadNode,*ThreadTree; //线索链表

<table> 
 <thead> 
  <tr> 
   <th>lchild</th> 
   <th>ltag</th> 
   <th>data</th> 
   <th>rtag</th> 
   <th>rchild</th> 
  </tr> 
 </thead> 
 <tbody></tbody> 
</table>

> ltag == 0 代表lchild指向该结点的左孩子  
> ltag ==1 代表lchild指向该结点的前驱
> 
> rtag == 0 代表rchild指向该结点的右孩子  
> rtag ==1 代表rchild指向该结点的后继

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzU1MTAzNg_size_16_color_FFFFFF_t_70 6]

void InThread(ThreadTree &p,ThreadTree &pre){
    //中序遍历对二叉树线索化的递归算法
    	if(p){
    		InThread(p->lchild,pre);
    		//修改前驱
    		if(p->lchild==NULL){
    			p->lchild=pre;
    			p->ltag=1;
    		}
    		//修改后继
    		if(pre!=NULL&&pre->rchild==NULL){
    			pre->rchild=p;
    			pre->rtag=1;
    		}
    		pre=p;
    		InThread(p->rchild,pre);
    	}
    }

#### 遍历线索二叉树 ####

void InOrderTraverse(ThreadTree T){
    	ThreadTree p=T；
    	while(p){
    		while(p->ltag==0)p=p->lchild;
    		printf(“%c”,p->data);
    		while(p->rtag==1&&p->rchild){
    			p=p->rchild;
    			printf(“%c”,p->data);
    		}
    		p=p->rchild;
    	}
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzU1MTAzNg_size_16_color_FFFFFF_t_70 7]

#### 参考资料 ####

王道数据结构

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzU1MTAzNg_size_16_color_FFFFFF_t_70]: /images/20211101/ed4d5155878543898554658c331bb13c.png
[20190813175811269.png]: /images/20211101/e96af11a1d784c1785c78d0324f8a974.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzU1MTAzNg_size_16_color_FFFFFF_t_70 1]: /images/20211101/70083cb2b65142d3a8e302a4e933d087.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzU1MTAzNg_size_16_color_FFFFFF_t_70 2]: /images/20211101/73040b097f0f4e3f89c39ef21501f9f9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzU1MTAzNg_size_16_color_FFFFFF_t_70 3]: /images/20211101/39562076c6da403d95ba9689e1fa558f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzU1MTAzNg_size_16_color_FFFFFF_t_70 4]: /images/20211101/30f002dffe784679a033ce124637f67a.png
[20190813191742652.png]: /images/20211101/096418a52dc34cdcb50595848d16ba03.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzU1MTAzNg_size_16_color_FFFFFF_t_70 5]: /images/20211101/8e1dee2785e64415b4b5f95d6706fde8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzU1MTAzNg_size_16_color_FFFFFF_t_70 6]: /images/20211101/d6b394e3e4c14dd38de47173f3d35954.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzU1MTAzNg_size_16_color_FFFFFF_t_70 7]: /images/20211101/a551c60bfeab4211ad551670f46755a0.png