[图论]中的定义

二叉树是一个连通的无环图，并且每一个顶点的度不大于3。有根二叉树还要满足根节点的度不大于2。有了根节点之后，每个顶点定义了唯一的父节点，和最多2个子节点。然而，没有足够的信息来区分左节点和右节点。如果不考虑连通性，允许图中有多个连通分量，这样的结构叫做森林。

二叉树(Binary Tree)的类型

二叉树是一个有根树，并且每个节点最多有2个子节点。非空的二叉树，若树叶总数为 n0，分支度为2的总数为 n2，则 n0 = n2 + 1。

一棵深度为k，且有 2 k − − --> 1 {\displaystyle 2^{\begin{aligned}k\end{aligned}}-1} 个节点的二叉树，称为满二叉树（Full Binary Tree）。这种树的特点是每一层上的节点数都是最大节点数。而在一棵二叉树中，除最后一层外，若其余层都是满的，并且最后一层或者是满的，或者是在右边缺少连续若干节点，则此二叉树为完全二叉树（Complete Binary Tree）。具有n个节点的完全二叉树的深度为 l o g 2 n + 1 {\displaystyle log_{2}n+1} 。深度为k的完全二叉树，至少有 2 k − − --> 1 {\displaystyle 2^{\begin{aligned}k-1\end{aligned}}} 个节点，至多有 2 k − − --> 1 {\displaystyle 2^{\begin{aligned}k\end{aligned}}-1} 个节点。

存储二叉树的方法

在程序设计语言中能用多种方法来构造二叉树。

顺序存储表示

二叉树可以用数组或链接串列来存储，若是满二叉树就能紧凑排列而不浪费空间。如果某个节点的索引为 i ，（假设根节点的索引为0）则在它左子节点的索引会是 2 i + 1 {\displaystyle 2i+1} ，以及右子节点会是 2 i + 2 {\displaystyle 2i+2} ；而它的父节点（如果有）索引则为 ⌊ i − − --> 1 2 ⌋ {\displaystyle \left\lfloor {\frac {i-1}{2}}\right\rfloor } 。这种方法更有利于紧凑存储和更好的访问的局部性，特别是在序遍历中。然而，它需要连续的存储空间，这样在存储高度为 h 的 n 个节点所组成的一般树时，将浪费很多空间。在最糟糕的情况下，如果深度为h的二叉树其每个节点都只有右孩子，则该存储结构需要占用 2 h − − --> 1 {\displaystyle 2^{h}-1} 的空间，实际上却只有h个节点，浪费了不少空间，是顺序存储结构的一大缺点。

存储结构

/* 二元樹的順序存儲表示 */#define MAX_TREE_SIZE 100 /* 二元樹的最大節點數 */typedefTElemTypeSqBiTree[MAX_TREE_SIZE];/* 0号单元存储根节点 */typedefstruct{intlevel,order;/* 節點的層，本層序號(按[[滿二元樹]]計算) */}position;

基本操作

