在電腦科學中，二元樹是每個節點最多有兩個子樹的樹結構。通常子樹被稱作「左子樹」（left subtree）和「右子樹」（right subtree）。二元樹常被用於實現二元搜尋樹和二叉堆。

二元樹的每個結點至多只有二棵子樹(不存在度大於2的結點)，二元樹的子樹有左右之分，次序不能顛倒。二元樹的第i層至多有個結點；深度為k的二元樹至多有個結點；對任何一棵二元樹T，如果其終端結點數為，度為2的結點數為，則。

樹和二元樹的三個主要差別：

1.樹的結點個數至少為1，而二元樹的結點個數可以為0；
2.樹中結點的最大度數沒有限制，而二元樹結點的最大度數為2；
3.樹的結點無左、右之分，而二元樹的結點有左、右之分。
<完全二元樹和滿二元樹>

1.滿二元樹：一棵深度為k，且有個節點成為滿二元樹
2.完全二元樹：深度為k，有n個節點的二元樹，若且唯若其每一個節點都與深度為k的滿二元樹中序號為1至n的節點對應時，稱之為完全二元樹
目錄 [隱藏]
1 圖論中的定義
2 二元樹(Binary Tree)的類型
3 存儲二元樹的方法
3.1 順序存儲表示
3.1.1 儲存結構
3.1.2 基本操作
3.2 二叉鏈表存儲表示
3.2.1 存儲結構
3.2.2 基本操作
3.3 三叉鏈表存儲表示
3.3.1 存儲結構
3.3.2 基本操作
4 訪問二元樹的方法
4.1 前(先)序、中序、後序遍歷
4.2 深度優先遍歷
4.3 廣度優先遍歷
5 將n叉樹轉換為二元樹
5.1 存儲結構與基本操作
5.1.1 樹的二叉鏈表存儲表示
5.1.2 樹的二叉鏈表存儲的基本操作
6 線索二元樹 (threaded binary tree)
6.1 二叉線索存儲表示
6.1.1 存儲結構
6.1.2 基本操作


[編輯] 圖論中的定義二元樹在圖論中是這樣定義的：二元樹是一個連通的無環圖，並且每一個頂點的度不大於3。有根二元樹還要滿足根結點的度不大於2。有了根結點之後，每個頂點定義了唯一的父結點，和最多2個子結點。然而，沒有足夠的訊息來區分左結點和右結點。如果不考慮連通性，允許圖中有多個連通分量，這樣的結構叫做森林。

[編輯] 二元樹(Binary Tree)的類型二元樹是一個有根樹，並且每個節點最多有2個子節點。非空的二元樹，若樹葉總數為 n0，分支度為2的總數為 n2，則 n0 = n2 + 1。



一棵深度為k，且有個節點的二元樹，稱為滿二元樹（Full Binary Tree）。這種樹的特點是每一層上的節點數都是最大節點數。在一棵二元樹中，除最後一層外，若其餘層都是滿的，並且最後一層或者是滿的，或者是在右邊缺少連續若干節點，則此二元樹為完全二元樹（Complete Binary Tree）。具有n個節點的完全二元樹的深度為。深度為k的完全二元樹，至少有個節點，至多有個節點。



Complete Binary Tree Full Binary Tree
總節點k < k < k =
樹高h h = h =

[編輯] 存儲二元樹的方法在編程語言中能用多種方法來構造二元樹。

[編輯]
順序存儲表示二元樹可以用數組或線性表來存儲，而且如果這是完全二元樹，這種方法不會浪費空間。用這種緊湊排列，如果一個結點的索引為i，它的子結點能在索引2i+1和2i+2找到，並且它的父節點（如果有）能在索引floor((i-1)/2)找到（假設根節點的索引為0）。這種方法更有利於緊湊存儲和更好的訪問的局部性，特別是在前序遍歷中。然而，它需要連續的存儲空間，這樣在存儲高度為h的n個結點組成的一般普通樹時將會浪費很多空間。一種最極壞的情況下如果深度為h的二元樹每個節點只有右孩子需要佔用2的h次冪減1，而實際卻只有h個結點，空間的浪費太大，這갊O順序存儲結構的一大缺點。


[編輯] 儲存結構 /* 二叉?的?序存?表示 */
#define MAX_TREE_SIZE 100 /* 二叉?的最大??? */
typedef TElemType SqBiTree[MAX_TREE_SIZE]; /* 0??元存?根?? */

