軟件技術(shù)基礎(chǔ)課件

2.5.5穿線二叉穿線二叉樹的概遍歷二叉樹實為把非線性結(jié)構(gòu)線性化了，而這種線性有序的信息是否可以在結(jié)構(gòu)中保持住呢？即保持其。穿線二叉樹為我們提供了肯定的答案。穿線二叉樹是二叉樹的一種方式，是二叉樹以一個新結(jié)點和刪除一個指定結(jié)點等運算。18-在原二叉樹上建立線建立線索的過程就是線性化的過，即邊遍歷邊建立線索，遍歷完成，線索建好。根據(jù)二叉樹的鏈?zhǔn)?結(jié)構(gòu)我們注意到：當(dāng)一顆有n個結(jié)點的二叉樹，便有n+個指針域存放著空NU。這是因為，n各結(jié)點一共有2n個指針域，除根結(jié)點外，每個結(jié)點有且僅有一個指向它的指針，于是共有1個指針，即只有n個指針域被有效使用。那些空值的指針域，正好被用來構(gòu)造穿線二叉樹。18-由此得到具體做法是，利用空值域裝線索，若一個結(jié)lchid存放前驅(qū)線索；同樣若結(jié)點的右孩子為空，則用空值域chid放后繼線索。lag和fagtemplatestructTd;//數(shù)據(jù)intlflag;//左標(biāo)志intrflag;//右標(biāo)志

=0，lchild指向結(jié)點的左子=1，lchild指向結(jié)點的前驅(qū)線=0，rchild指向結(jié)點的右子結(jié)=1，rchild指向結(jié)點的后繼線TTnode*lchild;//左指針TTnode*rchild;//右指針}18-18-中序穿線二叉樹的構(gòu)算法思 到的結(jié)點序號（指針）填入，并置右標(biāo)域為1 到的結(jié)點序號（指針）填入，并置左標(biāo)域為118-template<classstaticin_threaded(TTnode<T>*p,TTnode<T>{{in_threaded(p->lchild,//若上 到的結(jié)點的右指針為//則將當(dāng) 到的結(jié)點序號填入，并置右標(biāo)志域為if((*h!=NULL)&&((*h)-{(*h)->rchild=p;(*h)->rflag=1;//若當(dāng) 到的結(jié)點的左指針為//則將上 到的結(jié)點序號填入，并置左標(biāo)志域為if(p-{p->lchild=*h;p-in_threaded(p->rchild,}return}18-中序穿線二叉樹的遍算法思首先，從二叉樹的根結(jié)點開始該葉子結(jié)點即為中序序列的第一個結(jié)點然后從中序序列的第一個結(jié)點開始掃描，依次找出中序列中的后件。其規(guī)則如下若當(dāng)前結(jié)點的右標(biāo)志值為，則當(dāng)前結(jié)點的右指針域值為其后件的序號。若當(dāng)前結(jié)點的右標(biāo)志值為，則沿右子樹的左鏈進行搜索，直到發(fā)現(xiàn)某個結(jié)點的左標(biāo)志值為1且左指針值不空為止，該結(jié)點即為當(dāng)前結(jié)點的后件。18-中序線索二叉鏈表的遍template<classvoid{TTnode<T>*p;if(BT==NULL)return;二叉鏈表為空while(p->lflag==0)p=p->lchild;//沿左鏈找到葉子結(jié)點cout<<p->d<<““; while(p->rchild!=NULL)//沿右鏈掃描后件{if(p->rflag==1)p=p- //沿右子樹的左鏈掃whil