資料結構入門5-1（數和二叉樹）

目錄

注

樹和二叉樹的定義

樹的定義

樹的基本術語

二叉樹的定義

樹和二叉樹的抽象資料類型定義

二叉樹的性質和存儲結構

二叉樹的性質

二叉樹的存儲結構

1. 順序存儲結構

2. 鍊式存儲結構

周遊二叉樹和線索二叉樹

周遊二叉樹（traversing binary tree）

1. 算法描述

2. 根據周遊序列确定二叉樹

3. 二叉樹周遊算法的應用

線索二叉樹（Threaded Binary Tree）

1. 線索二叉樹的基本概念

2. 構造線索二叉樹

3. 周遊線索二叉樹

注

        本筆記主要參考《資料結構（C語言版）》

        樹結構是一種非常重要的非線性資料結構，這種層次結構以分支關系定義。樹結構非常常見，在作業系統、編譯系統或者資料庫中都有樹的身影。

樹和二叉樹的定義

樹的定義

        樹（tree）是 n（n ≥ 0）個結點的有限集，通過n，可以将樹歸為：① 空樹（n = 0）；② 非空樹（n ＞ 0）。

        而對于非空樹T：

例如：

        其中，對于（b）中一般的樹，可以認為：

        樹的結構定義是一個遞歸的定義，即在 樹的定義中 又用到了樹的定義。樹的表示方式有很多，譬如：

    之是以存在多種多樣的表示方式，說明了樹結構在日常生活及計算機程式設計中的重要性。

樹的基本術語

基本術語	解釋	例子
結點	樹中的一個獨立單元 （包含了一個資料元素和若幹指向其子樹的分支）	下圖中的A、B、C等。
結點的度	結點擁有的 子樹的數量 稱為結點的度	下圖中，A的度為3，C的度為1，F的度為0。
樹的度	樹的度是樹内 各結點的度 的最大值	下圖中，樹的度為3。
葉子	度為0的結點稱為 葉子 或 終端結點	下圖中，結點K、L、F、G、M、I、J都是樹的結點。
非終端結點	度不為0的結點被稱為 非終端結點 或 分支結點 （除根結點外，非終端結點又稱内部結點）

基本術語	解釋	例子
雙親、孩子	結點的 子樹的根 稱為該節點的孩子 （相應地，該結點稱為其孩子的雙親）	上圖中，B的雙親是A， B的孩子是E和F。
兄弟	同一個雙親的孩子之間互相稱為兄弟	上圖中，H、J和L互為兄弟。
祖先	從根到該結點 所經分支上的所有結點 都是該結點的祖先	上圖中，M的祖先是A、D和H。
子孫	以某結點為根的子樹，該子樹上的任一結點 都稱為該結點的子孫	上圖中，B的子孫是E、K、L和F。
堂兄弟	雙親在同一層 的結點互為堂兄弟	結點G和E、F、H、I、J互為堂兄弟。

基本術語	解釋	例子（說明）
層次	結點的層次 從根開始 定義	如上圖所示，樹中任一結點的層次等于其雙親結點的層次加1。
樹的深度	樹中結點的 最大層次 稱為樹的深度或高度	上圖中，樹的深度為4。
有序樹	如果樹中任意結點的子樹之間（從左到右）存在順序關系，稱該樹為有序樹	有序樹中：   第一個孩子：最左邊的子樹的根；   最後一個孩子：最右邊的子樹的根。
無序樹	樹中的任意結點的子樹之間不存在順序關系
森林	是m（m ≥ 0）棵互不相交的樹的集合 （對于樹中的每個結點而言，其子樹的集合就算森林）

    通過上述定義可知，可以用森林和樹互相遞歸的定義描述樹。 

         就邏輯結構而言，任何一顆樹都是一個二進制組 Tree = (root, F)，其中：

        當m ≠ 0時，樹根和其子樹森林之間存在下列關系：

