二叉树
線索二叉樹 > 二叉線索存儲表示 > 基本操作

基於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 */
   }
 }
一個存儲在陣列中的完全二元樹
基於鏈表的二叉樹邏輯結構示意
基於三叉鏈表的二叉樹的邏輯結構
二叉樹與森林相互轉換的邏輯示意