樹(shù)和二叉樹(shù)ppt課件.ppt

樹(shù)和二叉樹(shù)ppt課件.ppt

ID:58842295

大?。?66.50 KB

頁(yè)數(shù):45頁(yè)

時(shí)間:2020-09-30

樹(shù)和二叉樹(shù)ppt課件.ppt_第1頁(yè)
樹(shù)和二叉樹(shù)ppt課件.ppt_第2頁(yè)
樹(shù)和二叉樹(shù)ppt課件.ppt_第3頁(yè)
樹(shù)和二叉樹(shù)ppt課件.ppt_第4頁(yè)
樹(shù)和二叉樹(shù)ppt課件.ppt_第5頁(yè)
資源描述:

《樹(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

當(dāng)前文檔最多預(yù)覽五頁(yè),下載文檔查看全文

此文檔下載收益歸作者所有

當(dāng)前文檔最多預(yù)覽五頁(yè),下載文檔查看全文
溫馨提示:
1. 部分包含數(shù)學(xué)公式或PPT動(dòng)畫(huà)的文件,查看預(yù)覽時(shí)可能會(huì)顯示錯(cuò)亂或異常,文件下載后無(wú)此問(wèn)題,請(qǐng)放心下載。
2. 本文檔由用戶(hù)上傳,版權(quán)歸屬用戶(hù),天天文庫(kù)負(fù)責(zé)整理代發(fā)布。如果您對(duì)本文檔版權(quán)有爭(zhēng)議請(qǐng)及時(shí)聯(lián)系客服。
3. 下載前請(qǐng)仔細(xì)閱讀文檔內(nèi)容,確認(rèn)文檔內(nèi)容符合您的需求后進(jìn)行下載,若出現(xiàn)內(nèi)容與標(biāo)題不符可向本站投訴處理。
4. 下載文檔時(shí)可能由于網(wǎng)絡(luò)波動(dòng)等原因無(wú)法下載或下載錯(cuò)誤,付費(fèi)完成后未能成功下載的用戶(hù)請(qǐng)聯(lián)系客服處理。