【正文】 n有右兄弟的條件是，它不僅雙親的從右邊的第一個子女，即(n1)%k!=0，其右兄弟編號是n+1。，在具有n(n≥1)個結(jié)點的m叉樹中，有n(m1)+1個指針域是空的。解：具有n個結(jié)點的m叉樹共用n*m個指針。除根結(jié)點外，其余n1個結(jié)點均有指針?biāo)福士罩羔様?shù)為n*m(n1)=n*(m1)+1。：(1)先序序列與后序序列相同；(2)中序序列與后序序列相同；(3)先序序列與中序序列相同；(4)中序序列與層次遍歷序列相同。解：(1)若先序序列與后序序列相同，則或為空樹，或為只有根結(jié)點的二叉樹。(2)若中序序列與后序序列相同，則或為空樹，或為任一結(jié)點至多只有左子樹的二叉樹。(3)若先序序列與中序序列相同，則或為空樹，或為任一結(jié)點至多只有右子樹的二叉樹。(4)若中序序列與層次遍歷序列相同，則或為空樹，或為任一結(jié)點至多只有右子樹的二叉樹。，中序遍歷序列為DBGEHJACIF。請畫出這棵二叉樹。解：按層次遍歷，第一個結(jié)點（樹不空）為根，該結(jié)點在中序序列中把序列分成左右兩部分——左子樹和右子樹。若左子樹不空，層次序列中第二個結(jié)點為左子樹的根；若左子樹為空，則層次序列中第二個結(jié)點為右子樹的根。對右子樹分析類似。層次序列的特點是：從左到右每個結(jié)點或是當(dāng)前情況下子樹的根或是葉子。：ABCDEFGHIJKL。請寫出后序遍歷該二叉樹的訪問結(jié)點序列。解：HIDJKEBLFGCA。，后序遍歷序列為：GDBEIHFCA。(1)試畫出該二叉樹；(2)試畫出該二叉樹的中序線索樹；(3)試畫出該二叉樹對應(yīng)的森林。解：（1）（2）略（3），字符集為A、B、C、D，設(shè)計一套二進制編碼，使得上述正文的編碼最短。解：字符A、B、C、D出現(xiàn)的次數(shù)為3。其哈夫曼編碼如下：A：1，B：000，C：01，D：001。其哈夫曼樹為：，寫出計算該算術(shù)表達(dá)式值的算法。解：typedef struct Node{ ElemType data。 float val。 char optr。//只取+、*、/ struct Node *lchild,*rchild }BiNode,*BiTree。float PostEval(BiTree t){//以后序遍歷算法求以二叉樹表示的算術(shù)表達(dá)式的值 float lv,rv。 if(t!=NULL){ lv=PostEval(tlchild)。// rv=PostEval(trchild)。// switch(toptr){ case 39。+39。: value=lv+rv。break。 case 39。39。:value=lvrv。break。 case 39。*39。:value=lv*rv。break。 case 39。/39。:value=lv/rv。break。 } }return value。}，編寫判斷給定的二叉樹是否相似的算法。所謂二叉樹t1和t2相似指的是：t1和t2都是空樹；或者t1和t2的根結(jié)點是相似的，以及t1的左子樹和t2的左子樹是相似的且t1的右子樹和t2的右子樹是相似的。解：int Like(BiTree t1, BiTree t2){ int like1,like2。 if(t1==NULLamp。amp。t2==NULL)return 1。 else if(t1==NULL||t2==NULL)return 0。 else{ like1=Like(t1lchild,t2lchild)。 like2=Like(t1rchild,t2rchild)。 return (like1 amp。 like2)。 }}，編寫遞歸算法，將二叉樹中所有結(jié)點的左、右子樹相互交換。解：void Exchange(BiTree amp。t){ if(t){ BiTree s。 s=tlchild。tlchild=trchild。trchild=s。 Exchange(tlchild)。Exchange(trchild)。}}。解：int Depth(PTree t){ int maxdepth=0,i,temp,f。 for(i=0。i。i++){ temp=0。f=i。 while(f1){temp++。f=[f].parent。} if(tempmaxdepth)maxdepth=temp。 } return maxdepth。}，編寫按層次遍歷方式計算二叉樹結(jié)點個數(shù)的算法。解：int Level(BiTree t){ int num=0。 LinkQueue Q。 BiTree p。 if(t){ InitQueue(Q)。EnQueue(Q,t)。 while(!QueueEmpty(Q)){ DeQueue(Q,p)。num++。 if(plchild)EnQueue(Q,plchild)。 if(prchild)EnQueue(Q,prchild)。 }//while }//if return num。}，利用葉子結(jié)點中的空指針域?qū)⑺腥~子結(jié)點鏈接為一個帶有頭結(jié)點的雙向鏈表，算法返回頭結(jié)點的指針。解：BiTree head,pre。//全局變量鏈表頭指針head，prevoid CreateLeafList(BiTree t){ if(t){ CreateLeafList(tlchild)。//中序遍歷左子樹 if(tlchild==NULLamp。amp。trchild==NULL)//葉子結(jié)點 if(head==NULL){//第一個葉子結(jié)點 head=new BiTNode。 //生成頭結(jié)點 headlchild=NULL。 headrchild=t。//頭結(jié)點的左鏈為空，右鏈指向第一個葉子結(jié)點 tlchild=head。pre=t。//第一個葉子結(jié)點左鏈指向頭結(jié)點，pre指向當(dāng)前葉子結(jié)點 } else{prerchild=t。tlchild=pre。pre=t。}。 CreateLeafList(trchild)。 prerchild=NULL。 } }，編寫算法，按照括號表示法輸出二叉樹的所有結(jié)點。解：其過程是：對于非空二叉樹t，先輸出其元素值，當(dāng)存在左孩子結(jié)點或右孩子結(jié)點時，輸出一個“（”符號，然后遞歸處理左子樹，輸出一個“，”符號，遞歸處理右子樹，最后輸出一個“）”符號。void DispBiTree(BiTree t){ if(t){ printf(%c,tdata)。 if(tlchild!=NULL||trchild!=NULL){ printf(()。 DispBiTree(tlchild)。 if(trchild!=NULL) printf(,)。 DispBiTree(trchild)。 printf())。 } }}，編寫算法，輸出二叉樹的所有葉子結(jié)點。解：void DispLeaf(BiTree t){ if(t){ if(tlchild==NULLamp。amp。trchild==NULL)printf(%c ,tdata)。 DispLeaf(tlchild)。 DispLeaf(trchild)。 }}，編寫算法，輸出值為x的結(jié)點的所有祖先。解：int Ancestor(BiTree t,ElemType x){ if(t==NULL)return 0。 if(tdata==x)return 1。 if(Ancestor(tlchild,x)||Ancestor(trchild,x)){ printf(%c ,tdata)。 return 1。 }}，編寫算法，輸出所有葉子結(jié)點到根結(jié)點的路徑。解：利用后序非遞歸遍歷的特點，將其中訪問結(jié)點改為判斷結(jié)點是否為葉子結(jié)點，若是，輸出棧中所有結(jié)點值void AllPathAncestor(BiTree t){ BiTNode *St[100]。 BiTNode *p。 int flag,i,top=1。//棧指針初始化 if(t){ do{ while(t){ //t的所有左結(jié)點進棧 top++。 St[top]=t。 t=tlchild。 } p=NULL。 //p指向棧頂結(jié)點的前一個已訪問的結(jié)點 flag=1。 //設(shè)置t的訪問標(biāo)記為已訪問過 while(top!=1amp。amp。flag){ t=St[top]。 //出棧 if(trchild==p){ if(tlchild==NULLamp。amp。trchild==NULL){ //若為葉子結(jié)點 for(i=top。i0。i) printf(%c,St[i]data)。 //輸出棧中所有結(jié)點 printf(%c\n,St[0]data)。 } top。 p=t。//p指向剛訪問過的結(jié)點 } else{ t=trchild。 //t指向右孩子結(jié)點 flag=0。 //設(shè)置未訪問標(biāo)記 } } }while(top!=1)。 printf(\n)。 }}，將二叉樹的順序存儲結(jié)構(gòu)轉(zhuǎn)化為二叉鏈表存儲結(jié)構(gòu)。解：typedef char ElemType。typedef struct {//結(jié)點結(jié)構(gòu) ElemType *data。//數(shù)據(jù)元素 int n。//左右孩子指針}SqBTree。BiTree Trans(SqBTree a,int i){//數(shù)據(jù)元素放在數(shù)組a的從下標(biāo)為1開始的單元中 BiTree t。 if(i)return NULL。//當(dāng)i大于a的結(jié)點個數(shù) if([i]==39。39。)return NULL。//當(dāng)i對于的結(jié)點為空 t=new BiTNode。 tdata=[i]。 tlchild=Trans(a,2*i)。 trchild=Trans(a,2*i+1)。 return t。}。解：在后序序列中，若結(jié)點p有右子女，則右子女是其前驅(qū)，若無右子女而有左子女，則左子女是其前驅(qū)。若p左右子女均無，設(shè)其中序左線索指向其祖先結(jié)點f（p是f右子樹中按中序遍歷的第一個結(jié)點），若f有左子女，則其右子女是p在后序下的前驅(qū)，若f無左子女，則順其前驅(qū)找雙親的雙親，一直繼續(xù)到雙親有左子女（這時左子女是p的前驅(qū)）。還有一種情況，若p是中序遍歷的第一個結(jié)點，p在中序和后序下均無前驅(qū)。BiThrTree InPostPre(BiThrTree t,BiThrTree p){BiThrNode *q。 if(pRTag==0)q=prchild。//若p有右子女，則右子女是其后序前驅(qū) else if(pLTag==0)q=plchild。 //若p無右子女而有左子女，則左子女是其后序前驅(qū) else if(plchild==NULL)q=NULL。//p是中序序列第一個結(jié)點，無后序前驅(qū) else {//順左線索向上找p的祖先，若存在，再找祖先的左子女 while(pLTag==1amp。amp。plchild!=NULL)p=plchild。 if(pLTag==0)q=plchild。 //p結(jié)點的祖先的左子女是其后序前驅(qū) else q=NULL。 //僅右單支樹（p是葉子），已上到根結(jié)點，p結(jié)點無后序前驅(qū) } return q。}。解：BiThrTree LeftMost(BiThrTree t){//求結(jié)點t的最左子孫的左線索BiThrTree p=t。 while(pLTag==0)p=plchild。 if(plchild!=NULLamp。amp。plchild!=t)return(plchild)。 else return NULL。}BiThrTree RightMost(BiThrTree t){//求結(jié)點t的最右子孫的右線索 BiThrTree p=t。 while(pRTag==0)p=prchild。 if(prchild!=NULLamp。amp。prchild!=t)return(prchild)。 else return NULL。}int ISRightChild(BiThrTree t,BiThrTree amp。father){//若t是father的右孩子，返回1，否則返回0 father=LeftMost(t)。 if(fatheramp。amp。fatherrchild==t)return 1。 else return 0。}void PostOrderInThr(BiThrTree t){//后