typedef struct
{
int level,order; /* ??的?，本?序?(按?二叉??算) */
}position;
[編輯] 基本操作顯示▼隱藏▲基於C/C++的實作演算法 /* 二叉?的?序存?的基本操作(23?)*/
#define ClearBiTree InitBiTree /* 在順序存儲結構中，兩函數完全一樣 */
#define DestroyBiTree InitBiTree /* 在順序存儲結構中，兩函數完全一樣 */
void InitBiTree(SqBiTree T) －－－（SqBiTree & T）
{ /* 構造空二叉樹T。因為T是數組名，故不需要& */
int i;
for(i=0;i<MAX_TREE_SIZE;i++)
T[i]=Nil; /* 初值為空(Nil在主程中定義) */
}
void CreateBiTree(SqBiTree T)
{ /* 按層序次序輸入二叉樹中結點的值(字符型或整型), 構造順序存儲的二叉樹T */
int i=0;
#if CHAR /* 結點類型為字符 */
int l;
char s[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++;
}
#endif
for(i=1;i<MAX_TREE_SIZE;i++)
if(T[(i+1)/2-1]==Nil&&T[i]!=Nil) /* 此非根結點(不空)無雙親 */
{
printf("出現無雙親的非根結點"form"\n",T[i]);
exit(ERROR);
}
}
Status BiTreeEmpty(SqBiTree T)
{ /* 初始條件：二叉樹T存在。操作結果：若T為空二叉樹，則返回TRUE，否則FALSE */
if(T[0]==Nil) /* 根結點為空，則樹空 */
return TRUE;
else
return FALSE;
}
int BiTreeDepth(SqBiTree T)
{ /* 初始條件：二叉樹T存在。操作結果：返回T的深度 */
int i,j=-1;
for(i=MAX_TREE_SIZE-1;i>=0;i--) /* 找到最後一個結點 */
if(T[i]!=Nil)
break;
i++; /* 為了便於計算 */
do
j++;
while(i>=pow(2,j)); /*pow是原型為double pow( double x, double y ),計算x的y次方,h = log₂k + 1來計算二叉樹的深度*/
return j;
}
Status Root(SqBiTree T,TElemType *e)
{ /* 初始條件：二叉樹T存在。操作結果：當T不空，用e返回T的根，返回OK；否則返回ERROR，e無定義 */
if(BiTreeEmpty(T)) /* T空 */
return ERROR;
else
{
*e=T[0];
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&&(T[i*2+1]!=Nil||T[i*2+2]!=Nil)) /* 給雙親賦空值但有葉子(不空) */
return ERROR;
T[i]=value;
return OK;
}
TElemType Parent(SqBiTree T,TElemType e)
{ /* 初始條件：二叉樹T存在，e是T中某個結點 */
/* 操作結果：若e是T的非根結點，則返回它的雙親，否則返回”空” */
int i;
if(T[0]==Nil) /* 空樹 */
return Nil;
for(i=1;i<=MAX_TREE_SIZE-1;i++)
if(T[i]==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(T[0]==Nil) /* 空樹 */
return Nil;
for(i=0;i<=MAX_TREE_SIZE-1;i++)
if(T[i]==e) /* 找到e */
return T[i*2+1];
return Nil; /* 沒找到e */
}
TElemType RightChild(SqBiTree T,TElemType e)
{ /* 初始條件：二叉樹T存在，e是T中某個結點。操作結果：返回e的右孩子。若e無右孩子,則返回"空" */
int i;
if(T[0]==Nil) /* 空樹 */
return Nil;
for(i=0;i<=MAX_TREE_SIZE-1;i++)
if(T[i]==e) /* 找到e */
return T[i*2+2];
return Nil; /* 沒找到e */
}
TElemType LeftSibling(SqBiTree T,TElemType e)
{ /* 初始條件：二叉樹T存在，e是T中某個結點 */
/* 操作結果：返回e的左兄弟。若e是T的左孩子或無左兄弟，則返回”空” */
int i;
if(T[0]==Nil) /* 空樹 */
return Nil;
for(i=1;i<=MAX_TREE_SIZE-1;i++)
if(T[i]==e&&i%2==0) /* 找到e且其序號為偶數(是右孩子) */
return T[i-1];
return Nil; /* 沒找到e */
}
TElemType RightSibling(SqBiTree T,TElemType e)
{ /* 初始條件：二叉樹T存在，e是T中某個結點 */
/* 操作結果：返回e的右兄弟。若e是T的右孩子或無右兄弟，則返回”空” */
int i;
if(T[0]==Nil) /* 空樹 */
return Nil;
for(i=1;i<=MAX_TREE_SIZE-1;i++)
if(T[i]==e&&i%2) /* 找到e且其序號為奇數(是左孩子) */
return T[i+1];
return Nil; /* 沒找到e */
}
void Move(SqBiTree q,int j,SqBiTree T,int i) /* 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結點置空 */
}
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(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結點的右子樹開始的子樹 */
Mov/* 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);
}
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(T[2*e+1]!=Nil) /* 左子樹不空 */
PostTraverse(T,2*e+1);
if(T[2*e+2]!=Nil) /* 右子樹不空 */
PostTraverse(T,2*e+2);
VisitFunc(T[e]);
}
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(T[i]==Nil)
i--; /* 找到最後一個非空結點的序號 */
for(j=0;j<=i;j++) /* 從根結點起，按層序遍歷二叉樹 */
if(T[j]!=Nil)
Visit(T[j]); /* 只遍歷非空的結點 */
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;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，一些子結點指針可能為空值，或者為特殊的哨兵結點。 使用連結串列能避免順序儲存浪費空間的問題，演算法和結構相對簡單，但使用二叉連結串列，由於缺乏父鏈的指引，在找回父節點時需要重新掃描樹得知父節點的節點位址。