二叉樹的定義

        二叉樹（Binary Tree）是n（n ≥ 0）個結點所構成的集合，它可以為空樹（n = 0），或者是非空樹。

        對于非空樹T：

        二叉樹和樹一樣，都具有遞歸的性質。而二者的差别主要展現在：

1. 二叉樹的每個結點至多有兩棵子樹（二叉樹中不存在度大于2的結點）；
2. 二叉樹的子樹有左右之分，次序不能任意颠倒。

        二叉樹的遞歸定義表明：二叉樹或為 空 ，或為 一個根結點加上兩棵互不相交的二叉樹（左子樹和右子樹）組成（兩棵子樹也可以是空樹）。

樹和二叉樹的抽象資料類型定義

    設A、B是集合，離散數學中的一些定義如下：

• A - B：是屬于集合的減法，它表明的是屬于A，但不屬于B的所有元素組成的集合；
• Ø：空集（也可通過Φ表示），即是指不含任何元素的集合；
• 劃分：若把集合A分成若幹個叫做分塊的非空子集，并且集合A中的任一進制素屬于并且僅屬于一個分塊，那麼把這些分塊構成的集合稱為劃分；
• 下述的R：簡單地說，是D中任意兩個元素之間的關系的集合（笛卡爾乘積）。

        樹的抽象資料類型定義：

        二叉樹的抽象資料類型定義：

二叉樹的性質和存儲結構

二叉樹的性質

        二叉樹具有三個重要的性質：

        另外，還存在兩種特殊形态的二叉樹，稱為 滿二叉樹 和 完全二叉樹 ：

---

        對于滿二叉樹而言：

    對二叉樹的結點進行編号，約定：編号從根結點開始，自上而下，從左到右。

        而對于完全二叉樹而言：

    可以把滿二叉樹看作是一種特殊的完全二叉樹。

        同時，完全二叉樹還具有兩個重要的特性：

二叉樹的存儲結構

        類似于線性表，二叉樹的存儲結構也可分為順序存儲和鍊式存儲兩種結構。

1. 順序存儲結構

//#define TElemType int	//自行定義TElemType的類型
//
#define MAXSIZE 100		//二叉樹的最大結點數
typedef TElemType SqBiTree[MAXSIZE];	//其中，下标為0的單元存儲根結點
SqBiTree bt;
           

        順序存儲結構通過一組位址連續的存儲單元來存儲資料元素，并且，為了能夠反映出存儲結構中的結點之間的邏輯關系，需要将二叉樹中的結點按照一定的規律安排到這組單元内：

• 完全二叉樹：從根處開始，按照層序進行存儲（即從上到下，從左到右存儲結點元素）。

  

• 一般的二叉樹：将其結點與對應深度的完全二叉樹上的結點相對照，存儲在一維數組的相應分量中。

  

    在最壞的情況下，一個深度為k且隻有k個結點的單支樹（數中不存在度為2的結點）卻需要長度遠超k的一維數組進行存儲。

        由此可知，順序存儲結構僅适用于完全二叉樹。一般二叉樹更适合鍊式存儲結構。

2. 鍊式存儲結構

        根據結點結構的不同，存在不同形式的鍊式存儲結構。

1. 二叉連結清單：連結清單的結點中包含了3個域，分别是資料域和左、右指針域。

   

   #define TElemType int
   
   typedef struct BiTNode {
   	TElemType data;						//結點的資料域
   	struct BiTNode* lchild, * rchild;	//結點的左、右孩子的指針域
   }BiTNode, * BiTree;
              

2. 三叉連結清單：相比于二叉連結清單，這種結點結構增加了一個指向雙親結點的指針域。

   

   （代碼實作參考二叉連結清單）

        對應于上述的結點結構，存在相應的存儲結構：

• 對于二叉連結清單而言：

  

          可以看出，在有n個結點的二叉連結清單中存在着 n+1 個空鍊域（這些空鍊域可以存儲其他有用資訊）。
