線索二叉樹的定義：還是按照鏈二叉樹的方法創建，只不過在結點原本為空的左指標改為指向該結點在中序遍歷中的前驅，結點原本為空的右指標改為指向該結點在中序遍歷中的后繼，也就是說把空的指標給利用了起來，
1.定義結構體
與鏈二叉樹不同的是結點增加了兩個資料，判斷指標下一個連接的是樹還是線索
typedef enum{Link,Thread}PointerTag; //0表示連接 ，1表示線索 typedef struct BiTNode{ char data; struct BiTNode *lchild,*rchild; //左右孩子樹 PointerTag ltag; //Link代表連接,Thread代表線索 PointerTag rtag; }BiTNode,*BiTree; BiTree pre; //全域變數 ，始終指向訪問過的節點
2.二叉樹的創建
//二叉樹的建立 void createBiTree(BiTree *T) { char c; scanf("%c",&c); if(c=='$') { *T=NULL; } else { *T=(BiTree)malloc(sizeof(BiTNode)); (*T)->data=https://www.cnblogs.com/qian-yi/p/c; (*T)->ltag=Link; //先設定都有左子樹 (*T)->rtag=Link; //先設定都有右子樹 createBiTree(&(*T)->lchild); //按照先序遍歷創建二叉樹 createBiTree(&(*T)->rchild); } }
3.將二叉樹中的空指標線索化，pre指向最后一個結點
就只是將二叉樹中空的指標線索化，一開始的pre指向的是頭結點
void createThread(BiTree T) { if(T) //線索二叉樹不為空 { createThread(T->lchild); if(!T->lchild) //如果該節點沒有左子樹 { T->ltag=Thread; //將該結點左邊線索化 T->lchild=pre; //該結點的前驅指向上一個結點 } if(!pre->rchild) //如果上一個結點沒有右子樹 { pre->rtag=Thread; //將該結點右邊線索化 pre->rchild=T; //將上一個結點的后繼指向該結點 } pre=T;//向下回圈 createThread(T->rchild); } }
4.添加頭結點
步驟如下：
（1）.先創建一個頭結點，
（2）.頭結點的左指標指向該二叉樹的根節點，表示為Link.
（3）中序遍歷的第一個結點的左指標表示為Thread，指向頭結點
（4）中序遍歷的尾結點的的右指標表示為Thrad，指向頭結點
（5）.頭結點的右指標指向的是二叉樹中序遍歷的尾結點，表示為Thread.
//線索二叉樹增加頭結點 void createHeadNode(BiTree *thrt,BiTree T) { *thrt=(BiTree)malloc(sizeof(BiTNode)); //創建頭結點 if(!thrt) { printf("創建空間失敗\n"); } (*thrt)->ltag=Link; //左邊是連接 (*thrt)->rtag=Thread; //右邊是線索 (*thrt)->rchild=*thrt; //右邊指標指向自己 if(!T) //如果二叉樹為空 { (*thrt)->lchild=*thrt; } else //如果二叉樹不為空 { (*thrt)->lchild=T; //頭結點的左邊指標指向根節點 pre=*thrt; //將前驅的值指向頭結點 createThread(T); //中序遍歷進行中序線索化，pre指向中序遍歷的最后一個結點 pre->rtag=Thread; //最后一個結點的右標志為線索 pre->rchild=*thrt; //最后一個結點的右指標指向頭結點 (*thrt)->rchild=pre; //頭結點的右指標指向最后一個節點 } }
5.按照中序遍歷的方法非遞回進行遍歷
中序遍歷：先找到最左節點，再訪問其根節點，再訪問右結點
這里的方法是：
1.先找到最左節點，然后列印該結點
2.如果該結點存在右子樹，訪問右子樹，則回傳回圈
2.如果不存在右子樹，則訪問線索，列印出該結點，訪問其右子樹，然后回圈
void middleSort(BiTree T) { BiTree p; p=T->lchild;//p是該二叉樹的根節點 while(p!=T) //空樹或遍歷結束時，p==T { while(p->ltag==Link) //先找到最左結點 { p=p->lchild; } printf("%c ",p->data); while(p->rtag==Thread&&p->rchild!=T) { p=p->rchild; printf("%c ",p->data); } p=p->rchild; //若p->rchild不是線索(是右孩子)，p指向右孩子，回傳回圈 } }
所有的代碼如下：
#include<stdio.h> #include<stdlib.h> typedef enum{Link,Thread}PointerTag; //0表示連接 ，1表示線索 typedef struct BiTNode{ char data; struct BiTNode *lchild,*rchild; //左右孩子樹 PointerTag ltag; //Link代表連接,Thread代表線索 PointerTag rtag; }BiTNode,*BiTree; BiTree pre; //全域變數 ，始終指向訪問過的節點 //二叉樹的建立 void createBiTree(BiTree *T) { char c; scanf("%c",&c); if(c=='$') { *T=NULL; } else { *T=(BiTree)malloc(sizeof(BiTNode)); (*T)->data=https://www.cnblogs.com/qian-yi/p/c; (*T)->ltag=Link; //先設定都有左子樹 (*T)->rtag=Link; //先設定都有右子樹 createBiTree(&(*T)->lchild); //按照先序遍歷創建二叉樹 createBiTree(&(*T)->rchild); } } //二叉樹的中序遍歷來線索化 ,線索化結束后pre指向最后的一個結點 void createThread(BiTree T) { if(T) //線索二叉樹不為空 { createThread(T->lchild); if(!T->lchild) //如果該節點沒有左子樹 { T->ltag=Thread; //將該結點左邊線索化 T->lchild=pre; //該結點的前驅指向上一個結點 } if(!pre->rchild) //如果上一個結點沒有右子樹 { pre->rtag=Thread; //將該結點右邊線索化 pre->rchild=T; //將上一個結點的后繼指向該結點 } pre=T;//向下回圈 createThread(T->rchild); } } //線索二叉樹增加頭結點 void createHeadNode(BiTree *thrt,BiTree T) { *thrt=(BiTree)malloc(sizeof(BiTNode)); //創建頭結點 if(!thrt) { printf("創建空間失敗\n"); } (*thrt)->ltag=Link; //左邊是連接 (*thrt)->rtag=Thread; //右邊是線索 (*thrt)->rchild=*thrt; //右邊指標指向自己 if(!T) //如果二叉樹為空 { (*thrt)->lchild=*thrt; } else //如果二叉樹不為空 { (*thrt)->lchild=T; //頭結點的左邊指標指向根節點 pre=*thrt; //將前驅的值指向頭結點 createThread(T); //中序遍歷進行中序線索化，pre指向中序遍歷的最后一個結點 pre->rtag=Thread; //最后一個結點的右標志為線索 pre->rchild=*thrt; //最后一個結點的右指標指向頭結點 (*thrt)->rchild=pre; //頭結點的右指標指向最后一個節點 } } //中序遍歷線索二叉樹T的非遞回演算法 void middleSort(BiTree T) { BiTree p; p=T->lchild;//p是該二叉樹的根節點 while(p!=T) //空樹或遍歷結束時，p==T { while(p->ltag==Link) //先找到最左結點 { p=p->lchild; } printf("%c ",p->data); while(p->rtag==Thread&&p->rchild!=T) { p=p->rchild; printf("%c ",p->data); } p=p->rchild; //若p->rchild不是線索(是右孩子)，p指向右孩子，回傳回圈 } } int main() { printf("請輸入二叉樹，按照先序遍歷的順序，空指標用$號表示\n"); BiTree T,K; createBiTree(&T); //按照先序遍歷的順序生成一個二叉樹 createHeadNode(&K,T); //給二叉樹添加頭結點并且線索化 middleSort(K); //按照中序遍歷的方法非遞回輸出值 }
這就是完整的線索二叉樹了，可能線索二叉樹也有其它的表示方式，也可以嘗試寫一下，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/198920.html
標籤：其他