[編輯] 存儲結構/* 二叉樹的二叉鏈表存儲表示 */
typedef struct BiTNode
{
TElemType data;
struct BiTNode *lchild,*rchild; /* 左右孩子指針 */
}BiTNode,*BiTree;
[編輯] 基本操作顯示▼隱藏▲基於C/C++的實作演算法 /* 二叉樹的二叉鏈表存儲的基本操作(22個) */
#define ClearBiTree DestroyBiTree /* 清空二叉樹和銷毀二叉樹的操作一樣 */
#include"func6-3.c"
/* 包括InitBiTree()、DestroyBiTree()、PreOrderTraverse()和InOrderTraverse()4函數 */
void CreateBiTree(BiTree *T)
{ /* 算法6.4：按先序次序輸入二叉樹中結點的值(可為字符型或整型，在主程中定義)，*/
/* 構造二叉鏈表表示的二叉樹T。變量Nil表示空(子)樹。有改動 */
TElemType ch;
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); /* 構造右子樹 */
}
}
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 i>j?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; /* 設隊列元素為二叉樹的指針類型 */
#include"c3-2.h" /* 鏈隊列 */
#include"bo3-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; /* 設棧元素為二叉樹的指針類型 */
#include"c3-1.h" /* 順序棧 */
#include"bo3-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;
[編輯] 基本操作顯示▼隱藏▲基於C/C++的實作演算法 /* 二叉樹的三叉鏈表存儲的基本操作(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); /* 構造右子樹 */
if((*T)->rchild) /* 有右孩子 */
(*T)->rchild->parent=*T; /* 給右孩子的雙親域賦值 */
}
}
Status BiTreeEmpty(BiPTree T)
{ /* 初始條件：二叉樹T存在。操作結果：若T為空二叉樹，則返回TRUE，否則FALSE */
if(T)
return FALSE;
else
return TRUE;
}
int BiTreeDepth(BiPTree T)
{ /* 初始條件：二叉樹T存在。操作結果：返回T的深度 */
int i,j;
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 i>j?i+1:j+1; /* T的深度為其左右子樹的深度中的大者+1 */
}
TElemType Root(BiPTree T)
{ /* 初始條件：二叉樹T存在。操作結果：返回T的根 */
if(T)
return T->data;
else
return Nil;
}
TElemType Value(BiPTree p)
{ /* 初始條件：二叉樹T存在，p指向T中某個結點。操作結果：返回p所指結點的值 */
return p->data;
}
void Assign(BiPTree p,TElemType value)
{ /* 給p所指結點賦值為value */
p->data=value;
}
typedef BiPTree QElemType; /* 設隊列元素為二叉樹的指針類型 */
#include"c3-2.h" /* 鏈隊列 */
#include"bo3-2.c" /* 鏈隊列的基本操作 */
BiPTree Point(BiPTree T,TElemType e)
{ /* 返回二叉樹T中指向元素值為e的結點的指針。加 */
LinkQueue q;
QElemType a;
if(T) /* 非空樹 */
{
InitQueue(&q); /* 初始化隊列 */
EnQueue(&q,T); /* 根結點入隊 */
while(!QueueEmpty(q)) /* 隊不空 */
{
DeQueue(&q,&a); /* 出隊，隊列元素賦給a */
if(a->data==e)
return a;
if(a->lchild) /* 有左孩子 */
EnQueue(&q,a->lchild); /* 入隊左孩子 */
if(a->rchild) /* 有右孩子 */
EnQueue(&q,a->rchild); /* 入隊右孩子 */
}
}
return NULL;
}
TElemType Parent(BiPTree T,TElemType e)
{ /* 初始條件：二叉樹T存在，e是T中某個結點 */
/* 操作結果：若e是T的非根結點，則返回它的雙親，否則返回”空”*/
BiPTree a;
if(T) /* 非空樹 */
{
a=Point(T,e); /* a是結點e的指針 */
if(a&&a!=T) /* T中存在結點e且e是非根結點 */
return a->parent->data; /* 返回e的雙親的值 */
}
return Nil; /* 其餘情況返回空 */
}
TElemType LeftChild(BiPTree T,TElemType e)
{ /* 初始條件：二叉樹T存在，e是T中某個結點。操作結果：返回e的左孩子。若e無左孩子,則返回"空" */
BiPTree 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(BiPTree T,TElemType e)
{ /* 初始條件：二叉樹T存在，e是T中某個結點。操作結果：返回e的右孩子。若e無右孩子,則返回"空" */
BiPTree 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(BiPTree T,TElemType e)
{ /* 初始條件：二叉樹T存在，e是T中某個結點 */
/* 操作結果：返回e的左兄弟。若e是T的左孩子或無左兄弟，則返回”空”*/
BiPTree a;
if(T) /* 非空樹 */
{
a=Point(T,e); /* a是結點e的指針 */
if(a&&a!=T&&a->parent->lchild&&a->parent->lchild!=a) /* T中存在結點e且e存在左兄弟 */
return a->parent->lchild->data; /* 返回e的左兄弟的值 */
}
return Nil; /* 其餘情況返回空 */
}
TElemType RightSibling(BiPTree T,TElemType e)
{ /* 初始條件：二叉樹T存在，e是T中某個結點 */
/* 操作結果：返回e的右兄弟。若e是T的右孩子或無右兄弟，則返回”空”*/
BiPTree a;
if(T) /* 非空樹 */
{
a=Point(T,e); /* a是結點e的指針 */
if(a&&a!=T&&a->parent->rchild&&a->parent->rchild!=a) /* T中存在結點e且e存在右兄弟 */
return a->parent->rchild->data; /* 返回e的右兄弟的值 */
}
return Nil; /* 其餘情況返回空 */
}
Status InsertChild(BiPTree p,int LR,BiPTree 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;
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;
}
return OK;
}
return ERROR; /* p空 */
}
Status DeleteChild(BiPTree 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空 */
}
void PreOrderTraverse(BiPTree T,void(*Visit)(BiPTree))
{ /* 先序遞歸遍歷二叉樹T */
if(T)
{
Visit(T); /* 先訪問根結點 */
PreOrderTraverse(T->lchild,Visit); /* 再先序遍歷左子樹 */
PreOrderTraverse(T->rchild,Visit); /* 最後先序遍歷右子樹 */
}
}
void InOrderTraverse(BiPTree T,void(*Visit)(BiPTree))
{ /* 中序遞歸遍歷二叉樹T */
if(T)
{
InOrderTraverse(T->lchild,Visit); /* 中序遍歷左子樹 */
Visit(T); /* 再訪問根結點 */
InOrderTraverse(T->rchild,Visit); /* 最後中序遍歷右子樹 */
}
}
void PostOrderTraverse(BiPTree T,void(*Visit)(BiPTree))
{ /* 後序遞歸遍歷二叉樹T */
if(T)
{
PostOrderTraverse(T->lchild,Visit); /* 後序遍歷左子樹 */
PostOrderTraverse(T->rchild,Visit); /* 後序遍歷右子樹 */
Visit(T); /* 最後訪問根結點 */
}
}
void LevelOrderTraverse(BiPTree T,void(*Visit)(BiPTree))
{ /* 層序遍歷二叉樹T(利用隊列) */
LinkQueue q;
QElemType a;
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的樹結點結構。我們可以寫出這樣的過程：

visit(node)
print node.value
if node.left != null then visit(node.left)
if node.right != null then visit(node.right)
這樣會用中序列印出樹中的值。在中序，每個結點在訪問它的子結點之前訪問。類似地，如果列印語句在最後，每個結點在訪問他的子節點之後訪問，樹中的值會用後序來列印。在這兩種情況中，左子樹中的值比右子樹中得值先列印。

visit(node)
if node.left != null then visit(node.left)
print node.value
if node.right != null then visit(node.right)
最後，上面的中序遍歷，每個結點在訪問左子樹和右子樹之間訪問。這在遍歷二叉搜尋樹時很常用，因為它能用遞增的順序來遍歷所有的值。

為什麼呢？如果n是二叉搜尋樹的結點，那麼n的左子樹的所有結點的值都比n的值要小，而且n的右子樹的所有節點的值都比n的值要大。因此，如果我們順序遍歷左子樹，然後訪問n，然後順序遍歷右子樹。我們就已經順序訪問了整個樹。




在這個二元樹中，
前序遍歷的結果：2, 7, 2, 6, 5, 11, 5, 9, 4
後序遍歷的結果：2, 5, 11, 6, 7, 4, 9, 5, 2
中序遍歷的結果：2, 7, 5, 6, 11, 2, 5, 4, 9



以上的遞歸演算法使用與樹的高度成比例的棧空間。如果我們在每個結點中存儲指向父結點的指針，那樣可以使用迭代演算法，只使用常數空間實現所有這些遍歷。然而，指向父結點的指針佔用更多的空間。這只在需要指向父節點的指針或棧空間有限時才使用。例如， 這是一個中序遍歷的迭代演算法：

visit(root)
prev := null
current := root
next := null

while current != null
if prev == current.parent
prev := current
next := current.left
if next == null or prev == current.left
print current.value
prev := current
next := current.right
if next == null or prev == current.right
prev := current
next := current.parent
current := next



用二元樹表示下述表達式：a+b*(c-d)-e/f
先序遍歷的序列是：-+a*b-cd/ef
中序遍歷的序列是：a+b*c-d-e/f
後序遍歷的序列是：abcd-*+ef/-


[編輯] 深度優先遍歷在深度優先順序中，我們希望從根結點訪問最遠的結點。和圖的深度優先搜尋不同的是，不需記住訪問過的每一個結點，因為樹中不會有環。前序，中序和後序遍歷都是深度優先遍歷的特例。參見深度優先搜尋。

[編輯] 廣度優先遍歷和深度優先遍歷不同，廣度優先遍歷會先訪問離根節點最近的節點。參見廣度優先搜尋。 二元樹的廣度優先遍歷又稱按層次遍歷。演算法藉助隊列實現。

[編輯] 將n叉樹轉換為二元樹一般有序樹和二元樹之間有一一對映關係，能進行相互轉換。

n叉樹轉換為二元樹的方法：二元樹中結點x的左子結點為n叉樹中結點x的左子結點；二元樹中結點x的右子結點為n叉樹中結點x的第一個右邊的同級結點y。

例如，在左邊的樹中，A有6個子結點{B,C,D,E,F,G}。它能被轉換成右邊的二元樹。






將一棵樹轉換為二元樹的方法：
1.在兄弟之間加一連線；
2.對每個結點，除了其左孩子外，去除其與其餘孩子之間的聯繫；
3.以樹的根結點為軸心，將整樹順時針轉45度。
[編輯] 存儲結構與基本操作樹的二叉鏈表表示法（孩子兄弟表示法）是樹和二元樹轉換的媒介。

[編輯] 樹的二叉鏈表存儲表示 /* 樹的二叉鏈表(孩子—兄弟)存儲表示 */
typedef struct CSNode
{
TElemType data;
struct CSNode *firstchild,*nextsibling;
}CSNode,*CSTree;
[編輯] 樹的二叉鏈表存儲的基本操作顯示▼隱藏▲基於C/C++的演算法實作 /* 樹的二叉鏈表(孩子—兄弟)存儲的基本操作(17個) */
#define ClearTree DestroyTree /* 二者操作相同 */
#include"func6-2.c" /* 包括PreOrderTraverse() */
void InitTree(CSTree *T)
{ /* 操作結果：構造空樹T */
*T=NULL;
}
void DestroyTree(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;
}
}
typedef CSTree QElemType; /* 定義隊列元素類型 */
#include"c3-2.h" /* 定義LinkQueue類型(鏈隊列) */
#include"bo3-2.c" /* LinkQueue類型的基本操作 */
void CreateTree(CSTree *T)
{ /* 構造樹T */
char c[20]; /* 臨時存放孩子結點(設不超過20個)的值 */
CSTree p,p1;
LinkQueue q;
int i,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;i<l;i++)
{
p1->nextsibling=(CSTree)malloc(sizeof(CSNode)); /* 建立下一個兄弟結點 */
EnQueue(&q,p1); /* 入隊上一個結點 */
p1=p1->nextsibling;
p1->data=c[i];
}
p1->nextsibling=NULL;
EnQueue(&q,p1); /* 入隊最後一個結點 */
}
else
p->firstchild=NULL; /* 長子指針為空 */
}
}
else
*T=NULL; /* 空樹 */
}
Status TreeEmpty(CSTree T)
{ /* 初始條件：樹T存在。操作結果：若T為空樹，則返回TURE，否則返回FALSE */
if(T) /* T不空 */
return FALSE;
else
return TRUE;
}
int TreeDepth(CSTree T)
{ /* 初始條件：樹T存在。操作結果：返回T的深度 */
CSTree p;
int depth,max=0;
if(!T) /* 樹空 */
return 0;
if(!T->firstchild) /* 樹無長子 */
return 1;
for(p=T->firstchild;p;p=p->nextsibling)
{ /* 求子樹深度的最大值 */
depth=TreeDepth(p);
if(depth>max)
max=depth;
}
return max+1; /* 樹的深度=子樹深度最大值+1 */
}
TElemType Value(CSTree p)
{ /* 返回p所指結點的值 */
return p->data;
}
TElemType Root(CSTree T)
{ /* 初始條件：樹T存在。操作結果：返回T的根 */
if(T)
return Value(T);
else
return Nil;
}
CSTree Point(CSTree 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->firstchild) /* 有長子 */
EnQueue(&q,a->firstchild); /* 入隊長子 */
if(a->nextsibling) /* 有下一個兄弟 */
EnQueue(&q,a->nextsibling); /* 入隊下一個兄弟 */
}
}
return NULL;
}
Status Assign(CSTree *T,TElemType cur_e,TElemType value)
{ /* 初始條件：樹T存在，cur_e是樹T中結點的值。操作結果：改cur_e為value */
CSTree p;
if(*T) /* 非空樹 */
{
p=Point(*T,cur_e); /* p為cur_e的指針 */
if(p) /* 找到cur_e */
{
p->data=value; /* 賦新值 */
return OK;
}
}
return ERROR; /* 樹空或沒找到 */
}
TElemType Parent(CSTree T,TElemType cur_e)
{ /* 初始條件：樹T存在，cur_e是T中某個結點 */
/* 操作結果：若cur_e是T的非根結點，則返回它的雙親，否則函數值為”空”*/
CSTree p,t;
LinkQueue q;
InitQueue(&q);
if(T) /* 樹非空 */
{
if(Value(T)==cur_e) /* 根結點值為cur_e */
return Nil;
EnQueue(&q,T); /* 根結點入隊 */
while(!QueueEmpty(q))
{
DeQueue(&q,&p);
if(p->firstchild) /* p有長子 */
{
if(p->firstchild->data==cur_e) /* 長子為cur_e */
return Value(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 */
return Value(t); /* 返回雙親 */
EnQueue(&q,p); /* 入隊下一個兄弟 */
}
}
}
}
return Nil; /* 樹空或沒找到cur_e */
}
TElemType LeftChild(CSTree T,TElemType cur_e)
{ /* 初始條件：樹T存在，cur_e是T中某個結點 */
/* 操作結果：若cur_e是T的非葉子結點，則返回它的最左孩子，否則返回”空”*/
CSTree f;
f=Point(T,cur_e); /* f指向結點cur_e */
if(f&&f->firstchild) /* 找到結點cur_e且結點cur_e有長子 */
return f->firstchild->data;
else
return Nil;
}
TElemType RightSibling(CSTree T,TElemType cur_e)
{ /* 初始條件：樹T存在，cur_e是T中某個結點 */
/* 操作結果：若cur_e有右兄弟，則返回它的右兄弟，否則返回”空”*/
CSTree f;
f=Point(T,cur_e); /* f指向結點cur_e */
if(f&&f->nextsibling) /* 找到結點cur_e且結點cur_e有右兄弟 */
return f->nextsibling->data;
else
return Nil; /* 樹空 */
}
Status InsertChild(CSTree *T,CSTree p,int i,CSTree c)
{ /* 初始條件：樹T存在，p指向T中某個結點，1≦i≦p所指結點的度+1，非空樹c與T不相交 */
/* 操作結果：插入c為T中p結點的第i棵子樹 */
/* 因為p所指結點的地址不會改變，故p不需是引用類型 */
int j;
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 */
return ERROR;
}
return OK;
}
else /* T空 */
return ERROR;
}
Status DeleteChild(CSTree *T,CSTree p,int i)
{ /* 初始條件：樹T存在，p指向T中某個結點，1≦i≦p所指結點的度 */
/* 操作結果：刪除T中p所指結點的第i棵子樹 */
/* 因為p所指結點的地址不會改變，故p不需是引用類型 */
CSTree b;
int j;
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 */
return ERROR;
}
return OK;
}
else
return ERROR;
}
void PostOrderTraverse(CSTree T,void(*Visit)(TElemType))
{ /* 後根遍歷孩子—兄弟二叉鏈表結構的樹T */
CSTree p;
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)); /* 最後訪問根結點 */
}
}
void LevelOrderTraverse(CSTree T,void(*Visit)(TElemType))
{ /* 層序遍歷孩子—兄弟二叉鏈表結構的樹T */
CSTree p;
LinkQueue q;
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域指示結點的後繼。以這種結點結構構成的二叉鏈表作為二元樹的存儲結構，叫做線索鏈表，其中指向結點前驅和後繼的指針叫做線索，加上線索的二元樹稱為線索二元樹ꄊC對二元樹以某種次序遍歷使其變為線索二元樹的過程叫做線索化。若對二元樹進行中序遍歷，則所得的線索二元樹稱為中序線索二元樹，線索鏈表稱為為中序線索鏈表。線索二元樹是一種物理結構。

在中序線索樹找結點後繼的規律是：若其右標誌為1，則右鏈為線索，指示其後繼，否則遍歷其右子樹時訪問的第一個結點（右子樹最左下的結點）為其後繼；找結點前驅的規律是：若其左標誌為1，則左鏈為線索，指示其前驅，否則遍歷左子樹時最後訪問的一個結點（左子樹中最右下的結點）為其前驅。
在後序線索樹中找到結點的後繼分三種情況：

1.若結點是二元樹的根，則其後繼為空；
2.若結點是其雙親的右孩子，或是其雙親的左孩子且其雙親沒有右子樹，則其後繼即為雙親結點；
3.若結點是其雙親的左孩子，且其雙親有右子樹，則其後繼為雙親右子樹上按後序遍歷列出的第一個結點。
[編輯] 二叉線索存儲表示[編輯] 存儲結構二元樹的二叉線索存儲表示：在線索鏈表上添加一個頭結點，並令其lchild域的指針指向二元樹的根結點，其rchild域的指針指向中序遍歷時訪問的最後一個結點。令二元樹中序序列中的第一個結點的lchild域指針和最後一個結點的rchild域的指針均指向頭結點，這樣就建立了一個雙向線索鏈表

/* 二叉樹的二叉線索存儲表示 */
typedef enum{Link,Thread}PointerTag; /* Link(0)：指針，Thread(1)：線索 */
typedef struct BiThrNode
{
TElemType data;
struct BiThrNode *lchild,*rchild; /* 左右孩子指針 */
PointerTag LTag,RTag; /* 左右標誌 */
}BiThrNode,*BiThrTree;
[編輯] 基本操作顯示▼隱藏▲基於C/C++的演算法實作 /* 二叉樹的二叉線索存儲的基本操作 */
void CreateBiThrTree(BiThrTree *T)
{ /* 按先序輸入線索二叉樹中結點的值，構造線索二叉樹T。0(整型)/空格(字符型)表示空結點 */
TElemType ch;
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; /* 給右標誌賦值(指針) */
}
}
BiThrTree pre; /* 全局變量，始終指向剛剛訪問過的結點 */
void InThreading(BiThrTree p)
{ /* 通過中序遍歷進行中序線索化，線索化之後pre指向最後一個結點。算法6.7 */
if(p) /* 線索二叉樹不空 */
{
InThreading(p->lchild); /* 遞歸左子樹線索化 */
if(!p->lchild) /* 沒有左孩子 */
{
p->LTag=Thread; /* 左標誌為線索(前驅) */
p->lchild=pre; /* 左孩子指針指向前驅 */
}
d;
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個結點 */
}
void PreThreading(BiThrTree p)
{ /* 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() */
}
void PreOrderThreading(BiThrTree *Thrt,BiThrTree T)
{ /* 先序線索化二叉樹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; /* 頭結點的後繼指向最後一個結點 */
}
}
void PreOrderTraverse_Thr(BiThrTree T,void(*Visit)(TElemType))
{ /* 先序遍歷線索二叉樹T(頭結點)的非遞歸算法 */
BiThrTree p=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指向右孩子或後繼 */
}
}
void PostThreading(BiThrTree p)
{ /* 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; /* 移動前驅 */
}
}
void PostOrderThreading(BiThrTree *Thrt,BiThrTree T)
{ /* 後序遞歸線索化二叉樹 */
*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;
}
}
}
void DestroyBiTree(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 */
}
}
void DestroyBiThrTree(BiThrTree *Thrt)
{ /* 初始條件：線索二叉樹Thrt存在。操作結果：銷毀線索二叉樹Thrt */
if(*Thrt) /* 頭結點存在 */
{
if((*Thrt)->lchild) /* 根結點存在 */
DestroyBiTree(&(*Thrt)->lchild); /* 遞歸銷毀頭結點lchild所指二叉樹 */
free(*Thrt); /* 釋放頭結點 */
*Thrt=NULL; /* 線索二叉樹Thrt指針賦0 */
}
}

