5.樹和二叉樹

5.1樹和二叉樹的定義

樹形結(jié)構(gòu)（非線性結(jié)構(gòu)）：結(jié)點(diǎn)之間有分支，具有層次關(guān)系。

5.1.1樹的定義

樹（Tree）是n（n≥0）個(gè)結(jié)點(diǎn)的有限集。

• 若n=0，稱為空樹；
• 若n＞0，則它滿足如下兩個(gè)條件：
  1. 有且僅有一個(gè)特定的稱為根（Root）的結(jié)點(diǎn)；
  2. 其余結(jié)點(diǎn)可分為m（m≥0）個(gè)互不相交的有限集T1,T2,…Tm，其中每一個(gè)集合本身又是一棵樹，并稱為根的子樹（SubTree）。

**樹是n個(gè)結(jié)點(diǎn)的有限集。**顯然，樹的定義是一個(gè)遞歸的定義。

樹的其他表示形式：

5.1.2樹的基本術(shù)語(yǔ)

• **根結(jié)點(diǎn)：**非空樹中無(wú)前驅(qū)結(jié)點(diǎn)的結(jié)點(diǎn)。

• **結(jié)點(diǎn)的度：**結(jié)點(diǎn)擁有的子樹數(shù)。

• **樹的度：**樹內(nèi)各結(jié)點(diǎn)的度的最大值。

• **葉子結(jié)點(diǎn)：**度為0的點(diǎn)，也稱為終端結(jié)點(diǎn)。

• **分支結(jié)點(diǎn)：**度≠0的結(jié)點(diǎn)，也稱為非終端結(jié)點(diǎn)。

• **內(nèi)部結(jié)點(diǎn)：**根結(jié)點(diǎn)以外的分支結(jié)點(diǎn)稱為內(nèi)部結(jié)點(diǎn)。

• **雙親結(jié)點(diǎn)：**結(jié)點(diǎn)的子樹的根稱為該結(jié)點(diǎn)的孩子，該結(jié)點(diǎn)稱為孩子的雙親。

• **兄弟結(jié)點(diǎn)：**結(jié)點(diǎn)之前有共同的雙親結(jié)點(diǎn)稱為兄弟結(jié)點(diǎn)。

• **堂兄弟結(jié)點(diǎn)：**雙親在同一層的結(jié)點(diǎn)。

• **結(jié)點(diǎn)的祖先：**從根到該結(jié)點(diǎn)所經(jīng)分支上的所有結(jié)點(diǎn)。

• **結(jié)點(diǎn)的子孫：**以某結(jié)點(diǎn)為根的子樹中的任一結(jié)點(diǎn)。

• **樹的深度：**樹中結(jié)點(diǎn)的最大層次。

[外鏈圖片轉(zhuǎn)存失敗,源站可能有防盜鏈機(jī)制,建議將圖片保存下來(lái)直接上傳(img-XagGN3sY-1691068168684)(https://ts1.cn.mm.bing.net/th/id/R-C.fe38e3b271e2321ef483becbb761c23b?rik=2QonkZPTVvq%2btg&riu=http%3a%2f%2fpic.baike.soso.com%2fp%2f20131206%2f20131206141836-722390134.jpg&ehk=mNDvDkeq8qFKHHsXCLhiWhru8%2fGKWK1lU%2f3sEGzBvh4%3d&risl=&pid=ImgRaw&r=0&sres=1&sresct=1)]

有序樹：樹中結(jié)點(diǎn)的各子樹從左至右有次序（最左邊的為第一個(gè)孩子）。

**無(wú)序樹：**樹中結(jié)點(diǎn)的各子樹無(wú)次序。

**森林：**是m（m≥0）顆互不相交的樹的集合。把根結(jié)點(diǎn)刪除樹就變成了森林。

? 一棵樹可以看成是一個(gè)特殊的森林。

? 給森林中的各子樹加上一個(gè)雙親結(jié)點(diǎn)，森林就變成了樹。

樹一定是森林，但森林不一定是樹。

5.1.3樹結(jié)構(gòu)和線性結(jié)構(gòu)的比較

5.1.4二叉樹的定義

為什么要重點(diǎn)研究每結(jié)點(diǎn)最多只有兩個(gè)“叉”的樹？

• 二叉樹的機(jī)構(gòu)最簡(jiǎn)單，規(guī)律性最強(qiáng)；
• 可以證明，所有樹都能轉(zhuǎn)為唯一對(duì)應(yīng)的二叉樹，不失一般性。

普通樹（多叉樹）若不轉(zhuǎn)化為二叉樹，則運(yùn)算很難實(shí)現(xiàn)

? 二叉樹在樹結(jié)構(gòu)的應(yīng)用中起著非常重要的作用，因?yàn)閷?duì)二叉樹的許多操作算法簡(jiǎn)單，而任何樹都可以與二叉樹相互轉(zhuǎn)換，這樣就解決了樹的存儲(chǔ)結(jié)構(gòu)及其運(yùn)算中存在的復(fù)雜性。