•  對于三叉連結清單而言：

  

    在不同的層次結構中，實作二叉樹的操作方式也會有所不同。就比如 PARENT(T, e)（尋找結點x的雙親），在三叉連結清單中（因為有存儲雙親位址的指針域）可以輕松找到目标；而在二叉連結清單中則需要從根結點開始巡查。

    是以，在考慮二叉樹的存儲結構時，還應該考慮這個二叉樹将要進行何種操作。

周遊二叉樹和線索二叉樹

作用：

• 周遊二叉樹：①在樹中查找具有某種特征的結點，②對樹中的全部結點逐一進行處理；
• 線索二叉樹：在第一次周遊時記錄結點的前驅、後驅資訊，友善再次周遊。

周遊二叉樹（traversing binary tree）

1. 算法描述

        算法要實作的目标：按某條搜尋路徑巡防樹中的每個結點，使得每個結點均被通路，且僅被通路一次。

||| 通路的含義：對結點進行各種處理，包括 輸出結點的資訊 ，對結點進行運算和修改 等。

    周遊二叉樹是二叉樹中最基本的操作。

        周遊的實質是對二叉樹進行線性化的過程，周遊的結果是将 非線性結構（的樹）中的結點排成一個線性序列。為了實作這個目标，就需要尋找能夠排列二叉樹上的結點的規律。

        由于二叉樹是由3個基本單元組成的：根結、左子樹和右子樹。是以，如果要周遊整個二叉樹，就是要周遊這三個部分。現在假設：

• D：通路根結點；
• L：周遊左子樹；
• R：周遊右子樹。

        由上述假設可以得到6種周遊二叉樹的方案：DLR、DRL、LDR、LRD、RDL、RLD。在此之上，對周遊方案進行限制，要求周遊順序必須是先左後右，由此選出3種方案，根據周遊根結點的先後順序，命名得到：

操作	名稱	操作定義 （若二叉樹為空，進行空操作）
DLR	先（根）序周遊	1. 通路根結點； 2. 先序周遊左子樹； 3. 先序周遊右子樹。
LDR	中（根）序周遊	1. 中序周遊左子樹； 2. 通路根結點； 3. 中序周遊右子樹。
LRD	後（根）序周遊	1. 後序周遊左子樹； 2. 後序周遊右子樹； 3. 通路根結點。

例如，下方的二叉樹表示的是表達式 a + b * (c - d) - e / f：

• 若按先序周遊上述二叉樹，可得到該二叉樹的先序序列：

  

• 按中序周遊上述二叉樹，得到該二叉樹的中序序列：

  

• 按後序周遊上述二叉樹，得到該二叉樹的後序序列：

  

例子：中序算法

    約定：在該中序算法中，對于結點的通路即為資料的輸出。

【遞歸版本】

void InOrderTraverse(BiTree T)
{//中序周遊二叉樹T的遞歸算法
	if (T)				//若二叉樹非空
	{
		InOrderTraverse(T->lchild);		//中序周遊左子樹
		cout << T->data;				//通路根結點
		InOrderTraverse(T->rchild);		//中序周遊右子樹
	}
}
           

（ps：如果改變上述語句的先後順序，就可以實作先序和後序周遊的遞歸算法。）

        由上述代碼可知，3種周遊的不同僅在于通路次序的差異。是以，如果從遞歸的角度讨論先序、中序和後序周遊，會發現三者是完全相同的：

        現在要求通過中序周遊的方式周遊上述二叉樹，由代碼可得周遊的執行過程：

 【非遞歸版本（使用棧）】

        根據目前的知識，可以把上述的遞歸算法改為非遞歸算法：

void inordertraverse(BiTree T)
{//中序周遊二叉樹T的非遞歸算法（棧）
	SqStack S;
	InitStack(S);
	BiTree p = T;					//初始化p，用來指向二叉樹T的根結點
	BiTree q = new BiTNode;		    //申請一塊結點空間，用來存放棧頂彈出的元素

	while (p || !StackEmpty(S))		//p非空且棧非空
	{
		if (p)						//p非空
		{
			Push(S, p);				//根指針進棧
			p = p->lchild;			//周遊左子樹
		}
		else
		{
			Pop(S, q);				//退棧
			cout << q->data << " ";	//通路根結點
			p = q->rchild;			//周遊右子樹
		}
	}
	DestoryStack(S);
}
           

