數據結構基礎（12）

二叉樹的先序遍歷

• 遍歷：按某種次序把所有結點都訪問一遍 – > 線性結構
• 層次遍歷：基于樹的層次特性確定的次序規則
• 二叉樹的先/中/后序遍歷：基于樹的遞歸特性確定的次序規則

二叉樹的遞歸特性

1. 要么是個空二叉樹
2. 要么就是由“根節點 + 左子樹 + 右子樹”組成的二叉樹

先序遍歷：根左右（NLR）-- > 又叫先根遍歷

中序遍歷：左根右（LNR）- > 又叫中根遍歷

后序遍歷：左右根（LRN）- > 又叫后根遍歷

基礎圖：

先序遍歷： ABC

中序遍歷：BAC

后序遍歷：BCA

在加深一點：

先序遍歷： A B D E C F G

中序遍歷; D B E A F C G

后序遍歷：D E B F G C A

對算數表達式的“分析樹”：

先序遍歷 — > 前綴表達式

中序遍歷 — > 中綴表達式（需要加界限符）

后序遍歷 — > 后綴表達式

先序遍歷

先序遍歷（PreOrder）的操作過程如下：

1. 若二叉樹為空，則什么也不做；
2. 若二叉樹非空：
   ①訪問根結點；
   ②先序遍歷左子樹
   ③先序遍歷右子樹

實現代碼：

