二叉樹

在電腦科學中，二叉樹（英語：Binary tree）是每個節點最多只有兩個分支（即不存在分支度大於2的節點）的樹結構^[1]。通常分支被稱作「左子樹」或「右子樹」。二叉樹的分支具有左右次序，不能隨意顛倒。

二叉樹的第 $i$ 層至多擁有 $2^{i-1}$ 個節點；深度為 $k$ 的二叉樹至多總共有 $2^{\begin{aligned}k+1\end{aligned}}-1$ 個節點（定義根節點所在深度 $k_{0}=0$ ），而總計擁有節點數符合的，稱為「滿二叉樹」；深度為 $k$ 有 $n$ 個節點的二叉樹，當且僅當其中的每一節點，都可以和深度 $k$ 的滿二叉樹，序號1到 $n$ 的節點一對一對應時，稱為完全二叉樹。對任何一棵非空的二叉樹 $T$ ，如果其葉片（終端節點）數為 $n_{0}$ ，分支度為2的節點數為 $n_{2}$ ，則 $n_{0}=n_{2}+1$ 。

與普通樹不同，普通樹的節點個數至少為1，而二叉樹的節點個數可以為0；普通樹節點的最大分支度沒有限制，而二叉樹節點的最大分支度為2；普通樹的節點無左、右次序之分，而二叉樹的節點有左、右次序之分。

二叉樹通常作為資料結構應用，典型用法是對節點定義一個標記函數，將一些值與每個節點相關聯。這樣標記的二叉樹就可以實現二叉搜尋樹和二叉堆積，並應用於高效率的搜尋和排序。

圖論中的定義[編輯]

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

性質[編輯]

二叉樹是一個有根樹，並且每個節點最多有2個子節點。非空的二叉樹，若樹葉總數為 n0，分支度為2的總數為 n2，則 n0 = n2 + 1。

特殊類型[編輯]

	完全二叉樹	完美二叉樹
總節點k	$2^{h-1}$ <= k <= $2^{h}-1$	k = $2^{h}-1$
樹高h	h = $log_{2}k+1$	h = $log_{2}(k+1)$

完美二叉樹[編輯]

一棵深度為k，且有 $2^{\begin{aligned}k\end{aligned}}-1$ 個節點的二叉樹，稱為完美二叉樹（Perfect Binary Tree）。這種樹的特點是每一層上的節點數都是最大節點數。

性質[編輯]

對於一棵深度為 $k$ 的完美二叉樹：

共有 $2^{k}-1$ 個結點
結點個數一定為奇數
第 $i$ 層有 $2^{i-1}$ 個結點
有 $2^{k-1}$ 個葉子

完全二叉樹[編輯]

在一顆二叉樹中，若除最後一層外的其餘層都是滿的，並且最後一層要麼是滿的，要麼在右邊缺少連續若干節點，則此二叉樹為完全二叉樹（Complete Binary Tree）。具有n個節點的完全二叉樹的深度為 $log_{2}n+1$ 。深度為k的完全二叉樹，至少有 $2^{\begin{aligned}k-1\end{aligned}}$ 個節點，至多有 $2^{\begin{aligned}k\end{aligned}}-1$ 個節點。

儲存[編輯]

在程式設計語言中能用多種方法來構造二叉樹。

順序儲存表示[編輯]

一個儲存在陣列中的完全二叉樹

二叉樹可以用陣列或鏈結串列來儲存，若是滿二叉樹就能緊湊排列而不浪費空間。如果某個節點的索引為i，（假設根節點的索引為0）則在它左子節點的索引會是 $2i+1$ ，以及右子節點會是 $2i+2$ ；而它的父節點（如果有）索引則為 $\left\lfloor {\frac {i-1}{2}}\right\rfloor$ 。這種方法更有利於緊湊儲存和更好的訪問的局部性，特別是在前序遍歷中。然而，它需要連續的儲存空間，這樣在儲存高度為h的n個節點所組成的一般樹時，將浪費很多空間。在最糟糕的情況下，如果深度為h的二叉樹其每個節點都只有右孩子，則該儲存結構需要佔用 $2^{h}-1$ 的空間，實際上卻有h個節點，浪費了不少空間，是順序儲存結構的一大缺點。

儲存結構[編輯]

 /* 二叉树的顺序存储表示 */
 #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);
    }
}

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<sub>2</sub>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結點的右子樹開始的子樹 */
  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(T[i]==Nil) /* 此結點空 */
    return ERROR;
  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); /* 佇列不空 */
  }
  return OK;
}