二叉樹是n（n≥0）個(gè)結(jié)點(diǎn)的有限集，它或者是空集（n=0），或者由一個(gè)根結(jié)點(diǎn)及兩顆互不相交的分別稱作這個(gè)根的左子樹和右子樹的二叉樹組成。

特點(diǎn)：

1. 每個(gè)結(jié)點(diǎn)最多有兩孩子（二叉樹中不存在度大于2的結(jié)點(diǎn)）。
2. 子樹有左右之分，其次序不能顛倒。
3. 二叉樹可以是空集合，根可以有空的左子樹或空的右子樹

注意：二叉樹不是樹的特殊情況，它們是兩個(gè)概念。

? 二叉樹結(jié)點(diǎn)的子樹要區(qū)分左子樹和右子樹，即使只有一顆子樹也要進(jìn)行區(qū)分，說(shuō)明它是左子樹，還是右子樹。

? 樹當(dāng)結(jié)點(diǎn)只有一個(gè)孩子時(shí)，就無(wú)須區(qū)分他是左還是右的次序。因此，二者是不同的。這是二叉樹與樹的最主要的區(qū)別。

也就是二叉樹每個(gè)結(jié)點(diǎn)位置或者說(shuō)次序都是固定的，可以是空，但是不可以說(shuō)它沒(méi)有位置，而樹的結(jié)點(diǎn)位置是相對(duì)于別的結(jié)點(diǎn)來(lái)說(shuō)的，沒(méi)有別的結(jié)點(diǎn)時(shí)，它就無(wú)所謂左右了。

二叉樹的五種基本形態(tài)

注意：雖然二叉樹與樹概念不同，但有關(guān)樹的基本術(shù)語(yǔ)對(duì)二叉樹都適用。

5.2樹和二叉樹的類型定義

CreateBiTree（&T，definition）

? 初始條件：definition給出二叉樹T的定義。

? 操作結(jié)果：按definition構(gòu)造二叉樹T。

PreOrderTraverse（T）

? 初始條件：二叉樹T存在。

? 操作結(jié)果：先序遍歷T，對(duì)每個(gè)結(jié)點(diǎn)訪問(wèn)一次。

InOrderTraverse（T）

? 初始條件：二叉樹T存在。

? 操作結(jié)果：中序遍歷T，對(duì)每個(gè)結(jié)點(diǎn)訪問(wèn)一次。

POSTOrderTraverse（T）

? 初始條件：二叉樹T存在。

? 操作結(jié)果：后序遍歷T，對(duì)每個(gè)結(jié)點(diǎn)訪問(wèn)一次。

5.3二叉樹的性質(zhì)和存儲(chǔ)結(jié)構(gòu)

5.3.1二叉樹的性質(zhì)

• 性質(zhì)1：在二叉樹的第 i 層上至多有 2^i-1個(gè)結(jié)點(diǎn)（i≥1）。

  

• 性質(zhì)2：深度為 k 的二叉樹至多有2^k-1個(gè)結(jié)點(diǎn)（k≥1）。

  深度為k時(shí)至少有 k 個(gè)結(jié)點(diǎn)。

• 性質(zhì)3：對(duì)任何一顆二叉樹T，如果其葉子數(shù)為n₀，度為2的結(jié)點(diǎn)數(shù)為n₂，則 n₀=n₂+1。

  總邊數(shù)為B B = n - 1 或 B = n₂ * 2 + n₁ * 1

  總結(jié)點(diǎn)數(shù)為n n = n₂ * 2 + n₁ * 1 + 1 或者 n = n₂ + n₁ + n₀

5.3.2兩種特殊形式的二叉樹

1、滿二叉樹

一棵深度為 k 且有 2^k-1 個(gè)結(jié)點(diǎn)的二叉樹稱為滿二叉樹。

特點(diǎn)：

1. 每一層上的結(jié)點(diǎn)數(shù)都是最大結(jié)點(diǎn)數(shù)（即每層都滿）。
2. 葉子結(jié)點(diǎn)全部在最底層。

