二叉树的存储和遍历

小咪咪 2022-11-04 00:51 126阅读 0赞

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

## 1. 顺序存储 ##

用一组连续的存储单元依次自上而下、自左至右存储完全二叉树上的结点元素。

> 注意，存放的是是完全二叉树的结点元素。

**例如：**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ1NjUxMjc_size_16_color_FFFFFF_t_70]  
**如何表示结点的逻辑关系呢？**

在完全二叉树中依次编号，对于结点`i`:

*  若存在左孩子，则编号为`2i`;
 *  若存在右孩子，则编号为`2i+1`。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ1NjUxMjc_size_16_color_FFFFFF_t_70 1]
    
    > 我们空出0索引的单元，就是为了能更好的利用上述的性质。  
    > 一般情况下，我们会在0索引的位置存放二叉树的结点个数，并不会浪费空间。  
    > 如果我们从第0个存储，左孩子的结点变为`2i+1`，右孩子的结点变为了`2i+2`。

**为什么只能存储完全二叉树呢？如果是非完全二叉树会怎么样？**  
![在这里插入图片描述][20210301095119702.png]  
如果存放的是非完全二叉树，用顺序存储的方式就无法表示逻辑关系了。

我们该用什么样的方法来表示呢？我们可以补全完全二叉树，用0填补空缺的位置：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ1NjUxMjc_size_16_color_FFFFFF_t_70 2]  
**可是这样存储会有很大的弊端，例如我们有这样一棵二叉树：**  
![在这里插入图片描述][20210301095433565.png]  
如果我们想要存放，要补全成为一棵完全二叉树：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ1NjUxMjc_size_16_color_FFFFFF_t_70 3]  
如果我们仍然按照顺序存储的话，会浪费很多存储空间。

**总结：**  
**顺序存储最坏情况下会非常浪费存储空间，比较适合完全二叉树。**

--------------------

## 2. 链式存储 ##

用链表来存放一棵二叉树，二叉树中每个结点用链表的一个链结点来存储。

每个结点需要两个指针，分别指向左孩子结点和右孩子结点。  
![在这里插入图片描述][20210301095905458.png]

typedef struct BiTNode{ 
    	ElemType data;
    	struct BiTNode *lchild,*rchild;
    }BiTNode, *BiTree;

**例如：**

一棵非完全二叉树：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ1NjUxMjc_size_16_color_FFFFFF_t_70 4]  
对于一些没有左孩子或右孩子或都没有的结点，产生了一些空的指针域。

对于这些指针域，我们有一条性质：

*含有 n个结点的二叉链表中，有 n+1个空链域。*

> 首先，有n个结点，就会有2n个指针域。  
> 指针域会指向孩子结点，否则就会为空，结点为n的二叉树，孩子结点个数为n-1。  
> 所以，空链域的个数为 2n-(n-1) = `n+1`。

另外，有时候为了实现某些特定的算法，有的链式存储结构也会有三个指针域，除了指向两个孩子结点的指针，还会有指向双亲结点的指针。

# 二、二叉树的遍历 #

按某条搜索路径访问树中的每个结点，树的每个结点均被访问一次，而且只访问一次。

## 1.先/中/后序遍历 ##

![在这里插入图片描述][202103011337390.png]  
先序遍历：根左右  
中序遍历：左根右  
后序遍历：左右根

> 三种遍历方式，都是先访问左子树再访问右子树。唯一的区别就是根的次序不同。这样也很容易记忆。

**1. 先序遍历**  
若二叉树非空：

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

**2. 中序遍历**  
若二叉树非空：

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

**3. 后序遍历**  
若二叉树非空：

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

以上的遍历都是使用递归算法实现的，我们接下来看一下**非递归的遍历算法：**  
（借助栈来实现）

1.  初始时依次扫描根结点并将它们——进栈
2.  出栈一个结点 访问他
3.  扫描该结点的右孩子结点并将其入栈
4.  依次扫描右孩子结点的所有左侧结点——入栈
5.  反复该过程直到栈空为止
    
        void InOrder2(BiTree T){ 
        	InitStack(S);
        	BiTree p = T;
        	while(p || !IsEmpty(S)){ 
        	 if(p){ 
        	 	Push(S, p);
        	 	p = p->lchild;
        	 }
        	 else{ 
        	 	Pop(S, p);
        	 	visit(p);
        	 	p = p->rchild;
        	 }
        	}
        }