基于C/C++的实现算法/* [[二元樹]]的順序存儲的基本操作(23個)*/#define ClearBiTree InitBiTree /* 在順序存儲結構中，兩函數完全一樣 */\arccos{}#define DestroyBiTree InitBiTree /* 在順序存儲結構中，兩函數完全一樣 */voidInitBiTree(SqBiTreeT)－－－（SqBiTree&T）{/* 構造[[空二元樹]]T。因為T是陣列名稱，故不需要& */inti;for(i=0;i<MAX_TREE_SIZE;i++)T[i]=Nil;/* 初值為空(Nil在主程中定義) */}voidCreateBiTree(SqBiTreeT){/* 按序次序輸入二叉樹中結點的值(字元型或整型), 構造順序存儲的二叉樹T */inti=0;#if CHAR /* 結點類型為字元 */intl;chars[MAX_TREE_SIZE];InitBiTree(T);/* 構造[空二元樹]T */printf("請按層序輸入結點的值(字元)，空格表示空結點，節點數≦%d:\n",MAX_TREE_SIZE);gets(s);/* 輸入字串 */l=strlen(s);/* 求字串的長度 */for(;i<l;i++)/* 將字串賦值給T */T[i]=s[i];#else /* 節點類型為整型 */InitBiTree(T);/* 構造[空二元樹]T */printf("請按層序輸入節點的值(整型)，0表示空節點，輸999結束。節點數≦%d:\n",MAX_TREE_SIZE);while(1){scanf("%d",&T[i]);if(T[i]==999){T[i]=Nil;break;}i++;}#endiffor(i=1;i=0;i--)/* 找到最後一個節點 */if(T[i]!=Nil)break;i++;/* 為了便於計算 */doj++;while(i>=pow(2,j));/*pow是原型為double pow( double x, double y ),計算x的y次方,h = log2k + 1來計算[二元樹]的深度*/returnj;}StatusRoot(SqBiTreeT,TElemType*e){/* 初始條件：[二元樹]T存在。操作結果：當T不空，用e返回T的根，返回OK；否則返回ERROR，e無定義 */if(BiTreeEmpty(T))/* T空 */returnERROR;else{*e=T[0];returnOK;}}TElemTypeValue(SqBiTreeT,positione){/* 初始條件：[二元樹]T存在，e是T中某個結點(的位置) *//* 操作結果：返回處於位置e(層,本層序號)的結點的值 */returnT[(int)pow(2,e.level-1)+e.order-2];}StatusAssign(SqBiTreeT,positione,TElemTypevalue){/* 初始條件：二叉樹T存在，e是T中某個結點(的位置) *//* 操作結果：給處於位置e(層,本層序號)的結點賦新值value */inti=(int)pow(2,e.level-1)+e.order-2;/* 將層、本層序號轉為矩陣的序號 */if(value!=Nil&&T[(i+1)/2-1]==Nil)/* 給葉子賦非空值但雙親為空 */returnERROR;elseif(value==Nil&&(T[i*2+1]!=Nil||T[i*2+2]!=Nil))/* 給雙親賦空值但有葉子(不空) */returnERROR;T[i]=value;returnOK;}TElemTypeParent(SqBiTreeT,TElemTypee){/* 初始條件：二叉樹T存在，e是T中某個結點 *//* 操作結果：若e是T的非根結點，則返回它的雙親，否則返回＂空＂ */inti;if(T[0]==Nil)/* 空樹 */returnNil;for(i=1;i<=MAX_TREE_SIZE-1;i++)if(T[i]==e)/* 找到e */returnT[(i+1)/2-1];returnNil;/* 沒找到e */}TElemTypeLeftChild(SqBiTreeT,TElemTypee){/* 初始條件：二叉樹T存在，e是T中某個結點。操作結果：返回e的左孩子。若e無左孩子,則返回"空" */inti;if(T[0]==Nil)/* 空樹 */returnNil;for(i=0;i<=MAX_TREE_SIZE-1;i++)if(T[i]==e)/* 找到e */returnT[i*2+1];returnNil;/* 沒找到e */}TElemTypeRightChild(SqBiTreeT,TElemTypee){/* 初始條件：二叉樹T存在，e是T中某個結點。操作結果：返回e的右孩子。若e無右孩子,則返回"空" */inti;if(T[0]==Nil)/* 空樹 */returnNil;for(i=0;i<=MAX_TREE_SIZE-1;i++)if(T[i]==e)/* 找到e */returnT[i*2+2];returnNil;/* 沒找到e */}TElemTypeLeftSibling(SqBiTreeT,TElemTypee){/* 初始條件：二叉樹T存在，e是T中某個結點 *//* 操作結果：返回e的左兄弟。若e是T的左孩子或無左兄弟，則返回＂空＂ */inti;if(T[0]==Nil)/* 空樹 */returnNil;for(i=1;i<=MAX_TREE_SIZE-1;i++)if(T[i]==e&&i%2==0)/* 找到e且其序號為偶數(是右孩子) */returnT[i-1];returnNil;/* 沒找到e */}TElemTypeRightSibling(SqBiTreeT,TElemTypee){/* 初始條件：二叉樹T存在，e是T中某個結點 *//* 操作結果：返回e的右兄弟。若e是T的右孩子或無右兄弟，則返回＂空＂ */inti;if(T[0]==Nil)/* 空樹 */returnNil;for(i=1;i<=MAX_TREE_SIZE-1;i++)if(T[i]==e&&i%2)/* 找到e且其序號為奇數(是左孩子) */returnT[i+1];returnNil;/* 沒找到e */}voidMove(SqBiTreeq,intj,SqBiTreeT,inti)/* InsertChild()用到。加 */{/* 把從q的j結點開始的子樹移為從T的i結點開始的子樹 */if(q[2*j+1]!=Nil)/* q的左子樹不空 */Move(q,(2*j+1),T,(2*i+1));/* 把q的j結點的左子樹移為T的i結點的左子樹 */if(q[2*j+2]!=Nil)/* q的右子樹不空 */Move(q,(2*j+2),T,(2*i+2));/* 把q的j結點的右子樹移為T的i結點的右子樹 */T[i]=q[j];/* 把q的j結點移為T的i結點 */q[j]=Nil;/* 把q的j結點置空 */}voidInsertChild(SqBiTreeT,TElemTypep,intLR,SqBiTreec){/* 初始條件：二叉樹T存在，p是T中某個結點的值，LR為0或1，非空二叉樹c與T不相交且右子樹為空 *//* 操作結果: 根據LR為0或1,插入c為T中p結點的左或右子樹。p結點的原有左或右子樹則成為c的右子樹 */intj,k,i=0;for(j=0;j<(int)pow(2,BiTreeDepth(T))-1;j++)/* 查找p的序號 */if(T[j]==p)/* j為p的序號 */break;k=2*j+1+LR;/* k為p的左或右孩子的序號 */if(T[k]!=Nil)/* p原來的左或右孩子不空 */Move(T,k,T,2*k+2);/* 把從T的k結點開始的子樹移為從k結點的右子樹開始的子樹 */Move(c,i,T,k);/* 把從c的i結點開始的子樹移為從T的k結點開始的子樹 */}typedefintQElemType;/* 設佇列元素類型為整型(序號) */#include"c3-2.h" /* 鏈佇列 */#include"bo3-2.c" /* 鏈佇列的基本操作 */StatusDeleteChild(SqBiTreeT,positionp,intLR){/* 初始條件：二叉樹T存在，p指向T中某個結點，LR為1或0 *//* 操作結果：根據LR為1或0，刪除T中p所指結點的左或右子樹 */inti;Statusk=OK;/* 佇列不空的標誌 */LinkQueueq;InitQueue(&q);/* 初始化佇列，用於存放待刪除的結點 */i=(int)pow(2,p.level-1)+p.order-2;/* 將層、本層序號轉為矩陣的序號 */if(T[i]==Nil)/* 此結點空 */returnERROR;i=i*2+1+LR;/* 待刪除子樹的根結點在矩陣中的序號 */while(k){if(T[2*i+1]!=Nil)/* 左結點不空 */EnQueue(&q,2*i+1);/* 入隊左結點的序號 */if(T[2*i+2]!=Nil)/* 右結點不空 */EnQueue(&q,2*i+2);/* 入隊右結點的序號 */T[i]=Nil;/* 刪除此結點 */k=DeQueue(&q,&i);/* 佇列不空 */}returnOK;}void(*VisitFunc)(TElemType);/* 函數變數 */voidPreTraverse(SqBiTreeT,inte){/* PreOrderTraverse()調用 */VisitFunc(T[e]);if(T[2*e+1]!=Nil)/* 左子樹不空 */PreTraverse(T,2*e+1);if(T[2*e+2]!=Nil)/* 右子樹不空 */PreTraverse(T,2*e+2);}voidPreOrderTraverse(SqBiTreeT,void(*Visit)(TElemType)){/* 初始條件：二叉樹存在，Visit是對結點操作的應用函數 *//* 操作結果：先序遍歷T，對每個結點調用函數Visit一次且僅一次 */VisitFunc=Visit;if(!BiTreeEmpty(T))/* 樹不空 */PreTraverse(T,0);printf("\n");}voidInTraverse(SqBiTreeT,inte){/* InOrderTraverse()調用 */if(T[2*e+1]!=Nil)/* 左子樹不空 */InTraverse(T,2*e+1);VisitFunc(T[e]);if(T[2*e+2]!=Nil)/* 右子樹不空 */InTraverse(T,2*e+2);}voidInOrderTraverse(SqBiTreeT,void(*Visit)(TElemType)){/* 初始條件：二叉樹存在，Visit是對結點操作的應用函數 *//* 操作結果：中序遍歷T，對每個結點調用函數Visit一次且僅一次 */VisitFunc=Visit;if(!BiTreeEmpty(T))/* 樹不空 */InTraverse(T,0);printf("\n");}voidPostTraverse(SqBiTreeT,inte){/* PostOrderTraverse()調用 */if(T[2*e+1]!=Nil)/* 左子樹不空 */PostTraverse(T,2*e+1);if(T[2*e+2]!=Nil)/* 右子樹不空 */PostTraverse(T,2*e+2);VisitFunc(T[e]);}voidPostOrderTraverse(SqBiTreeT,void(*Visit)(TElemType)){/* 初始條件：二叉樹T存在，Visit是對結點操作的應用函數 *//* 操作結果：後序遍歷T，對每個結點調用函數Visit一次且僅一次 */VisitFunc=Visit;if(!BiTreeEmpty(T))/* 樹不空 */PostTraverse(T,0);printf("\n");}voidLevelOrderTraverse(SqBiTreeT,void(*Visit)(TElemType)){/* 層序遍歷二叉樹 */inti=MAX_TREE_SIZE-1,j;while(T[i]==Nil)i--;/* 找到最後一個非空結點的序號 */for(j=0;j<=i;j++)/* 從根結點起，按層序遍歷二叉樹 */if(T[j]!=Nil)Visit(T[j]);/* 只遍歷非空的結點 */printf("\n");}voidPrint(SqBiTreeT){/* 逐層、按本層序號輸出二叉樹 */intj,k;positionp;TElemTypee;for(j=1;j<=BiTreeDepth(T);j++){printf("第%d層: ",j);for(k=1;k<=pow(2,j-1);k++){p.level=j;p.order=k;e=Value(T,p);if(e!=Nil)printf("%d:"form" ",k,e);}printf("\n");}}