對(duì)滿二叉樹結(jié)點(diǎn)位置進(jìn)行編號(hào)

• 編號(hào)規(guī)則：從根結(jié)點(diǎn)開始，自上而下，自左而右。
• 每一結(jié)點(diǎn)位置都有元素。

滿二叉樹在同樣深度的二叉樹中結(jié)點(diǎn)個(gè)數(shù)最多。

滿二叉樹在同樣深度的二叉樹中葉子結(jié)點(diǎn)個(gè)數(shù)最多。

2、完全二叉樹

深度為k的具有n個(gè)結(jié)點(diǎn)的二叉樹，當(dāng)且僅當(dāng)其每一個(gè)結(jié)點(diǎn)都與深度為k的滿二叉樹中編號(hào)為1~n的結(jié)點(diǎn)——對(duì)應(yīng)時(shí)，稱之為完全二叉樹。

注意：在滿二叉樹中，從最后一個(gè)結(jié)點(diǎn)開始，連續(xù)去掉任意個(gè)結(jié)點(diǎn)，即是一顆完全二叉樹。

? 一定是連續(xù)的去掉?。?！

特點(diǎn)：

1. 葉子只可能分布在層次最大的兩層上。
2. 對(duì)任一結(jié)點(diǎn)，如果其右子樹的最大層次為i，則其左子樹的最大層次必為 i 或 i + 1。

滿二叉樹一定是完全二叉樹，完全二叉樹不一定滿二叉樹。

5.3.3完全二叉樹的性質(zhì)

• **性質(zhì)4：**具有 n 個(gè)結(jié)點(diǎn)的完全二叉樹的深度為 [log₂n] + 1。

  注意：[ x ]：稱作x的底，表示不大于x的最大整數(shù)。

  表明了完全二叉樹結(jié)點(diǎn)數(shù)n與完全二叉樹深度k之間的關(guān)系。

• 性質(zhì)5：如果對(duì)一棵有n個(gè)結(jié)點(diǎn)的完全二叉樹（深度為[ log₂n ]+1）的結(jié)點(diǎn)按層序編號(hào)（從第1層到第[log₂n]+1層，每層從左到右），則對(duì)任一結(jié)點(diǎn) i （1≤ i ≤ n）有：

  1. 如果 i =1，則結(jié)點(diǎn) i 是二叉樹的根，無(wú)雙親；如果 i ＞1，則其雙親是結(jié)點(diǎn) [i / 2]。
  2. 如果2i＞n，則結(jié)點(diǎn)i為葉子結(jié)點(diǎn)，無(wú)左孩子；否則，其左孩子是結(jié)點(diǎn)2i。
  3. 如果2i + 1＞n，則結(jié)點(diǎn)i無(wú)右孩子；否則，其右孩子是結(jié)點(diǎn) 2i +1。

  表明了完全二叉樹中雙親結(jié)點(diǎn)編號(hào)與孩子結(jié)點(diǎn)編號(hào)之間的關(guān)系。

5.3.4二叉樹的存儲(chǔ)結(jié)構(gòu)

二叉樹的存儲(chǔ)結(jié)構(gòu)分為順序存儲(chǔ)結(jié)構(gòu)以及鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)（二叉鏈表，三叉鏈表）。

1、二叉樹的順序存儲(chǔ)結(jié)構(gòu)

實(shí)現(xiàn)：按滿二叉樹的結(jié)點(diǎn)層次編號(hào)，依次存放二叉樹中的數(shù)據(jù)元素。

二叉樹順序存儲(chǔ)表示：

#define MAXSIZE 100
typedef int SqBiTree[MAXSIZE];
SqBiTree bt;

二叉樹的順序存儲(chǔ)缺點(diǎn)：

• **最壞情況：**深度為k的且只有k個(gè)結(jié)點(diǎn)的單支樹需要長(zhǎng)度為2^k-1的一維數(shù)組。

特點(diǎn)：

1. 結(jié)點(diǎn)間關(guān)系蘊(yùn)含在其存儲(chǔ)位置中
2. 浪費(fèi)空間，適于存滿二叉樹和完全二叉樹

2、二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

二叉鏈表存儲(chǔ)結(jié)構(gòu)：

typedef struct BiNode {
	int data;
	struct BiNode* lchild, * rchild;//左右孩子
}BiNode,*BiTree;

在n個(gè)結(jié)點(diǎn)的二叉鏈表，有__n+1__個(gè)空指針域。