把上面的代码对照下面的图，认真的把流程跑一遍，你就明白了。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ1NjUxMjc_size_16_color_FFFFFF_t_70 5]

## 2. 层次遍历 ##

借助队列实现层次遍历。

> **算法思想:**
> 
> 1.  初始将根入队并访问根结点;
> 2.  若有左子树，则将左子树的根入队;
> 3.  若有右子树，则将右子树的根入队;
> 4.  将队首元素出队，并访问该结点;
> 5.  反复该过程直到队列空为止。

**代码：**

void levelOrder(BiTree T){ 
    	InitQueue(Q);
    	BiTree p;
    	EnQueue(Q, T);
    	while(!isEmpty(Q)){ 
    		DeQueue(Q, p);
    		visit(p);
    		if(p->lchild != null){ 
    			EnQueue(Q, p->lchild);
    		}
    		if(p->rchild != null){ 
    			EnQueue(Q, p->rchild);
    		}
    	}
    }

一样的道理，你对照下面的图和代码认真的将流程跑一遍，你就明白了。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ1NjUxMjc_size_16_color_FFFFFF_t_70 6]

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

首先思考一个问题，我们既然能对一棵二叉树进行遍历得到一个序列，那么我们能通过一个遍历序列来构造出一棵二叉树吗？

我们如果只有一个序列，我们是可以构造出很多种二叉树形式的。

实际上，我们在拥有先序(或后序）遍历序列和中序遍历序列才可以确定一棵二叉树。

> 而后序遍历序列和先序遍历序列不可以确定一棵二叉树。

**中序遍历序列和先序遍历序列：**

1.  在先序序列中，第一个节点是根节点；
2.  根节点将中序遍历划分为两个部分；
3.  然后在先序序列中确定两部分的结点，并且两部分的第一个结点分别为左子的根和右子树的根；
4.  在子树中递归重复该过程，便能唯一确定一棵二叉树。

我们用一个例子，来演示一下这种算法：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ1NjUxMjc_size_16_color_FFFFFF_t_70 7]

--------------------

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

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ1NjUxMjc_size_16_color_FFFFFF_t_70 8]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ1NjUxMjc_size_16_color_FFFFFF_t_70]: /images/20221023/2a104a0504514a4fbaea999062a8340a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ1NjUxMjc_size_16_color_FFFFFF_t_70 1]: /images/20221023/d629f699bc3d4a078dd7826bb3856113.png
[20210301095119702.png]: /images/20221023/c7bc487dd9484eb8bc12d6eb6af9516c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ1NjUxMjc_size_16_color_FFFFFF_t_70 2]: /images/20221023/d09988b26c1a4c94a379dc3e6eb64135.png
[20210301095433565.png]: /images/20221023/eefd8a7bf9b84e588d011284f2d9f736.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ1NjUxMjc_size_16_color_FFFFFF_t_70 3]: /images/20221023/e1842ce0e92b47ea80da8bd1b1d398d7.png
[20210301095905458.png]: /images/20221023/192fbd94d2a14988acb25d7d6a616522.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ1NjUxMjc_size_16_color_FFFFFF_t_70 4]: /images/20221023/4f60a237eb7a4a3aa4da4e854dae6f4e.png
[202103011337390.png]: /images/20221023/222af622c2ea4350a1fc55b9adef2215.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ1NjUxMjc_size_16_color_FFFFFF_t_70 5]: /images/20221023/2e83cb206f2349febf7229a5fd709a31.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ1NjUxMjc_size_16_color_FFFFFF_t_70 6]: /images/20221023/3abba3d0d47f427080ee3386a24759bb.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ1NjUxMjc_size_16_color_FFFFFF_t_70 7]: /images/20221023/491dfd58ad964429a2a18f5bf1b0cbe8.png
[20210310114512810.png]: /images/20221023/8cb6c6d2dca643eaaea21c8ab322e7ce.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ1NjUxMjc_size_16_color_FFFFFF_t_70 8]: /images/20221023/f062deea1e014555b328652434fc1bf7.png