二叉链表存储表示

  基于链表的二叉树逻辑结构示意

在使用记录或内存地址指针的程序设计语言中，二叉树通常用树结点结构来存储。有时也包含指向唯一的父节点的指针。如果一个结点的子结点个数小于2，一些子结点指针可能为空值，或者为特殊的哨兵结点。 使用链表能避免顺序存储浪费空间的问题，算法和结构相对简单，但使用二叉链表，由于缺乏父链的指引，在找回父节点时需要重新扫描树得知父节点的节点地址。

存储结构

/* 二叉樹的二叉鏈表存儲表示 */typedefstructBiTNode{TElemTypedata;structBiTNode*lchild,*rchild;/* 左右孩子指針 */}BiTNode,*BiTree;

基本操作

基于C/C++的实现算法/* 二叉樹的二叉鏈表存儲的基本操作(22個) */#define ClearBiTree DestroyBiTree /* 清空二叉樹和銷毀二叉樹的操作一樣 */#include"func6-3.c"/* 包括InitBiTree()、DestroyBiTree()、PreOrderTraverse()和InOrderTraverse()4函數 */voidCreateBiTree(BiTree*T){/* 演算法6.4：按先序次序輸入二叉樹中結點的值(可為字元型或整型，在主程中定義)，*//* 構造二叉鏈表表示的二叉樹T。變數Nil表示空(子)樹。有改動 */TElemTypech;scanf(form,&ch);if(ch==Nil)/* 空 */*T=NULL;else{*T=(BiTree)malloc(sizeof(BiTNode));/* 生成根結點 */if(!*T)exit(OVERFLOW);(*T)->data=ch;CreateBiTree(&(*T)->lchild);/* 構造左子樹 */CreateBiTree(&(*T)->rchild);/* 構造右子樹 */}}StatusBiTreeEmpty(BiTreeT){/* 初始條件：二叉樹T存在。操作結果：若T為空二叉樹，則返回TRUE，否則FALSE */if(T)returnFALSE;elsereturnTRUE;}intBiTreeDepth(BiTreeT){/* 初始條件：二叉樹T存在。操作結果：返回T的深度 */inti,j;if(T==NULL)/*如果T=NULL,这样写便于理解，当然也可以写成if（!T）*/;return0;/* 空樹深度為0 */if(T->lchild)i=BiTreeDepth(T->lchild);/* i為左子樹的深度 */elsei=0;if(T->rchild)j=BiTreeDepth(T->rchild);/* j為右子的深度 */elsej=0;returni>j?i+1:j+1;/* T的深度為其左右子樹的深度中的大者+1 */}TElemTypeRoot(BiTreeT){/* 初始條件：二叉樹T存在。操作結果：返回T的根 */if(BiTreeEmpty(T))returnNil;elsereturnT->data;}TElemTypeValue(BiTreep){/* 初始條件：二叉樹T存在，p指向T中某個結點。操作結果：返回p所指結點的值 */returnp->data;}voidAssign(BiTreep,TElemTypevalue){/* 給p所指結點賦值為value */p->data=value;}typedefBiTreeQElemType;/* 設佇列元素為二叉樹的指針類型 */#include"c3-2.h" /* 鏈佇列 */#include"bo3-2.c" /* 鏈佇列的基本操作 */TElemTypeParent(BiTreeT,TElemTypee){/* 初始條件：二叉樹T存在，e是T中某個結點 *//* 操作結果：若e是T的非根結點，則返回它的雙親，否則返回＂空＂*/LinkQueueq;QElemTypea;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(是其左或右孩子) */returna->data;/* 返回e的雙親的值 */else/* 沒找到e，則入隊其左右孩子指針(如果非空) */{if(a->lchild)EnQueue(&q,a->lchild);if(a->rchild)EnQueue(&q,a->rchild);}}}returnNil;/* 樹空或沒找到e */}BiTreePoint(BiTreeT,TElemTypes){/* 返回二叉樹T中指向元素值為s的結點的指標。另加 */LinkQueueq;QElemTypea;if(T)/* 非空樹 */{InitQueue(&q);/* 初始化佇列 */EnQueue(&q,T);/* 根指針入隊 */while(!QueueEmpty(q))/* 隊不空 */{DeQueue(&q,&a);/* 出隊，佇列元素賦給a */if(a->data==s)returna;if(a->lchild)/* 有左孩子 */EnQueue(&q,a->lchild);/* 入隊左孩子 */if(a->rchild)/* 有右孩子 */EnQueue(&q,a->rchild);/* 入隊右孩子 */}}returnNULL;}TElemTypeLeftChild(BiTreeT,TElemTypee){/* 初始條件：二叉樹T存在，e是T中某個結點。操作結果：返回e的左孩子。若e無左孩子,則返回"空" */BiTreea;if(T)/* 非空樹 */{a=Point(T,e);/* a是結點e的指針 */if(a&&a->lchild)/* T中存在結點e且e存在左孩子 */returna->lchild->data;/* 返回e的左孩子的值 */}returnNil;/* 其餘情況返回空 */}TElemTypeRightChild(BiTreeT,TElemTypee){/* 初始條件：二叉樹T存在，e是T中某個結點。操作結果：返回e的右孩子。若e無右孩子,則返回"空" */BiTreea;if(T)/* 非空樹 */{a=Point(T,e);/* a是結點e的指針 */if(a&&a->rchild)/* T中存在結點e且e存在右孩子 */returna->rchild->data;/* 返回e的右孩子的值 */}returnNil;/* 其餘情況返回空 */}TElemTypeLeftSibling(BiTreeT,TElemTypee){/* 初始條件：二叉樹T存在，e是T中某個結點 *//* 操作結果：返回e的左兄弟。若e是T的左孩子或無左兄弟，則返回＂空＂*/TElemTypea;BiTreep;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 */returnp->lchild->data;/* 返回p的左孩子(e的左兄弟) */}}returnNil;/* 其餘情況返回空 */}TElemTypeRightSibling(BiTreeT,TElemTypee){/* 初始條件：二叉樹T存在，e是T中某個結點 *//* 操作結果：返回e的右兄弟。若e是T的右孩子或無右兄弟，則返回＂空＂*/TElemTypea;BiTreep;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 */returnp->rchild->data;/* 返回p的右孩子(e的右兄弟) */}}returnNil;/* 其餘情況返回空 */}StatusInsertChild(BiTreep,intLR,BiTreec)/* 形參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;}returnOK;}returnERROR;/* p空 */}StatusDeleteChild(BiTreep,intLR)/* 形參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);returnOK;}returnERROR;/* p空 */}typedefBiTreeSElemType;/* 設棧元素為二叉樹的指針類型 */#include"c3-1.h" /* 順序棧 */#include"bo3-1.c" /* 順序棧的基本操作 */voidInOrderTraverse1(BiTreeT,void(*Visit)(TElemType)){/* 採用二叉鏈表存儲結構，Visit是對資料元素操作的應用函數。演算法6.3，有改動 *//* 中序遍歷二叉樹T的非遞迴演算法(利用棧)，對每個資料元素調用函數Visit */SqStackS;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");}voidInOrderTraverse2(BiTreeT,void(*Visit)(TElemType)){/* 採用二叉鏈表存儲結構，Visit是對資料元素操作的應用函數。演算法6.2，有改動 *//* 中序遍歷二叉樹T的非遞迴演算法(利用棧)，對每個資料元素用函數Visit */SqStackS;BiTreep;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");}voidPostOrderTraverse(BiTreeT,void(*Visit)(TElemType)){/* 初始條件：二叉樹T存在，Visit是對結點操作的應用函數 *//* 操作結果：後序遞迴遍歷T，對每個結點調用函數Visit一次且僅一次 */if(T)/* T不空 */{PostOrderTraverse(T->lchild,Visit);/* 先後序遍歷左子樹 */PostOrderTraverse(T->rchild,Visit);/* 再後序遍歷右子樹 */Visit(T->data);/* 最後訪問根結點 */}}voidLevelOrderTraverse(BiTreeT,void(*Visit)(TElemType)){/* 初始條件：二叉樹T存在，Visit是對結點操作的應用函數 *//* 操作結果：層序遞迴遍歷T(利用佇列)，對每個結點調用函數Visit一次且僅一次 */LinkQueueq;QElemTypea;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");}}