程式執行的結果如下：

【分析】

        在上述程式中，棧S的變化過程如下：

        在周遊二叉樹中，因為每個結點都被通路了一次，是以無論是遞歸還是非遞歸算法，其時間複雜度都是O(n)。而由上圖可知，輔助空間的大小就是樹的深度，是以，在最壞情況（樹的深度為n的情況）下，空間複雜度也是O(n)。

    之前提到過，除了前序、中序和後序外，還有一種按層次（從上到下，從左到右）周遊二叉樹的順序 —— 層序。在上述二叉樹中，如果使用層序周遊，得到的周遊序列是：-*cab。

（另外，層序周遊的算法可以通過隊列進行實作。）

2. 根據周遊序列确定二叉樹

        從之前的探讨中可以得出結論：若二叉樹的各結點的值均不同，則任意二叉樹結點的先序序列、中序序列和後序序列是唯一的。

        反過來，通過這個結論也可以得出一個推論：由二叉樹的先序序列和中序序列（或後序序列和中序序列）能唯一确定一棵二叉樹。

        上述推理過程确定了包括根結點在内的三個結點。而如果繼續拆分得到的兩個子序列，就可以繼續取得各個結點，最終就可以得到一棵二叉樹。

    同理，也可以由後序序列和中序序列确定唯一的一棵二叉樹（後序序列的最後一個結點就是目前的根結點）。

【例子】

        設存在一棵二叉樹，有：

• 中序序列：B D C E A F H G
• 後序序列：D E C B H G F A

        要求：畫出該二叉樹。

【分析】

1. 根據後序序列的特征（根結點必定在後序序列的尾部），可以确定該二叉樹的根結點為 A；
2. 由根結點A，将中序序列拆分為兩個子序列：

   

3.  将新獲得的子序列與後序序列進行元素比對，得到後序序列中的兩個子序列：

   

4.  繼而，可以得出：
   1. 在子樹DECB中，存在 B 為 A 的左孩子（即B為該子樹的根結點）；
   2. 在子樹FHG中，存在 F 為 A 的右孩子；
5. 由此，可以繼續對子樹進行拆分：

   

6. 通過這種方式類推，最終得到一棵二叉樹：

   

    由于無法區分左、右子樹，是以一棵二叉樹的先序序列和後序序列無法唯一确定一棵二叉樹。

3. 二叉樹周遊算法的應用

        作為二叉樹各種操作的基礎，“周遊” 會因為 通路結點 這一具體操作的不同而産生不同作用。譬如，假設 “通路” 能夠判别結點、計數或者生成結點等，就可以解決一些更加實際的問題。

【例子：建立二叉樹的存儲結構（二叉連結清單）】

        提示：為了建立二叉樹，需要在周遊過程中生成結點。并且約定

• 二叉樹中結點的元素均為一個單字元；
• 按先序周遊的順序建立二叉連結清單；
• T為指向根節點的指針。

【代碼】

void CreateBiTree(BiTree& T)
{//按先序次序輸入二叉樹中結點的值（一個字元），建立二叉連結清單表示的二叉樹T
	char ch;
	cin >> ch;
	
	if (ch == '#')			//遞歸結束，目前結點為空
		T = NULL;
	else					//遞歸，建立二叉樹
	{
		T = new BiTNode;	//生成目前結點
		T->data = ch;

		CreateBiTree(T->lchild);	//遞歸建立左子樹
		CreateBiTree(T->rchild);	//遞歸建立右子樹
	}
}
           

    由代碼邏輯可知，'#' 代表空結點。

譬如，執行程式，輸入 ABC##DE#G##F### ,可以建立二叉樹：

------

【例子：複制二叉樹】

        要求：複制已有的一棵二叉樹，得到與該二叉樹完全相同的另一棵二叉樹。

【代碼】

