您好,登錄后才能下訂單哦!
這篇文章主要講解了“C語言線索二叉樹結(jié)構(gòu)怎么實現(xiàn)”,文中的講解內(nèi)容簡單清晰,易于學(xué)習(xí)與理解,下面請大家跟著小編的思路慢慢深入,一起來研究和學(xué)習(xí)“C語言線索二叉樹結(jié)構(gòu)怎么實現(xiàn)”吧!
對于一個有n個節(jié)點的二叉樹,每個節(jié)點有指向左右孩子的指針域。其中會出現(xiàn)n+ 1個空指針域,這些空間不儲存任何事物,浪費著內(nèi)存的資源。
對于一些需要頻繁進(jìn)行二叉樹遍歷操作的場合,二叉樹的非遞歸遍歷操作過程相對比較復(fù)雜,遞歸遍歷雖然簡單明了,但是會有額外的開銷,對于操作的時間和空間都比較浪費。
我們可以考慮利用這些空地址,存放指向節(jié)點在某種遍歷次序下的前驅(qū)和后繼節(jié)點的地址。通過這些前驅(qū)和后繼節(jié)點的地址可以知道,從當(dāng)前位置下一步應(yīng)該走向哪里。
指向前驅(qū)和后繼的指針稱為線索,加上線索的二叉鏈表稱為線索鏈表,相應(yīng)的二叉樹就稱為線索二叉樹。
對二叉樹以某種次序遍歷使其變?yōu)榫€索二叉樹的過程稱為線索化。
為了區(qū)分二叉樹某一節(jié)點是指向它的孩子節(jié)點還是指向前驅(qū)或者后繼節(jié)點,我們可以在每個節(jié)點增設(shè)兩個標(biāo)志,Ltag,Rtag.
其中:
Ltag為0時,代表該節(jié)點指向它的左孩子,Ltag為1時,代表該節(jié)點指向它的前驅(qū)節(jié)點。
Rtag為0時,代表該節(jié)點指向它的右孩子,Rtag為1時,代表該節(jié)點指向它的后繼節(jié)點。
所以,線索二叉樹結(jié)構(gòu)定義代碼如下:
typedef char BTDataType; typedef enum{Link,Thread}PointerTag;//Link 是0,Thread 是1。 typedef struct BinaryTreeNode { struct BinaryTreeNode* left; struct BinaryTreeNode* right; PointerTag LTag ; PointerTag RTag; BTDataType data; }BTNode;
線索化的過程就是在遍歷過程中修改空指針的過程
以上二叉樹中序遍歷可以得到:
D B E A F C
D的前驅(qū)是空,后繼是B
B的前驅(qū)是D,后繼是E
E的前驅(qū)是B,后繼是A
F的前驅(qū)是A,后繼是C
C的前驅(qū)是F,后繼是空
線索化后:
中序遍歷線索化的遞歸函數(shù)代碼如下:
//中序線索化 BTNode* pre = NULL;/*全局變量,始終指向剛剛訪問過的節(jié)點*/ void InThreading(BTNode* p) { if (p == NULL) return; InThreading(p->left);//遞歸左子樹線索化 if (!p->left)//左孩子為空,left指針指向前驅(qū) { p->LTag = Thread; p->left = pre; } if (pre!=NULL && !pre->right)//右孩子為空,right指針指向后繼指針。 //這里判斷 pre!=NULL 是因為線索化中序遍歷的第一個節(jié)點(節(jié)點D)時,它并沒有前驅(qū)節(jié)點,此時的pre仍然是NULL。 { pre->RTag = Thread; pre->right = p; } pre = p;//保持pre指向p的前驅(qū) InThreading(p->right); }
分析:
if (!p->left)表示如果某節(jié)點的左指針域為空,因為其前驅(qū)節(jié)點剛剛訪問過,并且賦值給了pre,所以可以將pre賦值給 l -> left,并且修改 p-> LTag = Thread,以完成前驅(qū)節(jié)點的線索化。
pre 是 p 的前驅(qū),那么, p 就是 pre 的后繼。當(dāng)pre -> right 為空時,就可以將p賦值給 pre -> right , 并且修改 pre -> RTag = Thread。
void MidOrder(BTNode*p) { while (p != NULL) { while (p->LTag == Link)// { p = p->left; } printf("%c ",p->data); while (p->RTag == Thread && p->right != p) { p = p->right; printf("%c ", p->data); } p = p->right; } return; }
分析:
while (T->ltag == Link)從根節(jié)點開始遍歷,如果左標(biāo)記是Link讓它一直循環(huán)下去,直到找到標(biāo)記為Thread的的結(jié)點,也就是要遍歷的第一個結(jié)點,然后根據(jù)后驅(qū)指針找到后繼結(jié)點
后面就是重復(fù)以上過程,直到遍歷完整個二叉數(shù)。
感謝各位的閱讀,以上就是“C語言線索二叉樹結(jié)構(gòu)怎么實現(xiàn)”的內(nèi)容了,經(jīng)過本文的學(xué)習(xí)后,相信大家對C語言線索二叉樹結(jié)構(gòu)怎么實現(xiàn)這一問題有了更深刻的體會,具體使用情況還需要大家實踐驗證。這里是億速云,小編將為大家推送更多相關(guān)知識點的文章,歡迎關(guān)注!
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進(jìn)行舉報,并提供相關(guān)證據(jù),一經(jīng)查實,將立刻刪除涉嫌侵權(quán)內(nèi)容。