我們知道，當(dāng)以二叉鏈表作為存儲(chǔ)結(jié)構(gòu)時(shí)，只能找到結(jié)點(diǎn)的左、右孩子信息，而不能直接得到結(jié)點(diǎn)在任一序列中的前驅(qū)和后繼信息。

做下面規(guī)定：若結(jié)點(diǎn)有左子樹(shù)，則其lchild指示其左孩子，否則令lchild域指示其前驅(qū)；若結(jié)點(diǎn)有右子樹(shù)，則其rchild域指示其右孩子，否則rchild域指示其后繼。這樣我們?cè)黾觾蓚€(gè)標(biāo)志域(如下圖所示)

這種結(jié)構(gòu)就是先是鏈表，對(duì)應(yīng)的樹(shù)就是線索二叉樹(shù)。

這個(gè)有什么用呢？

我們舉個(gè)例子。

比如，下面的這個(gè)樹(shù)：

這個(gè)圖里面：我們?nèi)绻孟刃虮闅v為：ABDHIECFG但是我們看到這個(gè)H,I,E,F,G他們的左右孩子都為空，

但我們把他中序遍歷后為HDIBEAFCG,我們可以看到他們剛剛好，H,I,E,F,G他們的左右孩子都為空。但他們恰好可以用這個(gè)放他們的前驅(qū)或后繼。

這就是線索二叉樹(shù)的好處。。

代碼如下：

#include <stdio.h> #include <stdlib.h> #include <Windows.h>typedef char ElemType;//線索存儲(chǔ)標(biāo)志位 //Link(0)：表示指向左右孩子的指針 //Thread(1)：表示指向前驅(qū)后繼的線索 typedef enum{Link,Thread} PointerTag;typedef struct BitThrNode {char data;struct BitThrNode *lchild, *rchild;PointerTag ltag; //標(biāo)志左孩子PointerTag rtag; //標(biāo)志右孩子 }BiThrNode,*BiThrTree;//全局變量始終指向剛剛訪問(wèn)過(guò)的節(jié)點(diǎn) BiThrTree pre;//創(chuàng)建一顆二叉樹(shù)，按照前序遍歷方式輸入 void CreateBiThrTree(BiThrTree *T) {char c;scanf_s("%c", &c);if ('$' == c){*T = NULL;}else{*T = (BiThrNode*)malloc(sizeof(BiThrNode));(*T)->data = c;(*T)->ltag = Link;(*T)->rtag = Link;CreateBiThrTree(&(*T)->lchild);CreateBiThrTree(&(*T)->rchild);}}//中序遍歷線索化 void InThreading(BiThrTree T) {if (T){InThreading(T->lchild); //遞歸左孩子線索化//結(jié)點(diǎn)處理if (!T->lchild) //如果該結(jié)點(diǎn)沒(méi)有左孩子，設(shè)置ltag為T(mén)hread，并把lchild指向剛剛訪問(wèn)的結(jié)點(diǎn)。{T->ltag = Thread;T->lchild = pre;}if (!pre->rchild){pre->rtag = Thread;pre->rchild = T;}pre = T;InThreading(T->rchild); //遞歸右孩子線索化} }void InOrderThreading(BiThrTree *p,BiThrTree T) {*p = (BiThrTree)malloc(sizeof(BiThrNode));(*p)->ltag = Link;(*p)->rtag = Thread;(*p)->rchild = *p;if (!T){(*p)->lchild = *p;}else{(*p)->lchild = T;pre = *p;InThreading(T);pre->rchild = *p;pre->rtag = Thread;(*p)->rchild = pre;} }void visit(char c) {printf_s("%c", c); }//中序遍歷二叉樹(shù)，非遞歸 void InOrderTraverse(BiThrTree T) {BiThrTree p;p = T->lchild;while (p != T){while (p->ltag == Link){p = p->lchild;}visit(p->data);while (p->rtag == Thread && p->rchild != T){p = p->rchild;visit(p->data);}p = p->rchild;} }int main() {BiThrTree P, T = NULL;CreateBiThrTree(&T);InOrderThreading(&P, T);printf_s("中序遍歷輸出結(jié)果為：");InOrderTraverse(P);printf_s("\n");system("pause");return 0; } 下面是運(yùn)行結(jié)果：

總結(jié)

以上是生活随笔為你收集整理的6.3.2线索二叉树的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。