資源描述:
《樹(shù)和二叉樹(shù)ppt課件.ppt》由會(huì)員上傳分享,免費(fèi)在線閱讀,更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。
1、應(yīng)用第五章樹(shù)和二叉樹(shù)10/7/20211二叉樹(shù)在一般情況下無(wú)法直接找到某結(jié)點(diǎn)在某種遍歷序列中的前驅(qū)和后繼結(jié)點(diǎn)。若增加指針域來(lái)存放前驅(qū)和后繼結(jié)點(diǎn)信息,將大大降低存儲(chǔ)空間的利用率(密度)??疾靚個(gè)結(jié)點(diǎn)的二叉樹(shù),其中有n+1個(gè)空指針域,它們可以被用來(lái)存放“線索”加了線索的二叉樹(shù)稱(chēng)為線索二叉樹(shù)。一、線索二叉樹(shù)10/7/20212線索二叉樹(shù)結(jié)點(diǎn)的描述typedefintdatatype;typedefstructnode{intltag,rtag;datatypedata;structnode*lchild,*rchild;}bithptr;bithptr*pre;
2、lchildltagrtagdatarchild標(biāo)志位如果為0,表示指針指向孩子結(jié)點(diǎn),為1表示指針為線索10/7/202130A00B00E11C11D11F00G01H11I1NULLNULLt10/7/20214中序線索化算法INTHREAD(bithptr*p,bithptr*pre)//p為當(dāng)前結(jié)點(diǎn),pre為p的前驅(qū)結(jié)點(diǎn),開(kāi)始調(diào)用時(shí)p為根結(jié)點(diǎn)指針,pre為NULL{if(p!=NULL){INTHREAD(p->lchild,pre);//左子樹(shù)線索化//若當(dāng)前結(jié)點(diǎn)的左子樹(shù)為空,則建立指向其前驅(qū)結(jié)點(diǎn)的前驅(qū)線索if(p->lchild==NULL){
3、p->ltag=1;p->lchild=pre;}elsep->ltag=0;//若前驅(qū)結(jié)點(diǎn)不為空,且其右孩子為空,則建立該前驅(qū)結(jié)點(diǎn)指向當(dāng)前結(jié)點(diǎn)的后續(xù)線索if(pre!=NULL&&pre->rchild==NULL){pre->rtag=1;pre->rchild=p;}elsep->rtag=0;pre=p;//中序向前遍歷一個(gè)結(jié)點(diǎn)INTHREAD(p->rchild,pre);}}10/7/202151、若*p的右子樹(shù)為空,則p->rchild為右線索,直接指向*p的中序后繼結(jié)點(diǎn)。2、若*p的右子樹(shù)非空,則*p的中序后繼必是其右子樹(shù)中第一個(gè)遍歷到的結(jié)
4、點(diǎn),也就是從*p的右孩子開(kāi)始,沿左指針鏈往下查找,直到找到一個(gè)沒(méi)有左孩子的結(jié)點(diǎn)為止。中序線索二叉樹(shù)中,查找指定結(jié)點(diǎn)*p的中序后繼結(jié)點(diǎn)10/7/20216pR1R2Rk最左下結(jié)點(diǎn)10/7/20217中序線索二叉樹(shù)中求中序后繼結(jié)點(diǎn)的算法bithptr*INORDERNEXT(bithptr*p){bithptr*q;if(p->rtag==1)return(p->rchild);else{q=p->rchild;while(q->ltag==0)q=q->lchild;return(q);}}10/7/202181、若*p的左子樹(shù)為空,則p->lchild為左
5、線索,直接指向*p的中序前驅(qū)結(jié)點(diǎn)。2、若*p的左子樹(shù)非空,則從*p的左孩子出發(fā),沿右指針鏈往下查找,直到找到一個(gè)沒(méi)有右孩子的結(jié)點(diǎn)為止。中序線索二叉樹(shù)中,查找指定結(jié)點(diǎn)*p的中序前驅(qū)結(jié)點(diǎn)10/7/20219pR1R2Rk最右下結(jié)點(diǎn)10/7/202110線索二叉樹(shù)的遍歷算法TRAVERSEINTHREAD(bithptr*p){if(p!=NULL){while(p->ltag==0)p=p->lchild;do{printf(“t%d”,p->data);p=INORDERNEXT(p);}while(p!=NULL);}}10/7/202111線索二叉
6、樹(shù)的結(jié)點(diǎn)插入算法INSERTRIGHT(bithptr*p,bithptr*q){bithptr*s;s=INORDERNEXT(p);q->ltag=1;q->lchild=p;q->rtag=p->rtag;q->rchild=p->rchild;p->rtag=0;p->rchild=q;if((s!=NULL)&&(s->ltag==1))s->lchild=q;}10/7/202112二叉排序樹(shù)又稱(chēng)為二叉查找樹(shù),其定義為:二叉排序樹(shù)或者是一棵空樹(shù),或者是具有如下性質(zhì)的二叉樹(shù):1、若它的左子樹(shù)非空,則左子樹(shù)上所有結(jié)點(diǎn)的值均小于根結(jié)點(diǎn);2、若它的右左
7、子樹(shù)非空,則右子樹(shù)上所有結(jié)點(diǎn)的值均大于根結(jié)點(diǎn);3、左、右子樹(shù)本身又各是一棵二叉樹(shù)。二、二叉排序樹(shù)10/7/202113caozhaodingchenwangmaxiaduni10/7/202114二叉排序樹(shù)結(jié)點(diǎn)的結(jié)構(gòu)描述typedefstructnode{datatypedata;structnode*lchild,*rchild;}bitree;10/7/202115二叉排序樹(shù)的結(jié)點(diǎn)插入//向一個(gè)二叉排序樹(shù)中插入一個(gè)結(jié)點(diǎn)svoidINSERT(bitree*b,bitree*s){if(b==NULL)b=s;elseif(s->data==b->dat
8、a)return;//不做任何插入操作elseif(s->data