void(*VisitFunc)(TElemType); /* 函數變數 */
void PreTraverse(SqBiTree T,int e)
{ /* 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);
}

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(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");
   }
 }

三元連結串列儲存表示[編輯]

改進於二元連結串列，增加父節點的指引，能更好地實現節點間的訪問，不過演算法相對複雜。當二叉樹用三元連結串列表示時，有N個結點，就會有N+2個空指針。

儲存結構[編輯]

 /* 二叉樹的三叉鏈表存儲表示 */
 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，然後順序遍歷右子樹。我們就已經循序存取了整個樹。

後序遍歷偽代碼如下：

visit(node)
    if node.left  != null then visit(node.left)
    if node.right != null then visit(node.right)
    print node.value

在這個二叉樹中，

前序遍歷的結果：M，G，D，B，A，C，F，E，J，H，I，K，L，S，P，O，N，Q，R，W，U，T，V，X，Z，Y
後序遍歷的結果：A，C，B，E，F，D，I，H，L，K，J，G，N，O，R，Q，P，T，V，U，Y，Z，X，W，S，M
中序遍歷的結果：A，B，C，D，E，F，G，H，I，J，K，L，M，N，O，P，Q，R，S，T，U，V，W，X，Y，Z

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

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叉樹轉換為二叉樹的方法：二叉樹中結點x的左子結點為n叉樹中結點x的左子結點；二叉樹中結點x的右子結點為n叉樹中結點x的第一個右邊的同級結點y。

二叉樹當且僅當根節點沒有右子結點時可轉換為n叉樹。

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

將一棵樹轉換為二叉樹的方法：

在兄弟之間加一連線；
對每個結點，除了其左孩子外，去除其與其餘孩子之間的聯繫；
以樹的根結點為軸心，將整樹順時針轉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域指示結點的後繼。以這種結點結構構成的二元連結串列作為二叉樹的儲存結構，叫做線索連結串列，其中指向結點前驅和後繼的指標叫做線索，加上線索的二叉樹稱為線索二叉樹。對二叉樹以某種次序遍歷使其變為線索二叉樹的過程叫做線索化。若對二叉樹進行中序遍歷，則所得的線索二叉樹稱為中序線索二叉樹，線索連結串列稱為為中序線索連結串列。線索二叉樹是一種物理結構。

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

若結點是二叉樹的根，則其後繼為空；
若結點是其雙親的右孩子，或是其雙親的左孩子且其雙親沒有右子樹，則其後繼即為雙親結點；
若結點是其雙親的左孩子，且其雙親有右子樹，則其後繼為雙親右子樹上按後序遍歷列出的第一個結點。

二元線索儲存表示[編輯]

儲存結構[編輯]

二叉樹的二元線索儲存表示：在線索連結串列上添加一個頭結點，並令其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; /* 左孩子指標指向前驅 */
     }
     if(pre && !pre->rchild) /* 前驅不爲空并且前驅沒有右孩子 */
     {
       pre->RTag=Thread; /* 前驅的右標誌為線索(後繼) */
       pre->rchild=p; /* 前驅右孩子指標指向其後繼(當前結點p) */
     }
     pre=p; /* 保持pre指向p的前驅 */
     InThreading(p->rchild); /* 遞迴右子樹線索化 */
   }
 }

 void InOrderThreading(BiThrTree *Thrt,BiThrTree T)
 { /* 中序遍歷二叉樹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; /* 頭結點的右指標指向中序遍歷的最後一個結點 */
   }
 }

 void InOrderTraverse_Thr(BiThrTree T,void(*Visit)(TElemType))
 { /* 中序遍歷線索二叉樹T(頭結點)的非遞迴演算法。演算法6.5 */
   BiThrTree p;
   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個結點 */
 }

 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 */
   }
 }

外部連結[編輯]

binary trees（頁面存檔備份，存於互聯網檔案館） entry in the FindStat（頁面存檔備份，存於互聯網檔案館）資料庫
Gamedev.net introduction on binary trees（頁面存檔備份，存於互聯網檔案館）
二叉樹歸納證明（頁面存檔備份，存於互聯網檔案館）
Balanced binary search tree on array How to create bottom-up an Ahnentafel list, or a balanced binary search tree on array（頁面存檔備份，存於互聯網檔案館）
Binary trees and Implementation of the same with working code examples

^ Thomas H. Cormen; Charles E. Leiserson; Ronald L. Rivest; Clifford Stein. B.5.3 Binary and positional trees. Introduction to algorithms Third. Cambridge, Mass.: MIT Press. 2009: 1177–1178 [2023-02-06]. ISBN 978-0-262-03384-8.

[1] Thomas H. Cormen; Charles E. Leiserson; Ronald L. Rivest; Clifford Stein. B.5.3 Binary and positional trees. Introduction to algorithms Third. Cambridge, Mass.: MIT Press. 2009: 1177–1178 [2023-02-06]. ISBN 978-0-262-03384-8.

[1]