typedef struct BiTNode{ElemType data;struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;//先序遍歷
void PreOrder(BiTree T){if(T!=NULL){visit(T);                //訪問根結點PreOrder(T->lchild);     //遞歸遍歷左子樹PreOrder(T->rchild);     //遞歸遍歷右子樹}
}

第一次被訪問的點

空間復雜度：O(h)

中序遍歷

中序遍歷（InOrder）的操作過程如下：

1. 若二叉樹為空，則什么也不做；
2. 若二叉樹非空：
   ①先序遍歷左子樹；
   ②訪問根結點；
   ③先序遍歷右子樹。

實現代碼：

typedef struct BiTNode{ElemType data;struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;//中序遍歷
void InOrder(BiTree T){if(T!=NULL){InOrder(T->lchild);  //遞歸遍歷左子樹visit(T);            //訪問根結點InOrder(T->rchild);  //遞歸遍歷右子樹}
}

第二次被訪問的點

后序遍歷

后序遍歷（PostOrder）的操作過程如下：

1. 若二叉樹為空，則什么也不做；
2. 若二叉樹非空：
   ①先序遍歷左子樹；
   ②先序遍歷右子樹；
   ③訪問根結點。

實現代碼：

typedef struct BiTNode{ElemType data;struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;//后序遍歷
void PostOrder(BiTree T){if(T!=NULL){PostOrder(T->lchild);  //遞歸遍歷左子樹PostOrder(T->rchild);  //遞歸遍歷右子樹visit(T);              //訪問根結點}
}

第三次被訪問的點

二叉樹的層序遍歷

算法思想：

算法思想：

1. 初始化一個輔助隊列
2. 根結點入隊
3. 若隊列非空，則隊頭結點出隊，訪問該結點，并將其左、右孩子插入隊尾（如果有的話）
4. 重復步驟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!=NULL)EnQueue(Q,p->lchild); //左孩子入隊if(p->rchild!=NULL)EnQueue(Q,p->rchild); //右孩子入隊}
}

? 存指針而不是結點

    BiTNode * data;

由遍歷序列構造二叉樹

• 一個中序遍歷序列可能對應多種二叉樹形態

• 一個前序遍歷序列可能對應多種二叉樹形態

• 一個后序遍歷序列可能對應多種二叉樹形態

• 一個層序遍歷序列可能對應多種二叉樹形態

SO : 若只給出一顆二叉樹的前/中/后/層 序遍歷序列中的一種 ，不能唯一確定一顆二叉樹

前序 + 中序遍歷序列

• 前序遍歷：根結點、前序遍歷左子樹、前序遍歷右子樹

前序遍歷序列：

根結點 左子樹的前序遍歷序列 右子樹的前序遍歷序列

• 中序遍歷：中序遍歷左子樹、根結點、中序遍歷右子樹

中序遍歷序列:

左子樹的中序遍歷序列 根結點 右子樹的中序遍歷序列

前序遍歷序列： A D B C E

中序遍歷序列： B D C A E

得出的二叉樹：

后序 + 中序遍歷序列

• 后序遍歷：前序遍歷左子樹、前序遍歷右子樹、根結點

后序遍歷序列：

左子樹的后序遍歷序列 右子樹的后序遍歷序列 根結點

• 中序遍歷：中序遍歷左子樹、根結點、中序遍歷右子樹

中序遍歷序列

左子樹的中序遍歷序列 根結點 右子樹的中序遍歷序列

后序遍歷序列： E F A H C I G B D

中序遍歷序列： E A F D H C B G I

得出的二叉樹：

層序 + 中序遍歷序列

• 層序遍歷序列

  根結點 左子樹的根 右子樹的根

• 中序遍歷序列

  左子樹的中序遍歷序列 根結點 右子樹的中序遍歷序列

層序遍歷序列：A B C D E

中序遍歷序列：A C B E D

得出的二叉樹：

KEY:找到樹的根節點，并根據中序序列劃分左右子樹，再找到左右子樹根結點

二叉樹的中序遍歷（缺點）：

Q1：如何找到指定結點 P 在中序遍歷序列中的前驅？

Q2 : 如何找到 p 的中序后繼？

思路：從根節點出發，重新進行一次中序遍歷，指針 q 記錄當前訪問的結點，指針 pre 記錄上一個被訪問的結點

1.當 q == p 時，pre 為前驅

2.當 pre == p 時，q 為后繼

缺點：

找前驅、后繼很不方便：遍歷操作必須從根開始

中序線索二叉樹

中序遍歷序列：D G B E A F C

• 前驅線索（由左孩子指針充當 —— > 紅色線
• 后繼線索（由右孩子指針充當）—— > 綠色線

線索鏈表代碼實現：

//線索二叉樹結點
typedef struct ThreadNode{ElemType data;struct ThreadNode *lchild,*rchild;int ltag,rtag;      //左、右線索標志
}ThreadNode,*ThreadTree;

• tag == 0，表示指針指向孩子
  tag ==1，表示指針是“線索”

• 先序、后序同理

中序線索化

實現代碼

// 線索二叉樹結點結構定義
typedef struct ThreadNode{ElemType data;  struct ThreadNode *lchild,*rchild;  int ltag,rtag; 
}ThreadNode,*ThreadTree;// 全局變量 pre，指向當前訪問結點的前驅
ThreadNode *pre=NULL;  // 中序遍歷二叉樹并進行線索化
void InThread(ThreadTree T){if(T!=NULL){InThread(T->lchild);visit(T); InThread(T->rchild);  }
}// 訪問結點函數（實際處理線索化邏輯）
void visit(ThreadNode *q) {// 左子樹為空，建立前驅線索if(q->lchild==NULL){ q->lchild=pre;q->ltag=1;}// 前驅存在且前驅的右孩子為空，建立前驅結點的后繼線索if(pre!=NULL&&pre->rchild==NULL){ pre->rchild=q;  pre->rtag=1;}pre=q;  // 更新pre為當前結點
}// 封裝中序線索化的入口函數，統一初始化pre并處理最終結點
void CreateInThread(ThreadTree T){pre=NULL;  // 初始化為NULLif(T!=NULL){  InThread(T); // 處理遍歷的最后一個結點：若其右孩子為空，標記為線索if(pre->rchild==NULL){ pre->rtag=1;  }}
}

先序線索化

• 先序線索化中，注意處理愛滴魔力轉圈圈問題，當 ltag == 0時，才能對左子樹先序線索化

實現代碼；

// 線索二叉樹結點結構定義
typedef struct ThreadNode{ElemType data;struct ThreadNode *lchild, *rchild;int ltag, rtag;
}ThreadNode, *ThreadTree;// 全局變量 pre，指向當前訪問結點的前驅
ThreadNode *pre = NULL;  // 先序遍歷二叉樹，一邊遍歷一邊線索化
void PreThread(ThreadTree T){if(T != NULL){visit(T);  // 先處理根節點（執行線索化核心邏輯）// lchild 不是前驅線索（即 ltag == 0 時，說明是真實孩子，遞歸處理左子樹）if (T->ltag == 0)  PreThread(T->lchild);  PreThread(T->rchild);  // 遞歸處理右子樹}
}// 訪問結點函數（實際進行線索化操作）
void visit(ThreadNode *q) {// 左子樹為空，建立前驅線索if(q->lchild == NULL){  q->lchild = pre;q->ltag = 1;}// 前驅存在且前驅的右孩子為空，建立前驅結點的后繼線索if(pre != NULL && pre->rchild == NULL){  pre->rchild = q;  pre->rtag = 1;}pre = q;  // 更新 pre 為當前結點，為下一個結點做準備
}// 先序線索化二叉樹的入口函數，統一初始化 pre 并處理最后一個結點
void CreatePreThread(ThreadTree T){pre = NULL;  // pre 初始化為 NULLif(T != NULL){  // 非空二叉樹才進行線索化PreThread(T);  // 調用先序線索化遞歸函數// 處理遍歷的最后一個結點：若其右孩子為空，標記為線索if (pre->rchild == NULL)  pre->rtag = 1;  }
}

后序線索化

實現代碼：

// 線索二叉樹結點結構（需提前定義 ElemType，如 typedef int ElemType; ）
typedef struct ThreadNode {ElemType data;struct ThreadNode *lchild, *rchild;int ltag, rtag;  // 0: 指向孩子，1: 線索
} ThreadNode, *ThreadTree;// 全局變量：指向當前訪問結點的前驅
ThreadNode *pre = NULL;  // 后序遍歷 + 線索化（遞歸邏輯：左 → 右 → 根）
void PostThread(ThreadTree T) {if (T != NULL) {PostThread(T->lchild);  // 后序遍歷左子樹PostThread(T->rchild);  // 后序遍歷右子樹visit(T);  // 訪問根節點（執行線索化操作）}
}// 訪問結點函數（處理線索化邏輯）
void visit(ThreadNode *q) {// 左子樹為空 → 建立前驅線索if (q->lchild == NULL) {  q->lchild = pre;q->ltag = 1;}// 前驅存在且其右孩子為空 → 建立后繼線索if (pre != NULL && pre->rchild == NULL) {  pre->rchild = q;  pre->rtag = 1;}pre = q;  // 更新前驅為當前結點
}// 后序線索化入口函數（初始化 + 處理最后結點）
void CreatePostThread(ThreadTree T) {pre = NULL;  // 初始化前驅if (T != NULL) {  // 非空樹才線索化PostThread(T);  // 調用后序線索化// 處理遍歷的最后一個結點（根結點）if (pre->rchild == NULL) {  pre->rtag = 1;  }}
}

中序線索二叉樹找中序后繼

在中序線索二叉樹中找到指定結點 * p 的中序后繼 next

1. 若 p->rtag == 1，則 next = p->rchild
2. 若 p->rtag == 0

next = 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);
}

空間復雜度O(1)

中序線索二叉樹找中序前驅

在中序線索二叉樹中找到指定結點 * p 的中序前驅 pre

1. 若 p->ltag == 1，則 pre = p->lchild
2. 若 p->ltag == 0

pre = 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 的中序后繼 next

1. 若 p->rtag == 1，則 pre = p->rchild
2. 若 p->rtag == 0

假設有左孩子

• 若 p 有左孩子，則先序后繼為左孩子

先序遍歷 —— 根 左 右
根 (根 左 右) 右

假設沒有左孩子

• 若 p 沒有左孩子，則先序后繼為右孩子

先序遍歷 —— 根 右
根 (根 左 右)

先序線索二叉樹找先序前驅

在先序線索二叉樹中找到指定結點 * p 的中序前驅 pre

1. 若 p->ltag == 1，則 pre = p->lchild
2. 若 p->ltag == 0

在先序遍歷中，左右子樹的結點只可能是根的后繼，不可能是前驅

后序線索二叉樹找后序前驅

在先序線索二叉樹中找到指定結點 * p 的中序前驅 pre

1. 若 p->ltag == 1，則 pre = p->lchild
2. 若 p->ltag == 0

假設有右孩子

• 若 p 有右孩子，則后序前驅為右孩子

后序遍歷 —— 左 右 根
左 (左 右 根) 根

假設沒有右孩子

• 若 p 沒有右孩子，則后序前驅為左孩子

后序遍歷 —— 左 根
(左 右 根) 根

	中序線索二叉樹	先序線索二叉樹	后序線索二叉樹
找前驅	?	?	?
找后繼	?	?	?