一顆線索二叉樹：

根據(jù)下圖進(jìn)行節(jié)點的創(chuàng)建：

代碼如下：

#include <iostream> using namespace std; typedef char ElemType;typedef struct BiThrNode {ElemType data;int ltag,rtag;struct BiThrNode *lchild,*rchild; }BiThrNode,*BiThrTree;

因為普通二叉樹有空指針域，所以我們可以利用這些空指針來線索化

1、二叉樹的線索化，實質(zhì)上就是遍歷一棵二叉樹，在遍歷過程中，訪問節(jié)點的操作是檢查當(dāng)前結(jié)點的左右指針域是否為空，如果為空，即將他們改為前驅(qū)節(jié)點或后繼節(jié)點的線索。為記錄前驅(qū)節(jié)點，定義pre為全局變量，始終指向當(dāng)前結(jié)點的前驅(qū)節(jié)點。

定義一個全局變量指向線索二叉樹的前驅(qū)節(jié)點：

BiThrNode *pre;

中序遍歷進(jìn)行線索化：

void InThreading(BiThrTree p) {if (p){InThreading(p->lchild);if (!p->lchild){p->ltag = 1;p->lchild = pre;}if (!pre->rchild){pre->rtag = 1;pre->rchild = p;}pre = p;InThreading(p->rchild);} }

根據(jù)下圖建立頭結(jié)點，線索化：

代碼如下：

bool InOrderThr(BiThrNode *head,BiThrTree T) {head = new BiThrNode;if (head==NULL)return false;head->ltag = 0;head->rtag = 1;head->rchild = head;if (!T){head->lchild = head;}else{head->lchild = T;pre = head;InThreading(T);pre->rchild = head;pre->rtag = 1;head->rchild = pre;}return true; }

對于中序線索二叉樹上的任意節(jié)點，尋找其中序的前驅(qū)節(jié)點，有以下兩種情況：
1、如果該節(jié)點的左標(biāo)志域為1，那么其左指針?biāo)赶虻墓?jié)點便是它的前驅(qū)節(jié)點。
2、如果該節(jié)點的左標(biāo)志為0，表明該節(jié)點有左孩子，根據(jù)中序遍歷的定義，它的前驅(qū)節(jié)點是以該節(jié)點的左孩子為根節(jié)點的子樹的最右節(jié)點，即沿著其左子樹的右指針鏈向下查找，當(dāng)某節(jié)點的右標(biāo)志域為1時，它就是所要找的前驅(qū)節(jié)點。

在中序線索二叉樹上查找任意節(jié)點的中序前驅(qū)節(jié)點：

BiThrNode *InPreNode(BiThrNode *p) {BiThrNode *pre;pre = p->lchild;if (p->ltag!=1){while(pre->rtag == 0){pre = pre->rchild;}}return pre; }

對于中序線索二叉樹上的任意節(jié)點，尋找其中序的后繼節(jié)點，有以下兩種情況：
1、如果該節(jié)點的右標(biāo)志域為1，那么其右指針?biāo)赶虻墓?jié)點便是它的后繼節(jié)點。
2、如果該節(jié)點的右標(biāo)志為0，表明該節(jié)點有右孩子，根據(jù)中序遍歷的定義，它的后繼節(jié)點是以該節(jié)點的右孩子為根節(jié)點的子樹的最左節(jié)點，即沿著其右子樹的左指針鏈向下查找，當(dāng)某節(jié)點的左標(biāo)志域為1時，它就是所要找的后繼節(jié)點。

在中序線索二叉樹上查找任意節(jié)點的中序后繼節(jié)點：

BiThrNode *InpostNode(BiThrNode *p) {BiThrNode *post;post = p->rchild;if (p->rtag!=1){while(post->ltag==0){post = post->lchild;}}return post; }

從最后一個節(jié)點根據(jù)前驅(qū)節(jié)點進(jìn)行線索二叉樹的遍歷：

void InOrderPre(BiThrNode *head) {BiThrNode *p;p = head->rchild;//指向最后一個節(jié)點while(p != NULL && p!=head){cout<<p->data;p = InPreNode(p);} }

從第一個節(jié)點根據(jù)后繼節(jié)點進(jìn)行線索二叉樹的遍歷：

void InOrderPost(BiThrNode *head) {BiThrNode *p;p = head->lchild;while (p->ltag != 1) {p = p->lchild;}while (p != NULL && p != head) {cout << p->data;p = InPostNode(p);} }

完整代碼如下：

#include <iostream> using namespace std; typedef char ElemType;typedef struct BiThrNode {//節(jié)點的創(chuàng)建ElemType data;int ltag, rtag;struct BiThrNode *lchild, *rchild; } BiThrNode, *BiThrTree;BiThrNode *pre;//定義一個全局變量指向線索二叉樹的前驅(qū)節(jié)點void InThreading(BiThrTree &p) {if (p) {InThreading(p->lchild);if (!p->lchild) {p->ltag = 1;p->lchild = pre;}if (!pre->rchild) {pre->rtag = 1;pre->rchild = p;}pre = p;InThreading(p->rchild);} }bool InOrderThr(BiThrTree &head, BiThrTree T) {head = new BiThrNode;if (head == NULL)return false;head->ltag = 0;head->rtag = 1;head->rchild = head;if (!T) {head->lchild = head;} else {head->lchild = T;pre = head;InThreading(T);pre->rchild = head;pre->rtag = 1;head->rchild = pre;}return true; }BiThrNode *InPreNode(BiThrNode *p) {BiThrNode *pre;pre = p->lchild;if (p->ltag != 1) {while (pre->rtag == 0) {pre = pre->rchild;}}return pre; }BiThrNode *InPostNode(BiThrNode *p) {BiThrNode *post;post = p->rchild;if (p->rtag != 1) {while (post->ltag == 0) {post = post->lchild;}}return post; }void InOrderPre(BiThrNode *head) {BiThrNode *p;p = head->rchild;//指向最后一個節(jié)點while (p != NULL && p != head) {cout << p->data;p = InPreNode(p);} }void InOrderPost(BiThrNode *head) {BiThrNode *p;p = head->lchild;while (p->ltag != 1) {p = p->lchild;}while (p != NULL && p != head) {cout << p->data;p = InPostNode(p);} }void CreateBiTree(BiThrTree &T) {//以先序遍歷的方式創(chuàng)建二叉樹char ch;cin >> ch;if (ch == '#')T = NULL;else {T = new BiThrNode;T->data = ch;T->ltag = 0;T->rtag = 0;CreateBiTree(T->lchild);CreateBiTree(T->rchild);} }int main() {BiThrTree T;BiThrNode *head;CreateBiTree(T);//以先序遍歷輸入if (InOrderThr(head, T))cout << "線索化完成" << endl;elsecout << "線索化失敗" << endl;cout<<"逆序輸出中序遍歷: ";InOrderPre(head);//逆序輸出中序遍歷cout << endl;cout<<"正序輸出中序遍歷: ";InOrderPost(head);//正序輸出中序遍歷return 0; }

測試效果圖:

測試結(jié)果：

本文參考文章地址:
https://blog.csdn.net/g15827636417/article/details/52967949

總結(jié)

以上是生活随笔為你收集整理的C++实现链式存储线索二叉树的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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