分析：必有2n個(gè)鏈域。除根結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)有且僅有一個(gè)雙親，所以只會(huì)有 n-1 個(gè)結(jié)點(diǎn)的鏈域存放指針，指向非空子女結(jié)點(diǎn)。

空指針數(shù)目 = 2n -（n-1）=n+1

三叉鏈表

typedef struct TriTNode{
  int data;
  struct TriTNode *lichild,*parent,*rchild;
}TriTNode,*TriTree;

5.4遍歷二叉樹和線索二叉樹

5.4.1遍歷二叉樹

遍歷定義——順著某一條搜索路徑巡訪二叉樹中的結(jié)點(diǎn)，使得每個(gè)結(jié)點(diǎn)均被訪問(wèn)一次，而且僅被訪問(wèn)一次（又稱周游）。

• “訪問(wèn)”的含義很廣，可以是對(duì)結(jié)點(diǎn)做各種處理，如：輸出結(jié)點(diǎn)的信息，修改結(jié)點(diǎn)的數(shù)據(jù)值等，但要求這種訪問(wèn)不破壞原來(lái)的數(shù)據(jù)結(jié)構(gòu)。

遍歷目的——得到樹中所有結(jié)點(diǎn)的一個(gè)線性排列。

遍歷用途——它是樹結(jié)構(gòu)插入、刪除、修改、查找和排序運(yùn)算的前提，是二叉樹一切運(yùn)算的基礎(chǔ)和核心。

1、遍歷二叉樹算法描述

遍歷方法：依次遍歷二叉樹中的三個(gè)組成部分，便是遍歷了整個(gè)二叉樹。

則遍歷整個(gè)二叉樹方案共有：

ABC、ACB、BAC、BCA、CAB、CBA六種。

若規(guī)定先左后右，則只有前三種情況：

? ABC —— 先（根）序遍歷，

? BAC —— 中（根）序遍歷，

? BCA —— 后（根）序遍歷。

由二叉樹的遞歸定義可知，遍歷左子樹和遍歷右子樹可如同遍歷二叉樹一樣“遞歸”進(jìn)行。

2、根據(jù)遍歷序列確定二叉樹

• 若二叉樹中各結(jié)點(diǎn)的值均不相同，則二叉樹結(jié)點(diǎn)的先序序列，中序序列和后序序列都是唯一的。
• 由二叉樹的先序序列和中序序列，或由二叉樹的后序序列和中序序列可以確定唯一一棵二叉樹。

3、遍歷的算法思想

先序遍歷（根左右）

若二叉樹為空，則空操作；若二叉樹非空，

? 訪問(wèn)根結(jié)點(diǎn)（D）

? 前序遍歷左子樹（L）

? 前序遍歷右子樹（R）

bool PreOrderTraverse(BiTree T) {
	if (T == NULL) return true;//空二叉樹
	else {
		visit(T);//訪問(wèn)根結(jié)點(diǎn)
		PreOrderTraverse(T->lchild);//遞歸遍歷左子樹
		PreOrderTraverse(T->rchild);//遞歸遍歷右子樹
	}
}

void Pre(BiTree T) {
	if (T != NULL) {
		printf("%d\t", T->data);
		Pre(T->lchild);
		Pre(T->rchild);
	}
}

中序遍歷（左根右）

若二叉樹為空，則空操作；若二叉樹非空，

? 中序遍歷左子樹（L）

? 訪問(wèn)根結(jié)點(diǎn)（D）

? 中序遍歷右子樹（R）

bool InOrderTraverse(BiTree T) {
	if (T == NULL) return true;
	else {
		InOrderTraverse(T->lchild);//遞歸遍歷左子樹
		visit(T);//訪問(wèn)根結(jié)點(diǎn)
		InOrderTraverse(T->rchild);//遞歸遍歷右子樹
	}
}

后序遍歷（左右根）

若二叉樹為空，則空操作；若二叉樹非空，

? 后序遍歷左子樹（L）

? 后序遍歷右子樹（R）

? 訪問(wèn)根結(jié)點(diǎn)（D）

bool PostOrderTraverse(BiTree T) {
	if (T == NULL) return true;
	else {
		PostOrderTraverse(T->lchild);//遞歸遍歷左子樹
		PostOrderTraverse(T->rchild);//遞歸遍歷右子樹
		visit(T);//訪問(wèn)根結(jié)點(diǎn)
	}
}

遍歷算法的分析