void Copy(BiTree T, BiTree& NewT)
{//複制一棵和T完全相同的二叉樹
	if (T == NULL)				//若為空結點，則目前遞歸結束
	{
		NewT = NULL;
		return;
	}
	else
	{
		NewT = new BiTNode;
		NewT->data = T->data;	//複制根結點
		Copy(T->lchild, NewT->lchild);		//遞歸複制右子樹
		Copy(T->rchild, NewT->rchild);		//遞歸複制左子樹
	}
}
           

【分析】

        複制二叉樹主要考慮兩種情況：

1. 若樹T目前結點為空，則NewT對應結點也為空；
2. 若樹T目前結點不為空，則NewT需要存在對應結點存儲資料。

        類似于周遊二叉樹，上述的算法也是進行按照先序進行，按照 ①根結點；②左子樹；③右子樹 的方式進行浏覽。

不推薦的非遞歸算法：

void Copy(BiTree T, BiTree& NewT)
{//中序周遊二叉樹T的非遞歸算法（棧）
	SqStack S;
	InitStack(S);
	BiTree p = T;
	BiTree q = new BiTNode;

	NewT = new BiTNode;
	BiTree r = NewT;
	BiTree s = new BiTNode;

	while (p || !StackEmpty(S))
	{
		if (p)						//若p非空
		{
			Push(S, p);				//根指針進棧
			p = p->lchild;			//周遊左子樹

			Push(S, r);				//将NewT的結點也入棧
			if (p)					//如果該層次是空，則不建立結點
				r->lchild = new BiTNode;
			r = r->lchild;
		}
		else
		{
			Pop(S, s);				//後進先出
			Pop(S, q);				//退棧
			s->data = q->data;
			p = q->rchild;			//周遊右子樹

			r = NULL;
			if (p)					//若右子樹為空，則不建立結點
				s->rchild = new BiTNode;
			r = s->rchild;
		}
	}
	DestoryStack(S);
}
           

    在周遊二叉樹的過程中，遞歸的層次 ≤ 樹的深度，也就是說，遞歸的層次是有限的。而在相同情況下，如果使用非遞歸算法，代碼不僅會顯得麻煩，并且會難以了解。

（ps：如果一定要使用非遞歸算法，可考慮使用兩個棧或者雙棧結構。）

------

【例子：計算二叉樹的深度】

        二叉樹的深度就是樹中結點的最大層次（即其左、右子樹深度的較大者加1）。

【代碼】

int Depth(BiTree T)
{//計算二叉樹T的深度
	if (T == NULL)
		return 0;
	else
	{
		int m = Depth(T->lchild);		//遞歸，計算左子樹的深度
		int n = Depth(T->rchild);		//遞歸，計算右子樹的深度

		if (m > n)                      //求出兩棵子樹深度的較大值
			return m + 1;
		else
			return n + 1;
	}
}
           

        該算法是建立在後序周遊二叉樹的算法基礎上的（先通路左子樹，再通路右子樹，最後考慮根結點）。

------

【例子：統計二叉樹中結點的個數】

結點個數 = 左子樹的結點個數 + 右子樹的結點個數 + 1（根結點）

int NodeCount(BiTree T)
{//統計二叉樹T中結點的個數
	if (T == NULL)			//若遇到空結點，則傳回0
		return 0;
	else					//結點個數通過公式計算得到
		return NodeCount(T->lchild) + NodeCount(T->rchild) + 1;
}
           

線索二叉樹（Threaded Binary Tree）

        從上述讨論可知，周遊二叉樹就是将二叉樹中的結點按照一定的規律進行排列，這實際上是對一個非線性結構進行的線性化操作。

        但是，在實際操作中也可以看到：當二叉連結清單作為存儲結構時，結點中隻存儲左、右孩子資訊，而結點在任一序列中的直接前驅和直接後驅是無法得到的。

    如：中序序列a+b*c，其中 “b” 的前驅是 “+” ，後驅是 “*” 。而這種資訊隻存在于周遊的動态過程中。

        很顯然，這在某些時候無法滿足程式的需要。

    當然，可以在 每個結點 中增加指針域來存儲有關前驅和後驅的資訊，但這樣做的代價就是結構的存儲密度的大幅降低。

        為此，就需要引入線索二叉樹的概念，通過它，可以儲存那些原本隻存在于動态過程中的前驅和後驅資訊。

