數(shù)據(jù)結構課后習題解答第六章樹和二叉樹(編輯修改稿)
2025-04-21 03:02 本頁面
【文章內容簡介】 )) return ERROR。 //未按層序輸入p=QueueHead(Q)。q=(BTNode*)malloc(sizeof(BTNode))。if(side==39。L39。) plchild=q。else if(side==39。R39。) prchild=q。else return ERROR。 //格式不正確qdata=child。EnQueue(Q,q)。}return OK。}//CreateBitree_Triplet Status Print_Expression(Bitree T)//按標準形式輸出以二叉樹存儲的表達式{if(Tdata是字母) printf(%c,Tdata)。else if(Tdata是操作符){if(!Tlchild||!Trchild) return ERROR。 //格式錯誤if(Tlchilddata是操作符amp。amp。Tlchilddata優(yōu)先級低于Tdata){printf(()。if(!Print_Expression(Tlchild)) return ERROR。printf())。} //注意在什么情況下要加括號else if(!Print_Expression(Tlchild)) return ERROR。if(Trchilddata是操作符amp。amp。Trchilddata優(yōu)先級低于Tdata){printf(()。if(!Print_Expression(Trchild)) return ERROR。printf())。}else if(!Print_Expression(Trchild)) return ERROR。}else return ERROR。 //非法字符return OK。}//Print_Expression typedef struct{ BTNode node。 int layer。 } BTNRecord。 //包含結點所在層次的記錄類型 int FanMao(Bitree T)//求一棵二叉樹的繁茂度{int countd。 //count數(shù)組存放每一層的結點數(shù)InitQueue(Q)。 //Q的元素為BTNRecord類型EnQueue(Q,{T,0})。while(!QueueEmpty(Q)){DeQueue(Q,r)。count[]++。if(lchild) EnQueue(Q,{lchild,+1})。if(rchild) EnQueue(Q,{rchild,+1})。} //利用層序遍歷來統(tǒng)計各層的結點數(shù)h=。 //最后一個隊列元素所在層就是樹的高度for(maxn=count[0],i=1。count[i]。i++)if(count[i]maxn) maxn=count[i]。 //求層最大結點數(shù)return h*maxn。}//FanMao分析:如果不允許使用輔助數(shù)組,就必須在遍歷的同時求出層最大結點數(shù),形式上會復雜一些,你能寫出來嗎? int maxh。 Status Printpath_MaxdepthS1(Bitree T)//求深度等于樹高度減一的最靠左的結點{Bitree pathd。maxh=Get_Depth(T)。 //if(maxh2) return ERROR。 //無符合條件結點Find_h(T,1)。return OK。}//Printpath_MaxdepthS1 void Find_h(Bitree T,int h)//尋找深度為maxh1的結點{path[h]=T。if(h==maxh1){for(i=1。path[i]。i++) printf(%c,path[i]data)。exit。 //打印輸出路徑}else{if(Tlchild) Find_h(Tlchild,h+1)。if(Trchild) Find_h(Trchild,h+1)。}path[h]=NULL。 //回溯}//Find_h Status CreateBitree_SqList(Bitree amp。T,SqList sa)//根據(jù)順序存儲結構建立二叉鏈表{Bitree ptr[+1]。 //該數(shù)組儲存與sa中各結點對應的樹指針if(!){T=NULL。 //空樹return。}ptr[1]=(BTNode*)malloc(sizeof(BTNode))。ptr[1]data=[1]。 //建立樹根T=ptr[1]。for(i=2。i=。i++){if(![i]) return ERROR。 //順序錯誤ptr[i]=(BTNode*)malloc(sizeof(BTNode))。ptr[i]data=[i]。j=i/2。 //找到結點i的雙親jif(ij*2) ptr[j]rchild=ptr[i]。 //i是j的右孩子else ptr[j]lchild=ptr[i]。 //i是j的左孩子}return OK。}//CreateBitree_SqList int DescNum(Bitree T)//求樹結點T的子孫總數(shù)填入DescNum域中,并返回該數(shù){if(!T) return 1。else d=(DescNum(Tlchild)+DescNum(Trchild)+2)。 //計算公式TDescNum=d。return d。}//DescNum分析:該算法時間復雜度為O(n),:為了能用一個統(tǒng)一的公式計算子孫數(shù)目,所以當T為空指針時,要返回1而不是0. BTNode *PreOrder_Next(BTNode *p)//在先序后繼線索二叉樹中查找結點p的先序后繼,并返回指針{if(plchild) return plchild。else return prchild。}//PreOrder_Next分析:? Bitree PostOrder_Next(Bitree p)//在后序后繼線索二叉樹中查找結點p的后序后繼,并返回指針{if(prtag) return prchild。 //p有后繼線索else if(!pparent) return NULL。 //p是根結點else if(p==pparentrchild) return pparent。 //p是右孩子else if(p==pparentlchildamp。amp。pparenttag)return pparent。 //p是左孩子且雙親沒有右孩子else //p是左孩子且雙親有右孩子{q=pparentrchild。while(!qltag||!qrtag){if(!qltag) q=qlchild。else q=qrchild。} //從p的雙親的右孩子向下走到底return q。}//else}//PostOrder_Next Status Insert_BiThrTree(BiThrTree amp。T,BiThrTree amp。p,BiThrTree amp。x)//在中序線索二叉樹T的結點p下插入子樹x{if(!pltagamp。amp。!prtag) return INFEASIBLE。 //無法插入if(pltag) //x作為p的左子樹{s=plchild。 //s為p的前驅pltag=Link。plchild=x。q=x。while(qlchild) q=qlchild。qlchild=s。 //找到子樹中的最左結點,并修改其前驅指向sq=x。while(qrchild) q=qrchild。qrchild=p。 //找到子樹中的最右結點,并修改其前驅指向p}else //x作為p的右子樹{s=prchild。 //s為p的后繼prtag=Link。
環(huán)評公示相關推薦
鄂ICP備17016276號-1