如果去掉輸出語(yǔ)句，從遞歸的角度看，三種算法是完全相同的，或者說(shuō)這三種算法的訪問(wèn)路徑是相同的，只是訪問(wèn)結(jié)點(diǎn)的時(shí)機(jī)不同。

從虛線的出發(fā)點(diǎn)到終點(diǎn)的路徑上，每個(gè)結(jié)點(diǎn)都要經(jīng)過(guò) 3 次。

第一次經(jīng)過(guò)時(shí)訪問(wèn) = 先序遍歷

第二次經(jīng)過(guò)時(shí)訪問(wèn) = 中序遍歷

第三次經(jīng)過(guò)時(shí)訪問(wèn) = 后序遍歷

4、遍歷二叉樹的非遞歸算法

中序遍歷非遞歸算法

二叉樹中序遍歷的非遞歸算法的關(guān)鍵：在中序遍歷過(guò)某結(jié)點(diǎn)的整個(gè)左子樹后，如何找到該結(jié)點(diǎn)的根以及右子樹。

基本思想：

1. 建立一個(gè)棧；
2. 根結(jié)點(diǎn)進(jìn)棧，遍歷左子樹；
3. 根結(jié)點(diǎn)出棧，輸出根結(jié)點(diǎn)，遍歷右子樹

bool InOrderTraver(BiTree T) {
	BiTree p,q;
	SqStack S;
	InitStack(S);
	p = T;
	while (p||!StackEmpty(S))
	{
		if (p) {
			Push(S, p);
			p = p->lchild
		}
		else {
			Pop(S, q);
			printf("%c", q->data);
			p = q->rchild;
		}
	}
	return true;
}

二叉樹的層次遍歷

對(duì)于一顆二叉樹，從根結(jié)點(diǎn)開始，按從上到下，從左到右的順序訪問(wèn)每一個(gè)結(jié)點(diǎn)。每個(gè)結(jié)點(diǎn)僅僅訪問(wèn)一次。

**算法設(shè)計(jì)思路：**使用一個(gè)隊(duì)列

1. 將根結(jié)點(diǎn)進(jìn)隊(duì)；
2. 隊(duì)不空時(shí)循環(huán)：從隊(duì)列中出列一個(gè)結(jié)點(diǎn)*p，訪問(wèn)它；
   • 若它有左孩子結(jié)點(diǎn)，將左孩子結(jié)點(diǎn)進(jìn)隊(duì)；
   • 若它有右孩子結(jié)點(diǎn)，將右孩子結(jié)點(diǎn)進(jìn)隊(duì)。

使用隊(duì)列類型定義如下：

void LevelOrder(BTNode *b){
  BTNode *p;
  SqQueue *qu;
  InitQueue(qu);
  EnQueue(qu,b);//根結(jié)點(diǎn)指針進(jìn)入隊(duì)列
  while(!QueueEmpty(qu)){
    DeQueue(qu,p);//出隊(duì)結(jié)點(diǎn)p
    printf("%c",p->data);
    if(p->lchild!=NULL)
      enQueue(qu,p->lchild);//有左孩子時(shí)將其進(jìn)隊(duì)
    if(p->rchild!=NULL)
      enQueue(qu,p->rchild);//有右孩子時(shí)將其進(jìn)隊(duì)
  }
}

5.4.2二叉樹遍歷算法的應(yīng)用

1、二叉樹的建立

按先序遍歷序列建立二叉樹的二叉鏈表

例：已知先序序列為：ABCDEGF

（1）從鍵盤輸入二叉樹的結(jié)點(diǎn)信息，建立二叉樹的存儲(chǔ)結(jié)構(gòu)；

（2）在建立二叉樹的過(guò)程中按照二叉樹先序方式建立。

對(duì)于上圖所示二叉樹，按下列順序讀入字符：

ABC##DE#G##F###

bool CreatBiTree(BiTree& T) {
	char* ch;
	scanf("%c", & ch);
	if (ch == "#") T = NULL;
	else {
		if (!(T = (BiNode*)malloc(sizeof(BiNode))))
			return false;
		T->data = ch;//生成根結(jié)點(diǎn)
		CreatBiTree(T->lchild);//構(gòu)建左子樹
		CreatBiTree(T->rchild);//構(gòu)建右子樹
	}
	return true;
}

2、復(fù)制二叉樹

算法思想：

1. 如果是空樹，遞歸結(jié)束；
2. 否則，申請(qǐng)新結(jié)點(diǎn)空間，復(fù)制根節(jié)點(diǎn)
   • 遞歸復(fù)制左子樹
   • 遞歸復(fù)制右子樹

