C語言數據結構之線索二叉樹及其遍歷
遍歷二叉樹就是以一定的規則將二叉樹中的節點排列成一個線性序列，從而得到二叉樹節點的各種遍歷序列，其實質是：對一個非線性的結構進行線性化。使得在這個訪問序列中每一個節點都有一個直接前驅和直接后繼。傳統的鏈式結構只能體現一種父子關系，￥不能直接得到節點在遍歷中的前驅和后繼￥，而我們知道二叉鏈表表示的二叉樹中有大量的空指針，當使用這些空的指針存放指向節點的前驅和后繼的指針時，則可以更加方便的運用二叉樹的某些操作。引入線索二叉樹的目的是： 為了加快查找節點的前驅和后繼。對二叉樹的線索化就是對二叉樹進行一次遍歷，在遍歷的過程中檢測節點的左右指針是否為空，如果是空，則將他們改為指向前驅和后繼節點的線索。
如果二叉樹沒有被線索化，也可以使用<<非遞歸>>的代碼進行遍歷的，但是那就需要借助于<<棧>>,但是在線索化之后，對線索化的二叉樹進行<<非遞歸>>的遍歷就不再需要棧的輔助。
實現代碼：
#include<stdio.h> #include<stdlib.h> #define OK 1 #define ERROR 0 typedef char ElemType; typedef int Status; /* 定義枚舉類型，其值只能是Link和Thread * Link表示的該指針指示的是孩子 * Thread表示的是還指針指示的是前驅或者是后綴 * */ typedef enum { Link,Thread }PointerTag; typedef struct ThrBiTrNode{ ElemType data; struct ThrBiTrNode *lchild, *rchild; PointerTag rTag, lTag; }ThrBiTrNode, *ThrBiTree; ThrBiTree Pre; Status InitThreadBinaryTree(ThrBiTree* T){ *T = NULL; return OK; } //先序建立二叉樹,lchild和rchild都是指示做孩子和右孩子，所以lTag和rTag為Link Status ThreadBinaryTree_PreOrderInput(ThrBiTree* T){ ElemType c; scanf("%c", &c); if( ' ' == c ){ *T = NULL; } else{ *T = (ThrBiTrNode*)malloc(sizeof(ThrBiTrNode)); if( !*T ){ return ERROR; } (*T)->data = c; (*T)->lTag = Link; (*T)->rTag = Link; ThreadBinaryTree_PreOrderInput(&(*T)->lchild); ThreadBinaryTree_PreOrderInput(&(*T)->rchild); } return OK; } //<<中序遍歷>>對二叉樹進行<<線索化>>，但是沒有提供Pre的初始值，只是給出了 //中間的過程，遞歸的思想和思考方式。 //1 線索化左子樹 //2 對雙親節點處理//遞歸中的base //3 線索化右子樹 Status InOrderThread(ThrBiTree T){ if( T != NULL ){ InOrderThread(T->lchild); //線索化左子樹 //對雙親節點進行線索化處理 if( T->lchild == NULL ){ //如果左孩子為空，則將lchild作為索引 //Pre指向剛剛訪問的節點 T->lTag = Thread; T->lchild = Pre; } if( Pre->rchild == NULL ){ //直到現在才知道Pre的后綴是T，所以 //要對Pre進行設置,如果Pre的rchild為空 //則將Pre的rchild設置為后綴，指向T Pre->rTag = Thread; Pre->rchild = T; } Pre = T; //標記當前的節點稱為剛剛訪問過的節點 //Pre最后會指向樹的中序遍歷的最后的 //一個節點 InOrderThread(T->rchild); //線索化右子樹 } return OK; } //創建中序線索二叉樹,為上個函數提供Pre Status CreateInOrderThreadBinaryTree(ThrBiTree T, ThrBiTree* headOfTree){ *headOfTree = (ThrBiTrNode*)malloc(sizeof(struct ThrBiTrNode)); if( !headOfTree ) return ERROR; (*headOfTree)->lTag = Link; //將要指向T (*headOfTree)->rTag = Thread; //將頭節點的rchild用于索引 (*headOfTree)->rchild = *headOfTree; //指向自身 if( T == NULL ){ (*headOfTree)->lchild = *headOfTree; //若T為空樹，則頭節點的lchild //指向自身 } else{ (*headOfTree)->lchild = T; Pre = *headOfTree; //賦值了全局變量Pre InOrderThread(T); //中序線索化 //printf("/n%c/n",Pre->data); //執行完InOrderThread之后Pre指向最后 //一個節點 Pre->rTag = Thread; Pre->rchild = *headOfTree; //(*headOfTree)->rchild = Pre; } return OK; } //對中序線索化后的線索二叉樹使用<<非遞歸>>的代碼進行中序遍歷 //并且原來的遞歸形式的代碼在這里是不再可以進行遍歷。 // 如果二叉樹沒有被線索化，也可以使用<<非遞歸>>的代碼進行遍 // 歷的，但是那就需要借助于<<棧>>,但是在線索化之后，對線索 // 化的二叉樹進行<<非遞歸>>的遍歷就不再需要棧的輔助。 Status visit(ElemType c){ printf("%c ", c); return OK; } Status InOrderTeaverse_NoRecursion(ThrBiTree T, ThrBiTree headOfTree){ //headOfTree是T的頭節點的指針，headOfTree->lchild = T; while( T != headOfTree ){ while( T->lTag == Link ){ //找到樹(子樹)的最左節點 //用while接替if// //用if理解while// T = T->lchild; } visit(T->data); while( T->rTag == Thread && T->rchild != headOfTree){ //這個while和下面的T=T->rchild //可用ifelse語句理解。 //if(rchild是線索 && 不是最后一個節點) //else(rchild不是線索)-->走到右孩子 //也就是代碼T=T->rchild T = T->rchild; visit(T->data); } T = T->rchild; } return OK; } //求中序線索二叉樹中中序序列下的第一個節點 ThrBiTrNode* SeekFirstNode_InOrderThrBiTree(ThrBiTree T){ if( T != NULL ){ while( T->lTag == Link ){ T = T->lchild; } return T; } return ERROR; } //求中序線索二叉樹中節點P在中序序列下的下一個節點 ThrBiTrNode* GetNextNode(ThrBiTrNode* CurrentP){ if( CurrentP->rTag == Link ){ //有右孩子的時候，那么下一個就是以 //右孩子為root的樹的最左下角元素。 //即seekFirstNode的返回值。 return SeekFirstNode_InOrderThrBiTree(CurrentP->rchild); } else{ //沒有右孩子，則rchild指向后綴 return CurrentP->rchild; } } //使用上面兩個函數，SeekFirstNode_InOrderThrBiTree和GetNextNode來實現對 //中序先做二叉樹的遍歷 Status InOrderTraverse_NoRecursion_Method(ThrBiTree T, ThrBiTree head){ for( T = SeekFirstNode_InOrderThrBiTree(T) ; T != head ; T = GetNextNode(T) ) visit(T->data); return OK; } //test /* ShowThread函數的目的是想在將T中序線索化之后，使用函數InOrderTraverse * 函數中序遍歷，輸出一下節點中的信息以檢驗線索化，但是失敗。原因是：在 * 線索化之后，空指針域都被應用，所有InOrderTraverse函數中的if( T )是滿 * 足不了的，故失敗。 Status ShowThread(ThrBiTree C){ printf("%d %d %d %d/n",(C->lchild)->data,(C->rchild)->data,C->lTag,C->rTag); printf("%d %d/n",C->lTag,C->rTag); return OK; * */ //中序遍歷二叉樹 Status InOrderTraverse(ThrBiTree T){ if( T ){ InOrderTraverse(T->lchild); visit(T->data); InOrderTraverse(T->rchild); } return OK; } int main(){ ThrBiTree T,R,Head = NULL; InitThreadBinaryTree(&T); printf("Please Input Binary Tree By PreOrder/n "); ThreadBinaryTree_PreOrderInput(&T); printf(" InOrder Traverse before Thread with Recursion/n"); InOrderTraverse(T); printf("/n"); CreateInOrderThreadBinaryTree(T,&Head); printf(" InOrder Traverse after Thread with no-Recursion/n"); InOrderTeaverse_NoRecursion(T,Head); printf("/n"); printf("The root is %c /n", T->data); //不能夠通過指針形參的值改變指針實參的值 //或者說，對指針形參的改變不會作用到指針 //實參上。 ThrBiTrNode *firstOfInOrder = NULL,*secondOfInOrder = NULL; if( SeekFirstNode_InOrderThrBiTree(T) != ERROR ){ firstOfInOrder = SeekFirstNode_InOrderThrBiTree(T); printf("the value of First Node of InOrderThreadBinaryTree is %c/n", firstOfInOrder->data); } secondOfInOrder = GetNextNode(firstOfInOrder); printf("the value of Node after D is: %c /n", secondOfInOrder->data); secondOfInOrder = GetNextNode(secondOfInOrder); printf("the value of Node after B is: %c /n", secondOfInOrder->data); secondOfInOrder = GetNextNode(secondOfInOrder); printf("the value of Node after E is: %c /n", secondOfInOrder->data); secondOfInOrder = GetNextNode(secondOfInOrder); printf("the value of Node after A is: %c /n", secondOfInOrder->data); secondOfInOrder = GetNextNode(secondOfInOrder); printf("the value of Node after C is: %c /n", secondOfInOrder->data); secondOfInOrder = GetNextNode(secondOfInOrder); printf("the value of Node after G is: %c /n", secondOfInOrder->data); secondOfInOrder = GetNextNode(secondOfInOrder); printf("the value of Node after root is: %c /n", secondOfInOrder->data); printf(" InOrder Traverse after Thread with no-Recursion Method_2/n"); InOrderTraverse_NoRecursion_Method(T,Head); return 0; } 
以上就是線索二叉樹及遍歷的實例，如有疑問請留言或者到本站社區交流討論，感謝閱讀，希望能幫助到大家，謝謝大家對本站的支持！
新聞熱點
疑難解答
圖片精選
