数据结构MOOC|二叉树的遍历

浅浅的花香味﹌ 2022-05-24 09:39 122阅读 0赞

课程内容来自：[http://www.icourse163.org/learn/ZJU-93001?tid=1002654021\#/learn/content?type=detail&id=1003620984&cid=1004311357&replay=true][http_www.icourse163.org_learn_ZJU-93001_tid_1002654021_learn_content_type_detail_id_1003620984_cid_1004311357_replay_true]

二叉树遍历的核心问题：二维结构（树）的线性化（线性序列）

*  从当前结点访问其左右儿子结点；
 *  访问了左儿子后，如何访问右儿子？

> 需要一个存储结构保存暂时访问不到的结点（如右儿子或该结点自己）
> 
> 存储结构：堆栈、队列

## 【二叉树的非递归遍历】 ##

非递归算法实现的基本思路：利用堆栈

中序遍历非递归算法：

1.  遇到一个结点，就将其压栈，并遍历其左子树；
2.  当左子树遍历结束时，从栈顶弹出这个结点并访问它；
3.  然后按其右指针再去中序遍历该结点的右子树。

![20180524205748229][]

<table> 
 <tbody> 
 <tr> 
 <td>序号</td> 
 <td>栈内元素</td> 
 <td>操作</td> 
 <td>输出序列</td> 
 </tr> 
 <tr> 
 <td>1</td> 
 <td>A</td> 
 <td>PUSH</td> 
 <td>NULL</td> 
 </tr> 
 <tr> 
 <td>2</td> 
 <td>BA</td> 
 <td>PUSH</td> 
 <td>NULL</td> 
 </tr> 
 <tr> 
 <td>3</td> 
 <td>DBA</td> 
 <td>PUSH</td> 
 <td>NULL</td> 
 </tr> 
 <tr> 
 <td>4</td> 
 <td>BA</td> 
 <td>POP</td> 
 <td>D</td> 
 </tr> 
 <tr> 
 <td>5</td> 
 <td>A</td> 
 <td>POP</td> 
 <td>DB</td> 
 </tr> 
 <tr> 
 <td>6</td> 
 <td>FA</td> 
 <td>PUSH</td> 
 <td>DB</td> 
 </tr> 
 <tr> 
 <td>7</td> 
 <td>EFA</td> 
 <td>PUSH</td> 
 <td>DB</td> 
 </tr> 
 <tr> 
 <td>8</td> 
 <td>FA</td> 
 <td>POP</td> 
 <td>DBE</td> 
 </tr> 
 <tr> 
 <td>9</td> 
 <td>A</td> 
 <td>POP</td> 
 <td>DBEF</td> 
 </tr> 
 <tr> 
 <td>10</td> 
 <td>NULL</td> 
 <td>POP</td> 
 <td>DBEFA</td> 
 </tr> 
 <tr> 
 <td>10</td> 
 <td>C</td> 
 <td>PUSH</td> 
 <td>DBEFA</td> 
 </tr> 
 <tr> 
 <td>12</td> 
 <td>GC</td> 
 <td>PUSH</td> 
 <td>DBEFA</td> 
 </tr> 
 <tr> 
 <td>13</td> 
 <td>C</td> 
 <td>POP</td> 
 <td>DBEFAG</td> 
 </tr> 
 <tr> 
 <td>14</td> 
 <td>HC</td> 
 <td>PUSH</td> 
 <td>DBEFAG</td> 
 </tr> 
 <tr> 
 <td>15</td> 
 <td>C</td> 
 <td>POP</td> 
 <td>DBEFAGH</td> 
 </tr> 
 <tr> 
 <td>16</td> 
 <td>NULL</td> 
 <td>POP</td> 
 <td>DBEFAGHC</td> 
 </tr> 
 <tr> 
 <td>17</td> 
 <td>I</td> 
 <td>PUSH</td> 
 <td>DBEFAGHC</td> 
 </tr> 
 <tr> 
 <td>18</td> 
 <td>NULL</td> 
 <td>POP</td> 
 <td>DBEFAGHCI</td> 
 </tr> 
 </tbody> 
</table>

//中序遍历的非递归实现
 void InOrderTraversal( BinTree BT){
 BinTree T = BT;
 Stack S = CreatStack( MaxSize );
 while( T || !IsEmpty(S)){
 while(T){
 Push(S,T);
 T = T->Left;
 }
 if(!IsEmpty(S)){
 T = Pop(S);
 cout<<T->Data<<endl;
 T = T->Right;
 }
 }
 }

//先序遍历的非递归实现
 void InOrderTraversal( BinTree BT){
 BinTree T = BT;
 Stack S = CreatStack( MaxSize );
 while( T || !IsEmpty(S)){
 while(T){
 Push(S,T);
 cout<<T->Data<<endl;
 T = T->Left;
 }
 if(!IsEmpty(S)){
 T = Pop(S);
 T = T->Right;
 }
 }
 }

## 【层序遍历】 ##

基本思路:利用队列

层序遍历算法：

1.  从队列中取出一个元素；
2.  访问该元素所指结点；
3.  若该元素所指结点的左右儿子结点非空，则将其左右儿子的指针顺序入队。

![20180525095809191][]

<table> 
 <tbody> 
 <tr> 
 <td>序号</td> 
 <td>队列元素</td> 
 <td>输出序列</td> 
 </tr> 
 <tr> 
 <td>1</td> 
 <td>A</td> 
 <td>NULL</td> 
 </tr> 
 <tr> 
 <td>2</td> 
 <td>BC</td> 
 <td>A</td> 
 </tr> 
 <tr> 
 <td>3</td> 
 <td>CDF</td> 
 <td>AB</td> 
 </tr> 
 <tr> 
 <td>4</td> 
 <td>DFGI</td> 
 <td>ABC</td> 
 </tr> 
 <tr> 
 <td>5</td> 
 <td>FGI</td> 
 <td>ABCD</td> 
 </tr> 
 <tr> 
 <td>6</td> 
 <td>GIE</td> 
 <td>ABCDF</td> 
 </tr> 
 <tr> 
 <td>7</td> 
 <td>IEH</td> 
 <td>ABCDFG</td> 
 </tr> 
 <tr> 
 <td>8</td> 
 <td>EH</td> 
 <td>ABCDFGI</td> 
 </tr> 
 <tr> 
 <td>9</td> 
 <td>H</td> 
 <td>ABCDFGIE</td> 
 </tr> 
 <tr> 
 <td>10</td> 
 <td>NULL</td> 
 <td>ABCDFGIEH</td> 
 </tr> 
 </tbody> 
</table>

void LevelOrderTraversal( BinTree BT)
 {
 Queue Q;
 BinTree T;
 if( !BT ) return;
 Q = CreatQueue( MaxSize );
 AddQ( Q,BT );
 while( !IsEmptyQ( Q )){
 T = DeleteQ( Q );
 cout<<T->Data<<endl;
 if( T->Left ) AddQ( Q,T->Left );
 if( T->Right ) AddQ( Q,T->Right );
 }
 }

## 【应用】 ##

1.输出二叉树中的叶子结点

//在二叉树的遍历算法中增加检测结点的“左右子树是否都为空”
 void PreOrderPrintLeaves( BinTree BT )
 {
 if( BT ){
 if( !BT->Left && !BT->Right )
 cout<<BT->Data<<endl;
 PreOrderPrintLeaves( BT->Left );
 PreorderPrintLeaves( BT->Right );
 }
 }

2.求二叉树的高度（Height=max(H1,H2)+1）

![20180525151039667][]

int PostOrderGetHeight( BinTree BT )
    {
        int HL, HR, MaxH;
        if( BT ){
            HL = PostOrderGetHeight( BT->Left );
            HR = PostOrderGetHeight( BT->Right );
            MaxH = ( HL > HR )? HL: HR;
            return ( MaxH+1 );
        }
        else return 0;
    }

3.二元运算表达式树及其遍历

![20180525151337563][]

4.前/后序遍+中序遍历，可以唯一确定一棵树；但前序遍历+后序遍历不可唯一确定一棵树。

![20180525151557491][]

如上图，中序遍历可以将左右子树分隔开来。诶呦中序则无法确定左右，如下图：

![20180525151741222][]

[http_www.icourse163.org_learn_ZJU-93001_tid_1002654021_learn_content_type_detail_id_1003620984_cid_1004311357_replay_true]: http://www.icourse163.org/learn/ZJU-93001?tid=1002654021#/learn/content?type=detail&id=1003620984&cid=1004311357&replay=true
[20180524205748229]: /images/20220524/2be2fc3ce3494ad895cc7be61b513957.png
[20180525095809191]: /images/20220524/425d3b1e4a9c4fd58519967e92d12888.png
[20180525151039667]: /images/20220524/2a3347001d1d47b497593de1af9722b1.png
[20180525151337563]: /images/20220524/44cb2848aa314a3eb80c0aaff02ad396.png
[20180525151557491]: /images/20220524/6c7a1c23ac724286bbb8626a9fade510.png
[20180525151741222]: /images/20220524/25119007caed4dccaf83551a1e12abda.png