int Copy(BiTree T, BiTree& NewT) {
	if (T == NULL) {
		NewT = NULL;
		return 0;
	}
	else {
		NewT = new BiNode;
		NewT->data = T->data;
		Copy(T->lchild, NewT->lchild);
		Copy(T->rchild, NewT->rchild);
	}
}

3、計(jì)算二叉樹深度

• 如果是空樹，則深度為0；
• 否則，遞歸計(jì)算左子樹的深度記為m，遞歸計(jì)算右子樹的深度記為n，二叉樹的深度則為m與n的較大者加1。

int Depth(BiTree T) {
	if (T == NULL) return 0;//如果是空樹返回0
	else {
		int m = Depth(T->lchild);
		int n = Depth(T->rchild);
		if (m > n) return(m + 1);
		else return(n + 1);
	}
}

4、計(jì)算二叉樹結(jié)點(diǎn)總數(shù)

• 如果是空樹，則結(jié)點(diǎn)個(gè)數(shù)為0；
• 否則，結(jié)點(diǎn)個(gè)數(shù)為左子樹的結(jié)點(diǎn)個(gè)數(shù) + 右子樹的結(jié)點(diǎn)個(gè)數(shù)再 + 1

int NodeCount(BiTree T) {
	if (T == NULL)
		return 0;
	else
		return NodeCount(T->lchild) + NodeCount(T->rchild) + 1;
}

5、計(jì)算二叉樹葉子結(jié)點(diǎn)數(shù)

• 如果是空樹，則葉子結(jié)點(diǎn)個(gè)數(shù)為0；
• 否則，為左子樹的葉子結(jié)點(diǎn)個(gè)數(shù) + 右子樹的葉子結(jié)點(diǎn)個(gè)數(shù)。

int LeafCount(BiTree T) {
	if (T == NULL)
		return 0;//如果是空樹返回0
	if (T->lchild == NULL && T->rchild == NULL)
		return 1;//如果是葉子結(jié)點(diǎn)返回1
	else
		return LeafCount(T->lchild) + LeafCount(T->rchild);
}

5.4.3線索二叉樹

問(wèn)題：為什么要研究線索二叉樹？

? 當(dāng)用二叉鏈表作為二叉樹的存儲(chǔ)結(jié)構(gòu)時(shí)，可以很方便地找到某個(gè)結(jié)點(diǎn)的左右孩子；但一般情況下，無(wú)法直接找到該結(jié)點(diǎn)在某種遍歷序列中的前驅(qū)和后繼結(jié)點(diǎn)。

提出的問(wèn)題：如何尋找特定遍歷序列中二叉樹結(jié)點(diǎn)的前驅(qū)和后繼？

解決方法：

1. 通過(guò)遍歷尋找——費(fèi)時(shí)間
2. 再增設(shè)前驅(qū)、后繼指針域——增加了存儲(chǔ)負(fù)擔(dān)。
3. 利用二叉鏈表中的空指針域。

回顧：二叉樹鏈表中空指針域的數(shù)量：

• 具有n個(gè)結(jié)點(diǎn)的二叉鏈表中，一共有2n個(gè)指針域；因?yàn)閚個(gè)結(jié)點(diǎn)中有n-1個(gè)孩子，即2n個(gè)指針域中，有n-1個(gè)用來(lái)指示結(jié)點(diǎn)的左右孩子，其余n+1個(gè)指針域?yàn)榭?/strong>。

typedef struct BiThrNode {
	int data;
	int ltag, rtag;
	struct BiThrNode* lchild, * rchild;
}BiThrNode,*BiThrTree;

typedef struct PTNode{
  TElemType data;
  int parent;//雙親位置域
}PTNode;

#define MAXSIZE 100
typedef struct{
  PTNode nodes[MAXSIZE];
  int r,n;//根結(jié)點(diǎn)的位置和結(jié)點(diǎn)個(gè)數(shù)
}PTree;

typedef struct CTNode{
  int child;
  struct CTNode *next;
}*ChildPtr;

typedef struct{
  TElemType data;
  ChildPtr firstchild;//孩子鏈表頭指針
}CTBox;

typedef struct{
  CTBox nodes[MAXSIZE];
  int n,r;//結(jié)點(diǎn)數(shù)和根結(jié)點(diǎn)的位置
}CTree;

typedef struct CSNode{
  ElemType data;
  struct CSNode *firstchild,*nextsibling;
}CSNode,*CSTree;