三叉链表存储表示

改进于二叉链表，增加父节点的指引，能更好地实现节点间的访问，不过算法相对复杂。 当二叉树用三叉链表表示时，有N个结点，就会有N+2个空指针。

存储结构

/* 二叉樹的三叉鏈表存儲表示 */typedefstructBiTPNode{TElemTypedata;structBiTPNode*parent,*lchild,*rchild;/* 父、左右孩子指針 */}BiTPNode,*BiPTree;

基本操作

基于C/C++的实现算法/* 二叉樹的三叉鏈表存儲的基本操作(21個) */#define ClearBiTree DestroyBiTree /* 清空二叉樹和銷毀二叉樹的操作一樣 */voidInitBiTree(BiPTree*T){/* 操作結果：構造空二叉樹T */*T=NULL;}voidDestroyBiTree(BiPTree*T){/* 初始條件：二叉樹T存在。操作結果：銷毀二叉樹T */if(*T)/* 非空樹 */{if((*T)->lchild)/* 有左孩子 */DestroyBiTree(&(*T)->lchild);/* 銷毀左孩子子樹 */if((*T)->rchild)/* 有右孩子 */DestroyBiTree(&(*T)->rchild);/* 銷毀右孩子子樹 */free(*T);/* 釋放根結點 */*T=NULL;/* 空指針賦0 */}}voidCreateBiTree(BiPTree*T){/* 按先序次序輸入二叉樹中結點的值(可為字元型或整型，在主程中定義)，*//* 構造三叉鏈表表示的二叉樹T */TElemTypech;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);/* 構造右子樹 */if((*T)->rchild)/* 有右孩子 */(*T)->rchild->parent=*T;/* 給右孩子的雙親域賦值 */}}StatusBiTreeEmpty(BiPTreeT){/* 初始條件：二叉樹T存在。操作結果：若T為空二叉樹，則返回TRUE，否則FALSE */if(T)returnFALSE;elsereturnTRUE;}intBiTreeDepth(BiPTreeT){/* 初始條件：二叉樹T存在。操作結果：返回T的深度 */inti,j;if(!T)return0;/* 空樹深度為0 */if(T->lchild)i=BiTreeDepth(T->lchild);/* i為左子樹的深度 */elsei=0;if(T->rchild)j=BiTreeDepth(T->rchild);/* j為右子樹的深度 */elsej=0;returni>j?i+1:j+1;/* T的深度為其左右子樹的深度中的大者+1 */}TElemTypeRoot(BiPTreeT){/* 初始條件：二叉樹T存在。操作結果：返回T的根 */if(T)returnT->data;elsereturnNil;}TElemTypeValue(BiPTreep){/* 初始條件：二叉樹T存在，p指向T中某個結點。操作結果：返回p所指結點的值 */returnp->data;}voidAssign(BiPTreep,TElemTypevalue){/* 給p所指結點賦值為value */p->data=value;}typedefBiPTreeQElemType;/* 設佇列元素為二叉樹的指針類型 */#include"c3-2.h" /* 鏈佇列 */#include"bo3-2.c" /* 鏈佇列的基本操作 */BiPTreePoint(BiPTreeT,TElemTypee){/* 返回二叉樹T中指向元素值為e的結點的指標。加 */LinkQueueq;QElemTypea;if(T)/* 非空樹 */{InitQueue(&q);/* 初始化佇列 */EnQueue(&q,T);/* 根結點入隊 */while(!QueueEmpty(q))/* 隊不空 */{DeQueue(&q,&a);/* 出隊，佇列元素賦給a */if(a->data==e)returna;if(a->lchild)/* 有左孩子 */EnQueue(&q,a->lchild);/* 入隊左孩子 */if(a->rchild)/* 有右孩子 */EnQueue(&q,a->rchild);/* 入隊右孩子 */}}returnNULL;}TElemTypeParent(BiPTreeT,TElemTypee){/* 初始條件：二叉樹T存在，e是T中某個結點 *//* 操作結果：若e是T的非根結點，則返回它的雙親，否則返回＂空＂*/BiPTreea;if(T)/* 非空樹 */{a=Point(T,e);/* a是結點e的指針 */if(a&&a!=T)/* T中存在結點e且e是非根結點 */returna->parent->data;/* 返回e的雙親的值 */}returnNil;/* 其餘情況返回空 */}TElemTypeLeftChild(BiPTreeT,TElemTypee){/* 初始條件：二叉樹T存在，e是T中某個結點。操作結果：返回e的左孩子。若e無左孩子,則返回"空" */BiPTreea;if(T)/* 非空樹 */{a=Point(T,e);/* a是結點e的指針 */if(a&&a->lchild)/* T中存在結點e且e存在左孩子 */returna->lchild->data;/* 返回e的左孩子的值 */}returnNil;/* 其餘情況返回空 */}TElemTypeRightChild(BiPTreeT,TElemTypee){/* 初始條件：二叉樹T存在，e是T中某個結點。操作結果：返回e的右孩子。若e無右孩子,則返回"空" */BiPTreea;if(T)/* 非空樹 */{a=Point(T,e);/* a是結點e的指針 */if(a&&a->rchild)/* T中存在結點e且e存在右孩子 */returna->rchild->data;/* 返回e的右孩子的值 */}returnNil;/* 其餘情況返回空 */}TElemTypeLeftSibling(BiPTreeT,TElemTypee){/* 初始條件：二叉樹T存在，e是T中某個結點 *//* 操作結果：返回e的左兄弟。若e是T的左孩子或無左兄弟，則返回＂空＂*/BiPTreea;if(T)/* 非空樹 */{a=Point(T,e);/* a是結點e的指針 */if(a&&a!=T&&a->parent->lchild&&a->parent->lchild!=a)/* T中存在結點e且e存在左兄弟 */returna->parent->lchild->data;/* 返回e的左兄弟的值 */}returnNil;/* 其餘情況返回空 */}TElemTypeRightSibling(BiPTreeT,TElemTypee){/* 初始條件：二叉樹T存在，e是T中某個結點 *//* 操作結果：返回e的右兄弟。若e是T的右孩子或無右兄弟，則返回＂空＂*/BiPTreea;if(T)/* 非空樹 */{a=Point(T,e);/* a是結點e的指針 */if(a&&a!=T&&a->parent->rchild&&a->parent->rchild!=a)/* T中存在結點e且e存在右兄弟 */returna->parent->rchild->data;/* 返回e的右兄弟的值 */}returnNil;/* 其餘情況返回空 */}StatusInsertChild(BiPTreep,intLR,BiPTreec)/* 形參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;if(c->rchild)/* c有右孩子(p原有左孩子) */c->rchild->parent=c;p->lchild=c;c->parent=p;}else/* LR==1 */{c->rchild=p->rchild;if(c->rchild)/* c有右孩子(p原有右孩子) */c->rchild->parent=c;p->rchild=c;c->parent=p;}returnOK;}returnERROR;/* p空 */}StatusDeleteChild(BiPTreep,intLR)/* 形參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);returnOK;}returnERROR;/* p空 */}voidPreOrderTraverse(BiPTreeT,void(*Visit)(BiPTree)){/* 先序遞迴遍歷二叉樹T */if(T){Visit(T);/* 先訪問根結點 */PreOrderTraverse(T->lchild,Visit);/* 再先序遍歷左子樹 */PreOrderTraverse(T->rchild,Visit);/* 最後先序遍歷右子樹 */}}voidInOrderTraverse(BiPTreeT,void(*Visit)(BiPTree)){/* 中序遞迴遍歷二叉樹T */if(T){InOrderTraverse(T->lchild,Visit);/* 中序遍歷左子樹 */Visit(T);/* 再訪問根結點 */InOrderTraverse(T->rchild,Visit);/* 最後中序遍歷右子樹 */}}voidPostOrderTraverse(BiPTreeT,void(*Visit)(BiPTree)){/* 後序遞迴遍歷二叉樹T */if(T){PostOrderTraverse(T->lchild,Visit);/* 後序遍歷左子樹 */PostOrderTraverse(T->rchild,Visit);/* 後序遍歷右子樹 */Visit(T);/* 最後訪問根結點 */}}voidLevelOrderTraverse(BiPTreeT,void(*Visit)(BiPTree)){/* 層序遍歷二叉樹T(利用佇列) */LinkQueueq;QElemTypea;if(T){InitQueue(&q);EnQueue(&q,T);while(!QueueEmpty(q)){DeQueue(&q,&a);Visit(a);if(a->lchild!=NULL)EnQueue(&q,a->lchild);if(a->rchild!=NULL)EnQueue(&q,a->rchild);}}} 