1. 線索二叉樹的基本概念

||| 規定：

1. 若結點有左子樹，則：
   1. lchild域 将訓示其左孩子；
   2. 否則，令 lchild域 訓示其前驅。
2. 若結點有右子樹，則：
   1. rchild域 将訓示其右孩子；
   2. 否則，令 rchild域 訓示其後繼。

        如圖所示：

        二叉樹的二叉線索類型定義：

typedef struct BiThrNode
{
	TElemType data;
	struct BiThrNode* lchild, * rchild;		//左、右孩子指針
	int LTag, RTag;							//左、右标志
}BiThrNode, *BiThrTree;
           

        由此而産生的各種概念：

概念	内容
線索連結清單	存儲結構是 由上述這種結點結構構成的二叉連結清單
線索	上述結點結構中指向前驅和後驅的 指針
線索二叉樹	加上線索的二叉樹
線索化	對二叉樹以某種次序周遊，使其變為線索二叉樹的 過程

例如：下圖所示為一中序線索連結清單

        在上圖中：

• 虛線作為 線索 ，連接配接了前驅和後驅。
• 添加了頭結點，并且：
  • 頭結點的lchild域的指針指向根結點，rchild域的指針指向中序周遊時通路的最後一個結點；
  • 令二叉樹中序序列中的 ①第一個結點的lchild域指針，②最後一個結點的rchild域的指針 均指向頭結點。

2. 構造線索二叉樹

        線索二叉樹構造的實質：将二叉連結清單中的空指針改為指向其前驅或後驅的線索。

【代碼】

    其中 指針變量pre 是提前設定的全局變量，它始終是 p 的前驅。

① 不帶頭結點的版本

void InThreading(BiThrTree p)
{
	if (p)
	{
		InThreading(p->lchild);			//左子樹遞歸線索化

		if (!p->lchild)					//p的左孩子為空
		{
			p->LTag = 1;				//給p加上做線索
			p->lchild = pre;			//p的左孩子的指針指向前驅（pre）
		}
		else
			p->LTag = 0;

		if (!pre->rchild)				//pre的右孩子為空
		{
			pre->RTag = 1;				//給pre加上右線索
			pre->rchild = p;			//pre的右孩子的指針指向後繼（p）
		}
		else
			pre->RTag = 0;

		pre = p;						//移動pre，令pre始終都是p的前驅
		InThreading(p->rchild);			//右子樹遞歸線索化
	}
}
           

【注】

        在實際的操作中，若全局變量pre沒有被主動配置設定指向空間，它将預設為一個空指針（NULL）。為此，可以使用new進行動态記憶體配置設定；

        另外，在編寫代碼及測試中，在函數外部無法定義結構體的成員。若要進行測試，可以将結構體pre的變量定義放到主函數内。

---

② 帶頭結點的版本（需要使用上述的函數InThreading）

void InOrderThreading(BiThrTree& Thrt, BiThrTree T)
{//将二叉樹T中序線索化，令 THrt 指向頭結點
	Thrt = new BiThrNode;		//建立頭結點
	Thrt->LTag = 0;				//由上圖可知，頭結點有左孩子。若樹非空，其左孩子就是樹根
	Thrt->RTag = 1;				//存在右線索
	Thrt->rchild = Thrt;		//初始化時，右指針指向自己

	if (!T)
		Thrt->lchild = Thrt;	//若樹為空，則左指針也指向自己
	else
	{
		Thrt->lchild = T;		//頭結點的左孩子指向樹根
		pre = Thrt;				

		InThreading(T);			//調用函數InThreading，對二叉樹T進行中序線索化

		pre->rchild = Thrt;		//函數InThreading調用結束時，pre指向最右邊的結點
		pre->RTag = 1;
		Thrt->rchild = pre;		//頭結點的右線索指向pre
	}
}
           

    由于線索二叉樹擁有結點的前驅和後驅的資訊，是以相比于普通二叉樹的周遊，線索二叉樹的周遊及指定結點的查找都變得更加簡單。 