顯示▼隱藏▲檢 論 編電腦科學中的樹

二元樹 二元樹 二元搜尋樹 (BST) 笛卡爾樹 Top tree T樹

自平衡二元搜尋樹 AA樹 AVL樹 紅黑樹 伸展樹 樹堆 節點大小平衡樹

B樹 B樹 B+樹 B*樹 Bx樹 UB樹 2-3樹 2-3-4樹 (a,b)-樹 Dancing tree H樹

Trie 字尾樹 基數樹

空間劃分樹 四叉樹 八叉樹 k-d樹 vp-樹 R樹 R*樹 R+樹 X樹 M樹 線段樹 希爾伯特R樹 優先R樹

非二元樹 Exponential tree Fusion tree 區間樹 PQ tree Range tree SPQR tree Van Emde Boas tree

其他型別 堆 雜湊樹 Finger tree Metric tree Cover tree BK-tree Doubly-chained tree iDistance Link-cut tree 樹狀陣列

取自「http://zh.wikipedia.org/w/index.php?title=二叉?&oldid=24229733」
查看本頁評分給本文評分
給本文評分
本頁評分
這是什麼？目前平均評分
可信度

客觀性

完整性

可讀性

我非常了解與本主題相關的知識（可選）
我有與其有關學院/大學學位這是我專業的一部分個人對此有深厚的興趣此處未列出我的知識的來源 我想幫助改善維基百科，請給我發送一封電子郵件（可選） 我們將向您發送確認電子郵件。基於反饋隱私政策，我們不會與任何人分享您的地址。提交評分

保存成功你的評分尚未提交你的評分已過期請重新評估本頁並重新評分。
發生了錯誤。請稍後再試。
謝謝！您的評分已保存。你想要創建帳戶嗎？帳戶將幫助您跟蹤您所做的編輯，參與討論，並成為社區的一部分。創建帳戶或者登入以後再說
謝謝！您的評分已保存。您知道您可以編輯此頁嗎？編輯本頁以後再說 3個分類：資料結構樹結構圖論1個隱藏分類：自2007年10月缺少來源的條目

--
plurk
http://www.plurk.com/dasea2010
face book
http://www.facebook.com/dasea.chien
google+
https://plus.google.com/u/0/

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.130.189.48