访问二叉树的方法

我们经常希望访问树中的每一个结点并且查看它的值。有很多常见的顺序来访问所有的结点，而且每一种都有有用的性质。

前(先)序、中序、后序遍历

遍历二叉树：L、D、R分别表示遍历左子树、访问根结点和遍历右子树，则先(根)序遍历二叉树的顺序是DLR，中(根)序遍历二叉树的顺序是LDR，后(根)序遍历二叉树的顺序是LRD。还有按层遍历二叉树。这些方法的时间复杂度都是O(n)，n为结点个数。

如果T2是由有序树T转换而来的二叉树，那么T中结点的前序就是T2中结点的前序，T中结点的后序就是T2中结点的中序。任何一棵二叉树的叶结点在先序、中序和后序遍历中的相对次序不发改变。设n,m为一棵二叉树上的两个结点，在中序遍历时，n在m前的条件是n在m的左方。前序序列和中序序列相同的二叉树为空树或任一结点均无左孩子的非空二叉树；中序序列和后序序列相同的二叉树为空树或任一结点均无右孩子的非空二叉树；前序序列和后序序列相同的二叉树为空树或仅有一个结点的二叉树。

假设我们有一个包含值的 value 和指向两个子结点的 left 和 right 的树结点结构。我们可以写出这样的过程：

这样会用前序打印出树中的值。在前序，每个结点在访问它的子结点之前访问。类似地，如果打印语句在最后，每个结点在访问他的子节点之后访问，树中的值会用后序来打印。在这两种情况中，左子树中的值比右子树中得值先打印。

最后，上面的中序遍历，每个结点在访问左子树和右子树之间访问。这在遍历二叉搜索树时很常，因为能用递增的顺序来遍历所有的值。

为什么呢？如果 n 是二叉搜索树的结点，那么 n 的左子树的所有结点的值都比n的值要小，而且 n 的右子树的所有节点的值都比n的值要大。因此，如果我们顺序遍历左子树，然后访问 n ，然后顺序遍历右子树。我们就已经循序访问了整个树。

以上的递归算法使用与树的高度成比例的栈空间。如果我们在每个结点中存储指向父结点的指针，那样可以使用反复运算算法，只使用常数空间实现所有这些遍历。然而，指向父结点的指针占用更多的空间。这只在需要指向父节点的指针或栈空间有限时才使用。例如， 这是一个中序遍历的反复运算算法：

深度优先遍历

在深度优先级中，我们希望从根结点访问最远的结点。和图的深度优先搜索不同的是，不需记住访问过的每一个结点，因为树中不会有环。前序，中序和后序遍历都是深度优先遍历的特例。参见深度优先搜索。

广度优先遍历

和深度优先遍历不同，广度优先遍历会先访问离根节点最近的节点。参见广度优先搜索。 二叉树的广度优先遍历又称按层次遍历。算法借助队列实现。

将n叉树转换为二叉树

一般有序树可映射为二叉树，但反之未必成立

n树转换为二叉树的方法：二叉树中结点x的左子结点为n叉树中结点x的左子结点；二叉树中结点x的右子结点为n叉树中结点x的第一个右边的同级结点y。

二叉树当且仅当根节点没有右子结点时可转换为n叉树。

例如，在左边的树中，A有6个子结点{B,C,D,E,F,G}。它能被转换成右边的二叉树。

将一棵树转换为二叉树的方法：

在兄弟之间加一连接；

对每个结点，除了其左孩子外，去除其与其余孩子之间的联系；

以树的根结点为轴心，将整树顺时针转45度。

存储结构与基本操作

树的二叉链表标记法（孩子兄弟标记法）是树和二叉树转换的媒介。

树的二叉链表存储表示

/* 樹的二叉鏈表(孩子—兄弟)存儲表示 */typedefstructCSNode{TElemTypedata;structCSNode*firstchild,*nextsibling;}CSNode,*CSTree;

树的二叉链表存储的基本操作