3. 周遊線索二叉樹

        一般地，如果需要經常查找結點的前驅和後繼，會選擇采用線索連結清單作為存儲結構。而在不同次序中，結點内部存儲位址的含義也會有所不同，為此需要進行分類讨論。

【分類讨論】

    下方所舉例子來源于上方的中序線索連結清單。

（1）在中序線索二叉樹中

• 查找指定結點的前驅：

p→LTag	含義
1	p的左指針域 訓示其前驅。
① p有左子樹； ② p所指結點的前驅是 周遊目前結點的左子樹時，通路的最後一個結點。（譬如：前圖中序連結清單中， '-' 的前驅就是 'd'）

• 查找指定結點的後繼：

p→RTag	含義
1	p的右指針域 訓示其後繼。
① p有右子樹； ② p所指結點的後繼是 周遊目前結點的右子樹時，通路的第一個結點。（譬如：前圖中序連結清單中，'-' 的後繼是 'e'）

------

（2）在先序線索二叉樹中：

• 查找指定結點的前驅：

p→LTag	含義
1	p的左指針域 訓示其前驅。
① p有左子樹； ② p的前驅有兩種情況：         ▪ 若目前結點是其雙親的左孩子，則該結點的前驅就是其雙親結點；         ▪ 否則，目前結點的前驅應是 周遊該結點的雙親的左子樹時，所通路的最後一個結點。

• 查找指定結點的後繼：

p→RTag	含義
1	p的右指針域 訓示其後繼。
① p有右子樹； ② 按照先序周遊的規則，p所指結點的後繼必為 目前結點的左子樹根（若存在）或右子樹根。

------

（3）在後序線索二叉樹中：

• 查找指定結點的前驅：

p→LTag	含義
1	p的左指針域 訓示其前驅。
① 若p→RTag為 0（右子樹存在），則p的右指針域 訓示其前驅； ② 若p→RTag為 1（右子樹不存在），則p的左指針域 訓示其前驅。

• 由于比較複雜，需要分類讨論指定結點的後繼情況：

p所指結點	後繼的情況
是二叉樹的根	其後繼為空。
是雙親的右孩子	其後繼為雙親結點。
1. 是雙親的左孩子 2. 沒有右兄弟	其後繼也是雙親結點。
1. 是雙親的左孩子 2. 有右兄弟	其後繼為 雙親的右子樹上按後繼周遊得到的第一個結點。

        在遇到上述這種查找後繼比較複雜的情況時，可以直接使用含4個指針的線索連結清單。

    由于結點内已經存在了前驅和後繼的資訊，線索二叉樹的周遊就不再需要設棧，是以在時間和空間上都比周遊二叉樹節省。接下來的算法就是通過 查找結點的後繼 進行線索二叉樹的周遊的。

【代碼：中序周遊線索二叉樹】

void InOrderTraverse_Thr(BiThrTree T)	
{//中序周遊線索二叉樹T的非遞歸算法，其中通路操作就是直接輸出
	BiThrNode* p = T->lchild;		//其中，T指向頭結點，故p指向根結點

	while (p != T)					//當T為空樹，或周遊結束時，p == T
	{
		while (p->LTag == 0)		//沿左孩子向下尋找
		{
			p = p->lchild;
		}
		cout << p->data;			//通路（輸出）左子樹為空的結點

		while (p->RTag == 1 && p->rchild != T)
		{
			p = p->rchild;			//通過右線索尋找後繼
			cout << p->data;		
		}
		p = p->rchild;				//轉向p的右子樹
	}
}
           

【分析】

• 時間複雜度：O(n);
• 空間複雜度：O(1)，因為上述操作未涉及任何堆棧。