二叉树经典.doc

二叉树一个简单的二叉树在计算机科学中，二叉树是每个节点最多有两个子树的有序树。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树常被用于实现二叉查找树和二叉堆。二叉树的每个结点至多只有二棵子树(不存在度大于2的结点)，二叉树的子树有左右之分，次序不能颠倒。二叉树的第i层至多有2i 1个结点；深度为k的二叉树至多有2k 1个结点；对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0 = n2 + 1。树和二叉树的三个主要差别：1. 树的结点个数至少为1，而二叉树的结点个数可以为0； 2. 树中结点的最大度数没有限制，而二叉树结点的最大度数为2； 3. 树的结点无左、右之分，而二叉树的结点有左、右之分。 目录 1 图论中的定义 2 二叉树(Binary Tree)的类型 3 存储二叉树的方法 o 3.1 顺序存储表示 3.1.1 存储结构 3.1.2 基本操作 o 3.2 二叉链表存储表示 3.2.1 存储结构 3.2.2 基本操作 o 3.3 三叉链表存储表示 3.3.1 存储结构 3.3.2 基本操作 4 访问二叉树的方法 o 4.1 前(先)序、中序、后序遍历 o 4.2 深度优先遍历 o 4.3 广度优先遍历 5 将n叉树转换为二叉树 o 5.1 存储结构与基本操作 5.1.1 树的二叉链表存储表示 5.1.2 树的二叉链表存储的基本操作 6 线索二叉树 (threaded binary tree) o 6.1 二叉线索存储表示 6.1.1 存储结构 6.1.2 基本操作 编辑 图论中的定义二叉树在图论中是这样定义的：二叉树是一个连通的无环图，并且每一个顶点的度不大于3。有根二叉树还要满足根结点的度不大于2。有了根结点之后，每个顶点定义了唯一的父结点，和最多2个子结点。然而，没有足够的信息来区分左结点和右结点。如果不考虑连通性，允许图中有多个连通分量，这样的结构叫做森林。编辑 二叉树(Binary Tree)的类型二叉树是一个有根树，并且每个节点最多有2个子节点。非空的二叉树，若树叶总数为 n0，分支度为2的总数为 n2，则 n0 = n2 + 1。一棵深度为k，且有2k 1个节点的二叉树，称为满二叉树（Full Binary Tree）。这种树的特点是每一层上的节点数都是最大节点数。在一棵二叉树中，除最后一层外，若其余层都是满的，并且最后一层或者是满的，或者是在右边缺少连续若干节点，则此二叉树为完全二叉树（Complete Binary Tree）。具有n个节点的完全二叉树的深度为log2n + 1。深度为k的完全二叉树，至少有2k 1个节点，至多有2k 1个节点。Complete Binary TreeFull Binary Tree总节点k2h 1 k 2h 1k = 2h 1树高hh = log2k + 1h = log2(k + 1)编辑 存储二叉树的方法在编程语言中能用多种方法来构造二叉树。在使用记录的编程语言中，二叉树通常用树结点结构来存储。有时也包含指向唯一的父节点的指针。如果一个结点的子结点个数小于2，一些子结点指针可能为空值，或者为特殊的哨兵结点。二叉树也可以用数组来存储，而且如果这是完全二叉树，这种方法不会浪费空间。用这种紧凑排列，如果一个结点的索引为i，它的子结点能在索引2i+1和2i+2找到，并且它的父节点（如果有）能在索引floor(i-1)/2)找到（假设根节点的索引为0）。这种方法更有利于紧凑存储和更好的访问的局部性，特别是在前序遍历中。然而，它需要连续的存储空间，这样在存储高度为h的n个结点组成的一般普通树时将会浪费很多空间。一种最极坏的情况下如果深度为h的二叉树每个节点只有右孩子需要占用2的h次幂减1，而实际却只有h个结点，空间的浪费太大，这是顺序存储结构的一大缺点。编辑 顺序存储表示编辑 存储结构 /* 二叉樹的順序存儲表示 */ #define MAX_TREE_SIZE 100 /* 二叉樹的最大結點數 */ typedef TElemType SqBiTreeMAX_TREE_SIZE; /* 0號單元存儲根結點 */ typedef struct int level,order; /* 結點的層,本層序號(按滿二叉樹計算) */ position;编辑 基本操作 /* 二叉树的顺序存储的基本操作(23个)*/ #define ClearBiTree InitBiTree /* 在順序存儲結構中，兩函數完全一樣 */ #define DestroyBiTree InitBiTree /* 在順序存儲結構中，兩函數完全一樣 */ void InitBiTree(SqBiTree T) /* 構造空二叉樹T。因為T是數組名，故不需要& */ int i; for(i=0;iMAX_TREE_SIZE;i+) Ti=Nil; /* 初值為空(Nil在主程中定義) */ void CreateBiTree(SqBiTree T) /* 按層序次序輸入二叉樹中結點的值(字符型或整型), 構造順序存儲的二叉樹T */ int i=0; #if CHAR /* 結點類型為字符 */ int l; char sMAX_TREE_SIZE; InitBiTree(T); /* 構造空二叉樹T */ printf(請按層序輸入結點的值(字符)，空格表示空結點，結點數%d:n,MAX_TREE_SIZE); gets(s); /* 輸入字符串 */ l=strlen(s); /* 求字符串的長度 */ for(;il;i+) /* 將字符串賦值給T */ Ti=si; #else /* 結點類型為整型 */ InitBiTree(T); /* 構造空二叉樹T */ printf(請按層序輸入結點的值(整型)，0表示空結點，輸999結束。結點數%d:n,MAX_TREE_SIZE); while(1) scanf(%d,&Ti); if(Ti=999) Ti=Nil; break; i+; #endif for(i=1;i=0;i-) /* 找到最後一個結點 */ if(Ti!=Nil) break; i+; /* 為了便於計算 */ do j+; while(i=pow(2,j); /*pow是原型為double pow( double x, double y ),計算x的y次方,h = log2k + 1來計算二叉樹的深度*/ return j; Status Root(SqBiTree T,TElemType *e) /* 初始條件：二叉樹T存在。操作結果：當T不空，用e返回T的根，返回OK；否則返回ERROR，e無定義 */ if(BiTreeEmpty(T) /* T空 */ return ERROR; else *e=T0; return OK; TElemType Value(SqBiTree T,position e) /* 初始條件：二叉樹T存在，e是T中某個結點(的位置) */ /* 操作結果：返回處於位置e(層,本層序號)的結點的值 */ return T(int)pow(2,e.level-1)+e.order-2; Status Assign(SqBiTree T,position e,TElemType value) /* 初始條件：二叉樹T存在，e是T中某個結點(的位置) */ /* 操作結果：給處於位置e(層,本層序號)的結點賦新值value */ int i=(int)pow(2,e.level-1)+e.order-2; /* 將層、本層序號轉為矩陣的序號 */ if(value!=Nil&T(i+1)/2-1=Nil) /* 給葉子賦非空值但雙親為空 */ return ERROR; else if(value=Nil&(Ti*2+1!=Nil|Ti*2+2!=Nil) /* 給雙親賦空值但有葉子(不空) */ return ERROR; Ti=value; return OK; TElemType Parent(SqBiTree T,TElemType e) /* 初始條件：二叉樹T存在，e是T中某個結點 */ /* 操作結果：若e是T的非根結點，則返回它的雙親，否則返回空 */ int i; if(T0=Nil) /* 空樹 */ return Nil; for(i=1;i=MAX_TREE_SIZE-1;i+) if(Ti=e) /* 找到e */ return T(i+1)/2-1; return Nil; /* 沒找到e */ TElemType LeftChild(SqBiTree T,TElemType e) /* 初始條件：二叉樹T存在，e是T中某個結點。操作結果：返回e的左孩子。若e無左孩子,則返回空 */ int i; if(T0=Nil) /* 空樹 */ return Nil; for(i=0;i=MAX_TREE_SIZE-1;i+) if(Ti=e) /* 找到e */ return Ti*2+1; return Nil; /* 沒找到e */ TElemType RightChild(SqBiTree T,TElemType e) /* 初始條件：二叉樹T存在，e是T中某個結點。操作結果：返回e的右孩子。若e無右孩子,則返回空 */ int i; if(T0=Nil) /* 空樹 */ return Nil; for(i=0;i=MAX_TREE_SIZE-1;i+) if(Ti=e) /* 找到e */ return Ti*2+2; return Nil; /* 沒找到e */ TElemType LeftSibling(SqBiTree T,TElemType e) /* 初始條件：二叉樹T存在，e是T中某個結點 */ /* 操作結果：返回e的左兄弟。若e是T的左孩子或無左兄弟，則返回空 */ int i; if(T0=Nil) /* 空樹 */ return Nil; for(i=1;i=MAX_TREE_SIZE-1;i+) if(Ti=e&i%2=0) /* 找到e且其序號為偶數(是右孩子) */ return Ti-1; return Nil; /* 沒找到e */ TElemType RightSibling(SqBiTree T,TElemType e) /* 初始條件：二叉樹T存在，e是T中某個結點 */ /* 操作結果：返回e的右兄弟。若e是T的右孩子或無右兄弟，則返回空 */ int i; if(T0=Nil) /* 空樹 */ return Nil; for(i=1;i=MAX_TREE_SIZE-1;i+) if(Ti=e&i%2) /* 找到e且其序號為奇數(是左孩子) */ return Ti+1; return Nil; /* 沒找到e */ void Move(SqBiTree q,int j,SqBiTree T,int i) /* InsertChild()用到。加 */ /* 把從q的j結點開始的子樹移為從T的i結點開始的子樹 */ if(q2*j+1!=Nil) /* q的左子樹不空 */ Move(q,(2*j+1),T,(2*i+1); /* 把q的j結點的左子樹移為T的i結點的左子樹 */ if(q2*j+2!=Nil) /* q的右子樹不空 */ Move(q,(2*j+2),T,(2*i+2); /* 把q的j結點的右子樹移為T的i結點的右子樹 */ Ti=qj; /* 把q的j結點移為T的i結點 */ qj=Nil; /* 把q的j結點置空 */ void InsertChild(SqBiTree T,TElemType p,int LR,SqBiTree c) /* 初始條件：二叉樹T存在，p是T中某個結點的值，LR為0或1，非空二叉樹c與T不相交且右子樹為空 */ /* 操作結果: 根據LR為0或1,插入c為T中p結點的左或右子樹。p結點的原有左或右子樹則成為c的右子樹 */ int j,k,i=0; for(j=0;j(int)pow(2,BiTreeDepth(T)-1;j+) /* 查找p的序號 */ if(Tj=p) /* j為p的序號 */ break; k=2*j+1+LR; /* k為p的左或右孩子的序號 */ if(Tk!=Nil) /* p原來的左或右孩子不空 */ Move(T,k,T,2*k+2); /* 把從T的k結點開始的子樹移為從k結點的右子樹開始的子樹 */ Move(c,i,T,k); /* 把從c的i結點開始的子樹移為從T的k結點開始的子樹 */ typedef int QElemType; /* 設隊列元素類型為整型(序號) */ #include c3-2.h /* 鏈隊列 */ #include bo3-2.c /* 鏈隊列的基本操作 */ Status DeleteChild(SqBiTree T,position p,int LR) /* 初始條件：二叉樹T存在，p指向T中某個結點，LR為1或0 */ /* 操作結果：根據LR為1或0，刪除T中p所指結點的左或右子樹 */ int i; Status k=OK; /* 隊列不空的標誌 */ LinkQueue q; InitQueue(&q); /* 初始化隊列，用於存放待刪除的結點 */ i=(int)pow(2,p.level-1)+p.order-2; /* 將層、本層序號轉為矩陣的序號 */ if(Ti=Nil) /* 此結點空 */ return ERROR; i=i*2+1+LR; /* 待刪除子樹的根結點在矩陣中的序號 */ while(k) if(T2*i+1!=Nil) /* 左結點不空 */ EnQueue(&q,2*i+1); /* 入隊左結點的序號 */ if(T2*i+2!=Nil) /* 右結點不空 */ EnQueue(&q,2*i+2); /* 入隊右結點的序號 */ Ti=Nil; /* 刪除此結點 */ k=DeQueue(&q,&i); /* 隊列不空 */ return OK; void(*VisitFunc)(TElemType); /* 函數變量 */ void PreTraverse(SqBiTree T,int e) /* PreOrderTraverse()調用 */ VisitFunc(Te); if(T2*e+1!=Nil) /* 左子樹不空 */ PreTraverse(T,2*e+1); if(T2*e+2!=Nil) /* 右子樹不空 */ PreTraverse(T,2*e+2); void PreOrderTraverse(SqBiTree T,void(*Visit)(TElemType) /* 初始條件：二叉樹存在，Visit是對結點操作的應用函數 */ /* 操作結果：先序遍歷T，對每個結點調用函數Visit一次且僅一次 */ VisitFunc=Visit; if(!BiTreeEmpty(T) /* 樹不空 */ PreTraverse(T,0); printf(n); void InTraverse(SqBiTree T,int e) /* InOrderTraverse()調用 */ if(T2*e+1!=Nil) /* 左子樹不空 */ InTraverse(T,2*e+1); VisitFunc(Te); if(T2*e+2!=Nil) /* 右子樹不空 */ InTraverse(T,2*e+2); void InOrderTraverse(SqBiTree T,void(*Visit)(TElemType) /* 初始條件：二叉樹存在，Visit是對結點操作的應用函數 */ /* 操作結果：中序遍歷T，對每個結點調用函數Visit一次且僅一次 */ VisitFunc=Visit; if(!BiTreeEmpty(T) /* 樹不空 */ InTraverse(T,0); printf(n); void PostTraverse(SqBiTree T,int e) /* PostOrderTraverse()調用 */ if(T2*e+1!=Nil) /* 左子樹不空 */ PostTraverse(T,2*e+1); if(T2*e+2!=Nil) /* 右子樹不空 */ PostTraverse(T,2*e+2); VisitFunc(Te); void PostOrderTraverse(SqBiTree T,void(*Visit)(TElemType) /* 初始條件：二叉樹T存在，Visit是對結點操作的應用函數 */ /* 操作結果：後序遍歷T，對每個結點調用函數Visit一次且僅一次 */ VisitFunc=Visit; if(!BiTreeEmpty(T) /* 樹不空 */ PostTraverse(T,0); printf(n); void LevelOrderTraverse(SqBiTree T,void(*Visit)(TElemType) /* 層序遍歷二叉樹 */ int i=MAX_TREE_SIZE-1,j; while(Ti=Nil) i-; /* 找到最後一個非空結點的序號 */ for(j=0;j=i;j+) /* 從根結點起，按層序遍歷二叉樹 */ if(Tj!=Nil) Visit(Tj); /* 只遍歷非空的結點 */ printf(n); void Print(SqBiTree T) /* 逐層、按本層序號輸出二叉樹 */ int j,k; position p; TElemType e; for(j=1;j=BiTreeDepth(T);j+) printf(第%d層: ,j); for(k=1;kdata=ch; CreateBiTree(&(*T)-lchild); /* 構造左子樹 */ CreateBiTree(&(*T)-rchild); /* 構造右子樹 */ Status BiTreeEmpty(BiTree T) /* 初始條件：二叉樹T存在。操作結果：若T為空二叉樹，則返回TRUE，否則FALSE */ if(T) return FALSE; else return TRUE; int BiTreeDepth(BiTree T) /* 初始條件：二叉樹T存在。操作結果：返回T的深度 */ int i,j; if(T=NULL) /*如果T=NULL,这样写便于理解，当然也可以写成if（!T）*/; return 0; /* 空樹深度為0 */ if(T-lchild) i=BiTreeDepth(T-lchild); /* i為左子樹的深度 */ else i=0; if(T-rchild) j=BiTreeDepth(T-rchild); /* j為右子樹的深度 */ else j=0; return ij?i+1:j+1; /* T的深度為其左右子樹的深度中的大者+1 */ TElemType Root(BiTree T) /* 初始條件：二叉樹T存在。操作結果：返回T的根 */ if(BiTreeEmpty(T) return Nil; else return T-data; TElemType Value(BiTree p) /* 初始條件：二叉樹T存在，p指向T中某個結點。操作結果：返回p所指結點的值 */ return p-data; void Assign(BiTree p,TElemType value) /* 給p所指結點賦值為value */ p-data=value; typedef BiTree QElemType; /* 設隊列元素為二叉樹的指針類型 */ #includec3-2.h /* 鏈隊列 */ #includebo3-2.c /* 鏈隊列的基本操作 */ TElemType Parent(BiTree T,TElemType e) /* 初始條件：二叉樹T存在，e是T中某個結點 */ /* 操作結果：若e是T的非根結點，則返回它的雙親，否則返回空*/ LinkQueue q; QElemType a; if(T) /* 非空樹 */ InitQueue(&q); /* 初始化隊列 */ EnQueue(&q,T); /* 樹根指針入隊 */ while(!QueueEmpty(q) /* 隊不空 */ DeQueue(&q,&a); /* 出隊，隊列元素賦給a */ if(a-lchild&a-lchild-data=e|a-rchild&a-rchild-data=e) /* 找到e(是其左或右孩子) */ return a-data; /* 返回e的雙親的值 */ else /* 沒找到e，則入隊其左右孩子指針(如果非空) */ if(a-lchild) EnQueue(&q,a-lchild); if(a-rchild) EnQueue(&q,a-rchild); return Nil; /* 樹空或沒找到e */ BiTree Point(BiTree T,TElemType s) /* 返回二叉樹T中指向元素值為s的結點的指針。另加 */ LinkQueue q; QElemType a; if(T) /* 非空樹 */ InitQueue(&q); /* 初始化隊列 */ EnQueue(&q,T); /* 根指針入隊 */ while(!QueueEmpty(q) /* 隊不空 */ DeQueue(&q,&a); /* 出隊，隊列元素賦給a */ if(a-data=s) return a; if(a-lchild) /* 有左孩子 */ EnQueue(&q,a-lchild); /* 入隊左孩子 */ if(a-rchild) /* 有右孩子 */ EnQueue(&q,a-rchild); /* 入隊右孩子 */ return NULL; TElemType LeftChild(BiTree T,TElemType e) /* 初始條件：二叉樹T存在，e是T中某個結點。操作結果：返回e的左孩子。若e無左孩子,則返回空 */ BiTree a; if(T) /* 非空樹 */ a=Point(T,e); /* a是結點e的指針 */ if(a&a-lchild) /* T中存在結點e且e存在左孩子 */ return a-lchild-data; /* 返回e的左孩子的值 */ return Nil; /* 其餘情況返回空 */ TElemType RightChild(BiTree T,TElemType e) /* 初始條件：二叉樹T存在，e是T中某個結點。操作結果：返回e的右孩子。若e無右孩子,則返回空 */ BiTree a; if(T) /* 非空樹 */ a=Point(T,e); /* a是結點e的指針 */ if(a&a-rchild) /* T中存在結點e且e存在右孩子 */ return a-rchild-data; /* 返回e的右孩子的值 */ return Nil; /* 其餘情況返回空 */ TElemType LeftSibling(BiTree T,TElemType e) /* 初始條件：二叉樹T存在，e是T中某個結點 */ /* 操作結果：返回e的左兄弟。若e是T的左孩子或無左兄弟，則返回空*/ TElemType a; BiTree p; if(T) /* 非空樹 */ a=Parent(T,e); /* a為e的雙親 */ if(a!=Nil) /* 找到e的雙親 */ p=Point(T,a); /* p為指向結點a的指針 */ if(p-lchild&p-rchild&p-rchild-data=e) /* p存在左右孩子且右孩子是e */ return p-lchild-data; /* 返回p的左孩子(e的左兄弟) */ return Nil; /* 其餘情況返回空 */ TElemType RightSibling(BiTree T,TElemType e) /* 初始條件：二叉樹T存在，e是T中某個結點 */ /* 操作結果：返回e的右兄弟。若e是T的右孩子或無右兄弟，則返回空*/ TElemType a; BiTree p; if(T) /* 非空樹 */ a=Parent(T,e); /* a為e的雙親 */ if(a!=Nil) /* 找到e的雙親 */ p=Point(T,a); /* p為指向結點a的指針 */ if(p-lchild&p-rchild&p-lchild-data=e) /* p存在左右孩子且左孩子是e */ return p-rchild-data; /* 返回p的右孩子(e的右兄弟) */ return Nil; /* 其餘情況返回空 */ Status InsertChild(BiTree p,int LR,BiTree c) /* 形參T無用 */ /* 初始條件：二叉樹T存在，p指向T中某個結點，LR為0或1，非空二叉樹c與T不相交且右子樹為空 */ /* 操作結果：根據LR為0或1，插入c為T中p所指結點的左或右子樹。p所指結點的 */ /* 原有左或右子樹則成為c的右子樹 */ if(p) /* p不空 */ if(LR=0) c-rchild=p-lchild; p-lchild=c; else /* LR=1 */ c-rchild=p-rchild; p-rchild=c; return OK; return ERROR; /* p空 */ Status DeleteChild(BiTree p,int LR) /* 形參T無用 */ /* 初始條件：二叉樹T存在，p指向T中某個結點，LR為0或1 */ /* 操作結果：根據LR為0或1，刪除T中p所指結點的左或右子樹 */ if(p) /* p不空 */ if(LR=0) /* 刪除左子樹 */ ClearBiTree(&p-lchild); else /* 刪除右子樹 */ ClearBiTree(&p-rchild); return OK; return ERROR; /* p空 */ typedef BiTree SElemType; /* 設棧元素為二叉樹的指針類型 */ #includec3-1.h /* 順序棧 */ #includebo3-1.c /* 順序棧的基本操作 */ void InOrderTraverse1(BiTree T,void(*Visit)(TElemType) /* 採用二叉鏈表存儲結構，Visit是對數據元素操作的應用函數。算法6.3，有改動 */ /* 中序遍歷二叉樹T的非遞歸算法(利用棧)，對每個數據元素調用函數Visit */ SqStack S; InitStack(&S); while(T|!StackEmpty(S) if(T) /* 根指針進棧，遍歷左子樹 */ Push(&S,T); T=T-lchild; else /* 根指針退棧，訪問根結點，遍歷右子樹 */ Pop(&S,&T); Visit(T-data); T=T-rchild; printf(n); void InOrderTraverse2(BiTree T,void(*Visit)(TElemType) /* 採用二叉鏈表存儲結構，Visit是對數據元素操作的應用函數。算法6.2，有改動 */ /* 中序遍歷二叉樹T的非遞歸算法(利用棧)，對每個數據元素調用函數Visit */ SqStack S; BiTree p; InitStack(&S); Push(&S,T); /* 根指針進棧 */ while(!StackEmpty(S) while(GetTop(S,&p)&p) Push(&S,p-lchild); /* 向左走到盡頭 */ Pop(&S,&p); /* 空指針退棧 */ if(!StackEmpty(S) /* 訪問結點，向右一步 */ Pop(&S,&p); Visit(p-data); Push(&S,p-rchild); printf(n); void PostOrderTraverse(BiTree T,void(*Visit)(TElemType) /* 初始條件：二叉樹T存在，Visit是對結點操作的應用函數 */ /* 操作結果：後序遞歸遍歷T，對每個結點調用函數Visit一次且僅一次 */ if(T) /* T不空 */ PostOrderTraverse(T-lchild,Visit); /* 先後序遍歷左子樹 */ PostOrderTraverse(T-rchild,Visit); /* 再後序遍歷右子樹 */ Visit(T-data); /* 最後訪問根結點 */ void LevelOrderTraverse(BiTree T,void(*Visit)(TElemType) /* 初始條件：二叉樹T存在，Visit是對結點操作的應用函數 */ /* 操作結果：層序遞歸遍歷T(利用隊列)，對每個結點調用函數Visit一次且僅一次 */ LinkQueue q; QElemType a; if(T) InitQueue(&q); /* 初始化隊列q */ EnQueue(&q,T); /* 根指針入隊 */ while(!QueueEmpty(q) /* 隊列不空 */ DeQueue(&q,&a); /* 出隊元素(指針),賦給a */ Visit(a-data); /* 訪問a所指結點 */ if(a-lchild!=NULL) /* a有左孩子 */ EnQueue(&q,a-lchild); /* 入隊a的左孩子 */ if(a-rchild!=NULL) /* a有右孩子 */ EnQueue(&q,a-rchild); /* 入隊a的右孩子 */ printf(n); 编辑 三叉链表存储表示编辑 存储结构 /* 二叉樹的三叉鏈表存儲表示 */ typedef struct BiTPNode TElemType data; struct BiTPNode *parent,*lchild,*rchild; /* 雙親、左右孩子指針 */ BiTPNode,*BiPTree;编辑 基本操作 /* 二叉樹的三叉鏈表存儲的基本操作(21個) */ #define ClearBiTree DestroyBiTree /* 清空二叉樹和銷毀二叉樹的操作一樣 */ void InitBiTree(BiPTree *T) /* 操作結果：構造空二叉樹T */ *T=NULL; void DestroyBiTree(BiPTree *T) /* 初始條件：二叉樹T存在。操作結果：銷毀二叉樹T */ if(*T) /* 非空樹 */ if(*T)-lchild) /* 有左孩子 */ DestroyBiTree(&(*T)-lchild); /* 銷毀左孩子子樹 */ if(*T)-rchild) /* 有右孩子 */ DestroyBiTree(&(*T)-rchild); /* 銷毀右孩子子樹 */ free(*T); /* 釋放根結點 */ *T=NULL; /* 空指針賦0 */ void CreateBiTree(BiPTree *T) /* 按先序次序輸入二叉樹中結點的值(可為字符型或整型，在主程中定義)，*/ /* 構造三叉鏈表表示的二叉樹T */ TElemType ch; scanf(form,&ch); if(ch=Nil) /* 空 */ *T=NULL; else *T=(BiPTree)malloc(sizeof(BiTPNode); /* 動態生成根結點 */ if(!*T) exit(OVERFLOW); (*T)-data=ch; /* 給根結點賦值 */ (*T)-parent=NULL; /* 根結點無雙親 */ CreateBiTree(&(*T)-lchild); /* 構造左子樹 */ if(*T)-lchild) /* 有左孩子 */ (*T)-lchild-parent=*T; /* 給左孩子的雙親域賦值 */ CreateBiTree(&(*T)-rchild); /* 構造右