基于C/C++的算法实现/* 樹的二叉鏈表(孩子—兄弟)存儲的基本操作(17個) */#define ClearTree DestroyTree /* 二者操作相同 */#include"func6-2.c" /* 包括PreOrderTraverse() */voidInitTree(CSTree*T){/* 操作結果：構造空樹T */*T=NULL;}voidDestroyTree(CSTree*T){/* 初始條件：樹T存在。操作結果：銷毀樹T */if(*T){if((*T)->firstchild)/* T有長子 */DestroyTree(&(*T)->firstchild);/* 銷毀T的長子為根結點的子樹 */if((*T)->nextsibling)/* T有下一個兄弟 */DestroyTree(&(*T)->nextsibling);/* 銷毀T的下一個兄弟為根結點的子樹 */free(*T);/* 釋放根結點 */*T=NULL;}}typedefCSTreeQElemType;/* 定義佇列元素類型 */#include"c3-2.h" /* 定義LinkQueue類型(鏈佇列) */#include"bo3-2.c" /* LinkQueue類型的基本操作 */voidCreateTree(CSTree*T){/* 構造樹T */charc[20];/* 臨時存放孩子結點(設不超過20個)的值 */CSTreep,p1;LinkQueueq;inti,l;InitQueue(&q);printf("請輸入根結點(字元型,空格為空): ");scanf("%c%*c",&c[0]);if(c[0]!=Nil)/* 非空樹 */{*T=(CSTree)malloc(sizeof(CSNode));/* 建立根結點 */(*T)->data=c[0];(*T)->nextsibling=NULL;EnQueue(&q,*T);/* 入隊根結點的指針 */while(!QueueEmpty(q))/* 隊不空 */{DeQueue(&q,&p);/* 出隊一個結點的指標 */printf("請按長幼順序輸入結點%c的所有孩子: ",p->data);gets(c);l=strlen(c);if(l>0)/* 有孩子 */{p1=p->firstchild=(CSTree)malloc(sizeof(CSNode));/* 建立長子結點 */p1->data=c[0];for(i=1;inextsibling=(CSTree)malloc(sizeof(CSNode));/* 建立下一個兄弟結點 */EnQueue(&q,p1);/* 入隊上一個結點 */p1=p1->nextsibling;p1->data=c[i];}p1->nextsibling=NULL;EnQueue(&q,p1);/* 入隊最後一個結點 */}elsep->firstchild=NULL;/* 長子指針為空 */}}else*T=NULL;/* 空樹 */}StatusTreeEmpty(CSTreeT){/* 初始條件：樹T存在。操作結果：若T為空樹，則返回TURE，否則返回FALSE */if(T)/* T不空 */returnFALSE;elsereturnTRUE;}intTreeDepth(CSTreeT){/* 初始條件：樹T存在。操作結果：返回T的深度 */CSTreep;intdepth,max=0;if(!T)/* 樹空 */return0;if(!T->firstchild)/* 樹無長子 */return1;for(p=T->firstchild;p;p=p->nextsibling){/* 求子樹深度的最大值 */depth=TreeDepth(p);if(depth>max)max=depth;}returnmax+1;/* 樹的深度=子樹深度最大值+1 */}TElemTypeValue(CSTreep){/* 返回p所指結點的值 */returnp->data;}TElemTypeRoot(CSTreeT){/* 初始條件：樹T存在。操作結果：返回T的根 */if(T)returnValue(T);elsereturnNil;}CSTreePoint(CSTreeT,TElemTypes){/* 返回二叉鏈表(孩子—兄弟)樹T中指向元素值為s的結點的指標。另加 */LinkQueueq;QElemTypea;if(T)/* 非空樹 */{InitQueue(&q);/* 初始化佇列 */EnQueue(&q,T);/* 根結點入隊 */while(!QueueEmpty(q))/* 隊不空 */{DeQueue(&q,&a);/* 出隊,佇列元素賦給a */if(a->data==s)returna;if(a->firstchild)/* 有長子 */EnQueue(&q,a->firstchild);/* 入隊長子 */if(a->nextsibling)/* 有下一個兄弟 */EnQueue(&q,a->nextsibling);/* 入隊下一個兄弟 */}}returnNULL;}StatusAssign(CSTree*T,TElemTypecur_e,TElemTypevalue){/* 初始條件：樹T存在，cur_e是樹T中結點的值。操作結果：改cur_e為value */CSTreep;if(*T)/* 非空樹 */{p=Point(*T,cur_e);/* p為cur_e的指針 */if(p)/* 找到cur_e */{p->data=value;/* 賦新值 */returnOK;}}returnERROR;/* 樹空或沒找到 */}TElemTypeParent(CSTreeT,TElemTypecur_e){/* 初始條件：樹T存在，cur_e是T中某個結點 *//* 操作結果：若cur_e是T的非根結點，則返回它的雙親，否則函數值為＂空＂*/CSTreep,t;LinkQueueq;InitQueue(&q);if(T)/* 樹非空 */{if(Value(T)==cur_e)/* 根結點值為cur_e */returnNil;EnQueue(&q,T);/* 根結點入隊 */while(!QueueEmpty(q)){DeQueue(&q,&p);if(p->firstchild)/* p有長子 */{if(p->firstchild->data==cur_e)/* 長子為cur_e */returnValue(p);/* 返回雙親 */t=p;/* 雙親指針賦給t */p=p->firstchild;/* p指向長子 */EnQueue(&q,p);/* 入隊長子 */while(p->nextsibling)/* 有下一個兄弟 */{p=p->nextsibling;/* p指向下一個兄弟 */if(Value(p)==cur_e)/* 下一個兄弟為cur_e */returnValue(t);/* 返回雙親 */EnQueue(&q,p);/* 入隊下一個兄弟 */}}}}returnNil;/* 樹空或沒找到cur_e */}TElemTypeLeftChild(CSTreeT,TElemTypecur_e){/* 初始條件：樹T存在，cur_e是T中某個結點 *//* 操作結果：若cur_e是T的非葉子結點，則返回它的最左孩子，否則返回＂空＂*/CSTreef;f=Point(T,cur_e);/* f指向結點cur_e */if(f&&f->firstchild)/* 找到結點cur_e且結點cur_e有長子 */returnf->firstchild->data;elsereturnNil;}TElemTypeRightSibling(CSTreeT,TElemTypecur_e){/* 初始條件：樹T存在，cur_e是T中某個結點 *//* 操作結果：若cur_e有右兄弟，則返回它的右兄弟，否則返回＂空＂*/CSTreef;f=Point(T,cur_e);/* f指向結點cur_e */if(f&&f->nextsibling)/* 找到結點cur_e且結點cur_e有右兄弟 */returnf->nextsibling->data;elsereturnNil;/* 樹空 */}StatusInsertChild(CSTree*T,CSTreep,inti,CSTreec){/* 初始條件：樹T存在，p指向T中某個結點，1≦i≦p所指結點的度+1，非空樹c與T不相交 *//* 操作結果：插入c為T中p結點的第i棵子樹 *//* 因為p所指結點的位址不會改變，故p不需是參考類型 */intj;if(*T)/* T不空 */{if(i==1)/* 插入c為p的長子 */{c->nextsibling=p->firstchild;/* p的原長子現是c的下一個兄弟(c本無兄弟) */p->firstchild=c;}else/* 找插入點 */{p=p->firstchild;/* 指向p的長子 */j=2;while(p&&i>j){p=p->nextsibling;j++;}if(j==i)/* 找到插入位置 */{c->nextsibling=p->nextsibling;p->nextsibling=c;}else/* p原有孩子數小於i-1 */returnERROR;}returnOK;}else/* T空 */returnERROR;}StatusDeleteChild(CSTree*T,CSTreep,inti){/* 初始條件：樹T存在，p指向T中某個結點，1≦i≦p所指結點的度 *//* 操作結果：刪除T中p所指結點的第i棵子樹 *//* 因為p所指結點的位址不會改變，故p不需是參考類型 */CSTreeb;intj;if(*T)/* T不空 */{if(i==1)/* 刪除長子 */{b=p->firstchild;p->firstchild=b->nextsibling;/* p的原次子現是長子 */b->nextsibling=NULL;DestroyTree(&b);}else/* 刪除非長子 */{p=p->firstchild;/* p指向長子 */j=2;while(p&&i>j){p=p->nextsibling;j++;}if(j==i)/* 找到第i棵子樹 */{b=p->nextsibling;p->nextsibling=b->nextsibling;b->nextsibling=NULL;DestroyTree(&b);}else/* p原有孩子數小於i */returnERROR;}returnOK;}elsereturnERROR;}voidPostOrderTraverse(CSTreeT,void(*Visit)(TElemType)){/* 後根遍歷孩子—兄弟二叉鏈表結構的樹T */CSTreep;if(T){if(T->firstchild)/* 有長子 */{PostOrderTraverse(T->firstchild,Visit);/* 後根遍歷長子子樹 */p=T->firstchild->nextsibling;/* p指向長子的下一個兄弟 */while(p){PostOrderTraverse(p,Visit);/* 後根遍歷下一個兄弟子樹 */p=p->nextsibling;/* p指向再下一個兄弟 */}}Visit(Value(T));/* 最後訪問根結點 */}}voidLevelOrderTraverse(CSTreeT,void(*Visit)(TElemType)){/* 層序遍歷孩子—兄弟二叉鏈表結構的樹T */CSTreep;LinkQueueq;InitQueue(&q);if(T){Visit(Value(T));/* 先訪問根結點 */EnQueue(&q,T);/* 入隊根結點的指針 */while(!QueueEmpty(q))/* 隊不空 */{DeQueue(&q,&p);/* 出隊一個結點的指標 */if(p->firstchild)/* 有長子 */{p=p->firstchild;Visit(Value(p));/* 訪問長子結點 */EnQueue(&q,p);/* 入隊長子結點的指針 */while(p->nextsibling)/* 有下一個兄弟 */{p=p->nextsibling;Visit(Value(p));/* 訪問下一個兄弟 */EnQueue(&q,p);/* 入隊兄弟結點的指針 */}}}}}

