【正文】 =ptriht。//該結點從B表相應行鏈表中摘下。 Pbt=pb。pb=pbright。//B表移至下一結點 //以下是將pbt插入A表的相應列鏈表中 j=pbtcol。pt=cha[j]。pre=pt。 while(ptdown !=cha[j]amp。amp。ptdownrowptbrow) {pre=pt。pt=ptdown} predown=pbt。pbtdown=pt。 //以下是將pbt插入A表相應行鏈表中 i=pbtright。pt=cha[i]。pre=pt。 while(ptright !=cha[i]amp。amp。ptrightcolptbcol) {pre=pt。pt=ptright。} preright=ptb。 ptbright=pt。 }//end of “if (pbcolpacol) else if(pacol=pbcol)//處理兩表中行列相同的非0元素 {v=padata+pbdata。 if(v !=0) {padata+=pbdata。pa=paright。 將pb從行鏈表中刪除；pb=pbright。 } else{將pa,pb從鏈表中刪除。然后 pa=paright。 pb=pbright。 } (1) head((p,h,w))=p(2) tail((b,k,p,h))=(k,p,h)(3) head(((a,b),(c,d)))=(a,b)(4) tail(((a,b),(c,d)))=((c,d))(5) head(tail(((a,b),(c,d)))=(c,d)(6) tail(head(((a,b),(c,d))))=(b) (1) (2) (1) 第6章 樹和二叉樹（參考答案）(1)根結點a 三個結點的樹的形態(tài)： 三個結點的二叉樹的形態(tài)： （2） （3） （1） （1） （2） （4） （5）6．3 設樹的結點數(shù)是n，則n=n0+n1+n2+……+nm+ (1)設樹的分支數(shù)為B，有n=B+1n=1n1+2n2+……+mnm+1 (2)由（1）和（2）有：n0=n2+2n3+……+(m1)nm+1(1) ki1 (i為層數(shù))(2) (n2)/k+1(3) (n1)*k+i+1(4) (n1)%k !=0。 其右兄弟的編號 n+1（1）順序存儲結構 1 2 3 4 5 6 7 8 9 10 11 12 13 14ABCDEFGH注：為空結點 A C B ^^ E ^ F ^ ^ D^ H ^^ G ^(1) 前序 ABDGCEFH(2) 中序 DGBAECHF(3) 后序 GDBEHFCA(1) 空二叉樹或任何結點均無左子樹的非空二叉樹(2) 空二叉樹或任何結點均無右子樹的非空二叉樹(3) 空二叉樹或只有根結點的二叉樹int height(bitree bt)// bt是以二叉鏈表為存儲結構的二叉樹，本算法求二叉樹bt的高度 { int bl,br。 // 局部變量，分別表示二叉樹左、右子樹的高度 if (bt==null) return(0)。 else { bl=height(btlchild)。 br=height(btrchild)。 return(blbr? bl+1: br+1)。 // 左右子樹高度的大者加1（根） } }// 算法結束 void preorder(cbt[],int n,int i)。 // cbt是以完全二叉樹形式存儲的n個結點的二叉樹，i是數(shù) // 組下標，初始調用時為1。本算法以非遞歸形式前序遍歷該二叉樹 { int i=1,s[],top=0。 // s是棧，棧中元素是二叉樹結點在cbt中的序號 // top是棧頂指針，?？諘rtop=0 if (n=0) { printf(“輸入錯誤”)。exit（0）；}while (i=n ||top0) { while(i=n) {visit(cbt[i])。 // 訪問根結點 if (2*i+1=n) s[++top]=2*i+1。 //若右子樹非空，其編號進棧 i=2*i。// 先序訪問左子樹 } if (top0) i=s[top]。 // 退棧，先序訪問右子樹 } // END OF while (i=n ||top0) }// 算法結束 //以下是非完全二叉樹順序存儲時的遞歸遍歷算法，“虛結點”用‘*’表示 void preorder(bt[],int n,int i)。 // bt是以完全二叉樹形式存儲的一維數(shù)組，n是數(shù)組元素個數(shù)。i是數(shù) // 組下標，初始調用時為1。 { if (i=n amp。amp。 bt[i]!=’*’) { visit(bt[i])。 preorder(bt,n,2*i)。 preorder(bt,n,2*i+1)。 }// 算法結束 int equal(bitree T1,bitree T2)。 // T1和T2是兩棵二叉樹，本算法判斷T1和T2是否等價 // T1和T2都是空二叉樹則等價 // T1和T2只有一棵為空，另一棵非空，則不等價 // T1和T2均非空，且根結點值相等，則比較其左、右子樹 {if (T1==null amp。amp。 T2==null) return(1)。 // 同為空二叉樹 else if (T1==null || T2==null) return(0)。 // 只有一棵為空 else if (T1data!=T2data) return(0)。// 根結點值不等 else return(equal(T1lchild,T2lchild)amp。amp。equal(T1rchild,T2rchild)) //判左右子樹等價}// 算法結束 6．11void levelorder (bitree ht)。{本算法按層次遍歷二叉樹ht}{if (ht!=null) {initqueue(q)。 {處始化隊列，隊列元素為二叉樹結點的指針} enqueue(q,ht)。 {根結點指針入隊列}while (!empty(q)) { p=delqueue(q)。 visit(p)。 // 訪問結點 if (plchild!=null) enqueue (q,plchild)。 //若左子女非空，則左子女入隊列 if (prchild!=null) enqueue (q,prchild)； //若右子女非空，則右子女入隊列 }}} // 算法結束 6．12void preorder (bitree *t)。 (前序非遞歸遍歷){ bitree *s[n+1]。 // s是指針數(shù)組，數(shù)組中元素為二叉樹節(jié)點的指針top=0。while (t!=null || top!=0) { while (t!=null) { visit(*t)。 s[++top]=t。 t=tlchild } if (top!=0) { t=s[top]。 t=trchild。}}} // 算法結束 void inorder (bitree *t)。 (中序非遞歸遍歷){bitree *s[n+1]。top=0。while ((t!=null || top!=0){ while (t!=null) { s[++top]=t。 t=tlchild } if (top!=0) { t=s[top]。 visit(*t)。 t=trchild。 }} // 算法結束 void postorder (bitree *t)。 (后序非遞歸遍歷){typedef struct node { bitree *t。 tag:0..1 } stack。stack s[n+1] 。top=0。while (t || top){ while (t) { s[++top].t=t。 s[top].tag=0。 t=tlchild。 } while (top amp。amp。 s[top].tag==1) { printf(s[top].tdata:3)。}if (top) { s[top].tag=1。 t=s[top].trchild 。}} } // 算法結束 bitree *dissect(bitree **t,ElemType x)// 二叉樹t至多有一個結點的數(shù)據(jù)域為x，本算法拆去以x為根的子樹 // 拆開后的第一棵樹用t表示，成功拆開后返回第二棵二叉樹{bitree *p,*find。 if (*t!=null) { if ((*t)data==x) // 根結點數(shù)據(jù)域為x {p=*t。 *t=null。 return(p)。 } else {find=(dissect(amp。(*t)lchild),x)。 // 在左子樹中查找并拆開 // 若在左子樹中未找到，就到右子樹中查找并拆開 if (!find) find=(dissect(amp。(*t)rchild),x)。 return(find)。 } } else return(null)。 // 空二叉樹 } // 算法結束 int search(bitree t,ElemType x)// 設二叉樹t中，值為x的結點至多一個，本算法打印x的所有祖先 // 算法思想是，借助后序非遞歸遍歷，用棧裝遍歷過程的結點，當查到 // 值為x的結點時，棧中元素都是x的祖先 { typedef struct { bitree p。 int tag。 }snode。 snode s[]。 int top=0。 while (t amp。amp。 tdata !=x || top){ while (t amp。amp。 tdata !=x) // 沿左分支向下 { s[++top].p=t。 s[top].tag=0。 t=tlchild。 } if (tdata==x) // {for (i=1。i=top。++i) printf(“%c\n”,s[i].pdata)。// 輸出，設元素為字符 return(1)。 } elsewhile (top0 amp。amp。 s[top].tag==1) top。//退出右子樹已訪問的結點 if (top0) // 置訪問標志1，訪問右子樹 {s[top].tag=1。t=s[top].p。 t=trchild。 }} return(0)。 // 沒有值為x的結點 } // 算法結束 中序序列BDCEAFHGA后序序列DECBHGFAFBGCDHE前序序列 ABCDEFGHA 后序線索樹： BCDEFHE null只有空指針處才能加線索。線索鏈表： 0 A 0 0 C 0 0 B 1 0 F 1 1 E 1 1 0 0 1 H