【概述】

對(duì)于一個(gè)有 n 個(gè)結(jié)點(diǎn)的二叉鏈表，每個(gè)結(jié)點(diǎn)指向左右孩子的兩個(gè)指針域，故共有 2n 個(gè)指針域，而 n 個(gè)結(jié)點(diǎn)的二叉樹共有 n-1 條分支，即存在 2n-(n-1)=n+1 個(gè)空指針域，白白浪費(fèi)了資源。

另一方面，在二叉鏈表上，只能知道每個(gè)結(jié)點(diǎn)的左右孩子結(jié)點(diǎn)的地址，而不知道某個(gè)結(jié)點(diǎn)的前驅(qū)和后繼，要想知道，必須對(duì)二叉樹進(jìn)行遍歷，以后每次想要知道時(shí)，都要遍歷一次，這無疑浪費(fèi)了時(shí)間。

綜合以上兩個(gè)方面，可以考慮利用空地址，存放指向結(jié)點(diǎn)在某種遍歷次序下的前驅(qū)與后繼，將指向前驅(qū)與后繼的指針稱為線索，加上線索的二叉鏈表稱為線索鏈表，相應(yīng)的二叉樹就稱為線索二叉樹。

【實(shí)現(xiàn)類】

線索化的實(shí)質(zhì)就是將二叉鏈表中的空指針改為指向前驅(qū)或后繼的線索，因此其存儲(chǔ)結(jié)構(gòu)相較于二叉鏈表有了更改

typedef enum{link,thread} Tag;//link=0表示指向左右孩子指針，thead=1表示指向前驅(qū)或后繼的線索 template<class T> struct Node{T data;//數(shù)據(jù)域Node<T> *lchild,rchild;//指針域Tag ltag,rtag;//標(biāo)志域 };

對(duì)二叉樹以某種次序遍歷使其變?yōu)榫€索二叉樹的過程稱為線索化，由于二叉樹的遍歷分為前序、中序、后序、層序四種，那么相應(yīng)的，在建立線索二叉樹時(shí)，依據(jù)遍歷次序的不同，也同樣分為四種：

• 前序線索二叉樹
• 中序線索二叉樹
• 后序線索二叉樹
• 層序線索二叉樹

以上四種線索二叉樹只是在線索化時(shí)的順序有所不同，以下以中序線索二叉樹為例

template<class T> class ThreadTree{ public:ThreadTree();//構(gòu)造函數(shù)，建立中序線索鏈表~ThreadTree();//析構(gòu)函數(shù)，釋放各結(jié)點(diǎn)空間Node<T> * findNext(Node<T> *bt);//查找結(jié)點(diǎn)bt的后繼void inOrder();//中序遍歷 private:Node<T> *root;//指向線索鏈表的頭指針Node<T> * creat(Node<T> *bt);//構(gòu)造函數(shù)調(diào)用void inThread(Node<T> *bt,Node<T> *pre);//構(gòu)造函數(shù)調(diào)用 };

【構(gòu)造函數(shù)】

構(gòu)造函數(shù)的功能是建立一個(gè)中序線索鏈表，實(shí)質(zhì)上就是將二叉樹中的空指針改為指向前驅(qū)或后繼的線索，而前驅(qū)或后繼信息只有在遍歷該二叉樹時(shí)才能得到，因此建立線索鏈表應(yīng)先建立一個(gè)二叉鏈表，然后在遍歷的過程中修改空指針建立線索鏈表。

template<class T> ThreadTree<T>::ThreadTree(){//構(gòu)造函數(shù)root=creat(root);//建立帶線索標(biāo)志的二叉鏈表Node<T> *pre=NULL;//當(dāng)前訪問結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)inThread(root,pre);//遍歷二叉鏈表，建立線索 } template<class T> Node<T>* ThreadTree<T>::creat(Node<T> *bt){//建立帶線索標(biāo)志的二叉鏈表char ch;cin>>ch;if(ch=='#')//生成空樹bt=NULL;else{bt=new Node<T>;bt->data=ch;bt->ltag=link;//左標(biāo)志bt->rtag=link;//右標(biāo)志bt->lchild=creat(bt->lchild);//遞歸建立左子樹bt->rchild=creat(bt->rchild);//遞歸建立右子樹} }template<class T> void ThreadTree<T>::inThread(Node<T> *bt,Node<T> *pre){//中序線索化if(root!=NULL){inThread(bt->lchild,pre);//遞歸左子樹線索化if(bt->lchild!=NULL){//沒有左孩子bt->ltag=thread;//前驅(qū)線索bt->lchild=pre;//左孩子指針執(zhí)行前驅(qū)}if(pre->rchild!=NULL){//沒有右孩子pre->rtag=thread;//后繼線索pre->rchild=bt;//右孩子指向后繼}pre=bt;//保持pre指向bt的前驅(qū)inThread(bt->rchild,pre);//遞歸右子樹線索化} }

【查找后繼結(jié)點(diǎn)】

首先判斷當(dāng)前結(jié)點(diǎn)是否已有線索，若已有，則可直接得到后繼，若沒有，則要尋找當(dāng)前結(jié)點(diǎn)的右孩子的最左下結(jié)點(diǎn)

template<class T> Node<T> * ThreadTree<T>::findNext(Node<T> *bt){//查找結(jié)點(diǎn)bt的后繼Node<T> *q;//后繼if(bt->rtag==thread)//已有線索，直接得到后繼結(jié)點(diǎn)q=bt->rchild;else{q=bt->rchild;//工作指針q指向bt的右孩子while(q->ltag==link)//查找最左下結(jié)點(diǎn)q=q->lchild;}return q; }

【遍歷操作】

對(duì)線索鏈表進(jìn)行中序遍歷操作時(shí)，只要尋找到中序序列的第一個(gè)結(jié)點(diǎn)，然后依次訪問其后繼即可

template<class T> void ThreadTree<T>::inOrder(){//中序遍歷if(root==NULL)return;else{Node<T> *p;p=root;while(p->ltag==link)//尋找中序遍歷序列的第一個(gè)結(jié)點(diǎn)p=p->lchild;cout<<p->data;while(p->rchild!=NULL){//當(dāng)結(jié)點(diǎn)p存在后繼，依次訪問其后繼p=findNext(p);cout<<p->data;}} }

?

總結(jié)

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

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