线索二叉树 (threaded binary tree)

线索二叉树(保留遍历时结点在任一序列的前驱和后继的信息)：若点有左子树则其lchild域指示其左孩子，否则令lchild域指示其前驱；若结点有右子树，则其rchild域指示其右孩子，否则令rchild指示其后继。还需在结点结构中增加两个标志域LTag和RTag。LTag=0时，lchild域指示结点的左孩子，LTag=1时，lchild域指示结点的前驱；RTag=0时，rchild域指示结点的右孩子，RTag=1时，rchild域指示结点的后继。以这种结点结构构成的二叉链表作为二叉树的存储结构，叫做线索链表，其中指向结点前驱和后继的指针叫做线索，加上线索的二叉树称为线索二叉树。对二叉树以某种次序遍历使其变为线索二叉树的过程叫做线索化。若对二叉树进行中序遍历，则所得的线索二叉树称为中序线索二叉树，线索链表称为为中序线索链表。线索二叉树是一种物理结构。

在中序线索树找结点后继的规律是：若其右标志为1，则右链为线索，指示其后继，否则遍历其右子树时访问的第一个结点（右子树最左下的结点）为其后继；找结点前驱的规律是：若其左标志为1，则左链为线索，指示其前驱，否则遍历左子树时最后访问的一个结点（左子树中最右下的结点）为其前驱。 在后序线索树中找到结点的后继分三种情况：

若结点是二叉树的根，则其后继为空；

若结点是其双亲的右孩子，或是其双亲的左孩子且其双亲没有右子树，则其后继即为双亲结点；

若结点是其双亲的左孩子，且其双亲有右子树，则其后继为双亲右子树上按后序遍历列出的第一个结点。

二叉线索存储表示

存储结构

二叉树的二叉线索存储表示：在线索链表上添加一个头结点，并令其lchild域的指针指向二叉树的根结点，其rchild域的指针指向中序遍历时访问的最后一个结点。令二叉树中序序列中的第一个结点的lchild域指针和最后一个结点的rchild域的指针均指向头结点，这样就创建了一个双向线索链表。二叉树常采用二叉链表方式存储。

/* 二叉樹的二叉線索存儲表示 */typedefenum{Link,Thread}PointerTag;/* Link(0)：指針，Thread(1)：線索 */typedefstructBiThrNode{TElemTypedata;structBiThrNode*lchild,*rchild;/* 左右孩子指針 */PointerTagLTag,RTag;/* 左右標誌 */}BiThrNode,*BiThrTree;

基本操作

基于C/C++的算法实现/* 二叉樹的二叉線索存儲的基本操作 */voidCreateBiThrTree(BiThrTree*T){/* 按先序輸入線索二叉樹中結點的值，構造線索二叉樹T。0(整型)/空格(字元型)表示空結點 */TElemTypech;scanf(form,&ch);if(ch==Nil)*T=NULL;else{*T=(BiThrTree)malloc(sizeof(BiThrNode));/* 生成根結點(先序) */if(!*T)exit(OVERFLOW);(*T)->data=ch;/* 給根結點賦植 */CreateBiThrTree(&(*T)->lchild);/* 遞迴構造左子樹 */if((*T)->lchild)/* 有左孩子 */(*T)->LTag=Link;/* 給左標誌賦值(指標) */CreateBiThrTree(&(*T)->rchild);/* 遞迴構造右子樹 */if((*T)->rchild)/* 有右孩子 */(*T)->RTag=Link;/* 給右標誌賦值(指標) */}}BiThrTreepre;/* 全域變數，始終指向剛剛訪問過的結點 */voidInThreading(BiThrTreep){/* 通過中序遍歷進行中序線索化，線索化之後pre指向最後一個結點。演算法6.7 */if(p)/* 線索二叉樹不空 */{InThreading(p->lchild);/* 遞迴左子樹線索化 */if(!p->lchild)/* 沒有左孩子 */{p->LTag=Thread;/* 左標誌為線索(前驅) */p->lchild=pre;/* 左孩子指標指向前驅 */}if(!pre->rchild)/* 前驅沒有右孩子 */{pre->RTag=Thread;/* 前驅的右標誌為線索(後繼) */pre->rchild=p;/* 前驅右孩子指標指向其後繼(當前結點p) */}pre=p;/* 保持pre指向p的前驅 */InThreading(p->rchild);/* 遞迴右子樹線索化 */}}voidInOrderThreading(BiThrTree*Thrt,BiThrTreeT){/* 中序遍歷二叉樹T，並將其中序線索化，Thrt指向頭結點。演算法6.6 */*Thrt=(BiThrTree)malloc(sizeof(BiThrNode));if(!*Thrt)/* 生成頭結點不成功 */exit(OVERFLOW);(*Thrt)->LTag=Link;/* 建頭結點，左標誌為指標 */(*Thrt)->RTag=Thread;/* 右標誌為線索 */(*Thrt)->rchild=*Thrt;/* 右指針回指 */if(!T)/* 若二叉樹空，則左指針回指 */(*Thrt)->lchild=*Thrt;else{(*Thrt)->lchild=T;/* 頭結點的左指標指向根結點 */pre=*Thrt;/* pre(前驅)的初值指向頭結點 */InThreading(T);/* 中序遍歷進行中序線索化，pre指向中序遍歷的最後一個結點 */pre->rchild=*Thrt;/* 最後一個結點的右指標指向頭結點 */pre->RTag=Thread;/* 最後一個結點的右標誌為線索 */(*Thrt)->rchild=pre;/* 頭結點的右指標指向中序遍歷的最後一個結點 */}}voidInOrderTraverse_Thr(BiThrTreeT,void(*Visit)(TElemType)){/* 中序遍歷線索二叉樹T(頭結點)的非遞迴演算法。演算法6.5 */BiThrTreep;p=T->lchild;/* p指向根結點 */while(p!=T){/* 空樹或遍歷結束時，p==T */while(p->LTag==Link)/* 由根結點一直找到二叉樹的最左結點 */p=p->lchild;Visit(p->data);/* 訪問此結點 */while(p->RTag==Thread&&p->rchild!=T)/* p->rchild是線索(後繼)，且不是遍歷的最後一個結點 */{p=p->rchild;Visit(p->data);/* 訪問後繼結點 */}p=p->rchild;/* 若p->rchild不是線索(是右孩子)，p指向右孩子，返回迴圈，*/}/* 找這棵子樹中序遍歷的第1個結點 */}voidPreThreading(BiThrTreep){/* PreOrderThreading()調用的遞迴函數 */if(!pre->rchild)/* p的前驅沒有右孩子 */{pre->rchild=p;/* p前驅的後繼指向p */pre->RTag=Thread;/* pre的右孩子為線索 */}if(!p->lchild)/* p沒有左孩子 */{p->LTag=Thread;/* p的左孩子為線索 */p->lchild=pre;/* p的左孩子指向前驅 */}pre=p;/* 移動前驅 */if(p->LTag==Link)/* p有左孩子 */PreThreading(p->lchild);/* 對p的左孩子遞迴呼叫preThreading() */if(p->RTag==Link)/* p有右孩子 */PreThreading(p->rchild);/* 對p的右孩子遞迴呼叫preThreading() */}voidPreOrderThreading(BiThrTree*Thrt,BiThrTreeT){/* 先序線索化二叉樹T，頭結點的右指標指向先序遍歷的最後1個結點 */*Thrt=(BiThrTree)malloc(sizeof(BiThrNode));if(!*Thrt)/* 生成頭結點 */exit(OVERFLOW);(*Thrt)->LTag=Link;/* 頭結點的左指針為孩子 */(*Thrt)->RTag=Thread;/* 頭結點的右指針為線索 */(*Thrt)->rchild=*Thrt;/* 頭結點的右指標指向自身 */if(!T)/* 空樹 */(*Thrt)->lchild=*Thrt;/* 頭結點的左指標也指向自身 */else{/* 非空樹 */(*Thrt)->lchild=T;/* 頭結點的左指標指向根結點 */pre=*Thrt;/* 前驅為頭結點 */PreThreading(T);/* 從頭結點開始先序遞迴線索化 */pre->rchild=*Thrt;/* 最後一個結點的後繼指向頭結點 */pre->RTag=Thread;(*Thrt)->rchild=pre;/* 頭結點的後繼指向最後一個結點 */}}voidPreOrderTraverse_Thr(BiThrTreeT,void(*Visit)(TElemType)){/* 先序遍歷線索二叉樹T(頭結點)的非遞迴演算法 */BiThrTreep=T->lchild;/* p指向根結點 */while(p!=T)/* p沒指向頭結點(遍歷的最後1個結點的後繼指向頭結點) */{Visit(p->data);/* 訪問根結點 */if(p->LTag==Link)/* p有左孩子 */p=p->lchild;/* p指向左孩子(後繼) */else/* p無左孩子 */p=p->rchild;/* p指向右孩子或後繼 */}}voidPostThreading(BiThrTreep){/* PostOrderThreading()調用的遞迴函數 */if(p)/* p不空 */{PostThreading(p->lchild);/* 對p的左孩子遞迴呼叫PostThreading() */PostThreading(p->rchild);/* 對p的右孩子遞迴呼叫PostThreading() */if(!p->lchild)/* p沒有左孩子 */{p->LTag=Thread;/* p的左孩子為線索 */p->lchild=pre;/* p的左孩子指向前驅 */}if(!pre->rchild)/* p的前驅沒有右孩子 */{pre->RTag=Thread;/* p前驅的右孩子為線索 */pre->rchild=p;/* p前驅的後繼指向p */}pre=p;/* 移動前驅 */}}voidPostOrderThreading(BiThrTree*Thrt,BiThrTreeT){/* 後序遞迴線索化二叉樹 */*Thrt=(BiThrTree)malloc(sizeof(BiThrNode));if(!*Thrt)/* 生成頭結點 */exit(OVERFLOW);(*Thrt)->LTag=Link;/* 頭結點的左指針為孩子 */(*Thrt)->RTag=Thread;/* 頭結點的右指針為線索 */if(!T)/* 空樹 */(*Thrt)->lchild=(*Thrt)->rchild=*Thrt;/* 頭結點的左右指標指向自身 */else{/* 非空樹 */(*Thrt)->lchild=(*Thrt)->rchild=T;/* 頭結點的左右指標指向根結點(最後一個結點) */pre=*Thrt;/* 前驅為頭結點 */PostThreading(T);/* 從頭結點開始後序遞迴線索化 */if(pre->RTag!=Link)/* 最後一個結點沒有右孩子 */{pre->rchild=*Thrt;/* 最後一個結點的後繼指向頭結點 */pre->RTag=Thread;}}}voidDestroyBiTree(BiThrTree*T){/* DestroyBiThrTree調用的遞迴函數，T指向根結點 */if(*T)/* 非空樹 */{if((*T)->LTag==0)/* 有左孩子 */DestroyBiTree(&(*T)->lchild);/* 銷毀左孩子子樹 */if((*T)->RTag==0)/* 有右孩子 */DestroyBiTree(&(*T)->rchild);/* 銷毀右孩子子樹 */free(*T);/* 釋放根結點 */T=NULL;/* 空指針賦0 */}}voidDestroyBiThrTree(BiThrTree*Thrt){/* 初始條件：線索二叉樹Thrt存在。操作結果：銷毀線索二叉樹Thrt */if(*Thrt)/* 頭結點存在 */{if((*Thrt)->lchild)/* 根結點存在 */DestroyBiTree(&(*Thrt)->lchild);/* 遞迴銷毀頭結點lchild所指二叉樹 */free(*Thrt);/* 釋放頭結點 */*Thrt=NULL;/* 線索二叉樹Thrt指針賦0 */}}

免责声明：以上内容版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。感谢每一位辛勤著写的作者，感谢每一位的分享。