數據結構例程――用二叉樹遍歷思想解決問題

本文是數據結構基礎系列(6)：樹和2叉樹中第10課時2叉樹的遍歷的例程。

【利用2叉樹遍歷思想解決問題】(請利用2叉樹算法庫)
　　假定2叉樹采取2叉鏈存儲結構存儲，分別實現以下算法，并在程序中完成測試：
　　（1）計算2叉樹節點個數；
　　（2）輸出所有葉子節點；
　　（3）求2叉樹b的葉子節點個數
　　（4）設計1個算法Level(b,x,h)，返回2叉鏈b中data值為x的節點的層數。
　　（5）判斷2叉樹是不是類似（關于2叉樹t1和t2類似的判斷：①t1和t2都是空的2叉樹，類似；②t1和t2之1為空，另外一不為空，則不類似；③t1的左子樹和t2的左子樹是類似的，且t1的右子樹與t2的右子樹是類似的，則t1和t2類似。）

［參考解答］（btreee.h見算法庫）
　　（1）計算2叉樹節點個數；

#include #include "btree.h" int Nodes(BTNode *b) { if (b==NULL) return 0; else return Nodes(b->lchild)+Nodes(b->rchild)+1; } int main() { BTNode *b; CreateBTNode(b,"A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))"); printf("2叉樹節點個數: %d ", Nodes(b)); DestroyBTNode(b); return 0; }

（2）輸出所有葉子節點；

#include <stdio.h> #include "btree.h" void DispLeaf(BTNode *b) { if (b!=NULL) { if (b->lchild==NULL && b->rchild==NULL) printf("%c ",b->data); else { DispLeaf(b->lchild); DispLeaf(b->rchild); } } } int main() { BTNode *b; CreateBTNode(b,"A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))"); printf("2叉樹中所有的葉子節點是: "); DispLeaf(b); printf(" "); DestroyBTNode(b); return 0; }

（3）求2叉樹b的葉子節點個數

#include <stdio.h> #include "btree.h" int LeafNodes(BTNode *b) //求2叉樹b的葉子節點個數 { int num1,num2; if (b==NULL) return 0; else if (b->lchild==NULL && b->rchild==NULL) return 1; else { num1=LeafNodes(b->lchild); num2=LeafNodes(b->rchild); return (num1+num2); } } int main() { BTNode *b; CreateBTNode(b,"A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))"); printf("2叉樹b的葉子節點個數: %d ",LeafNodes(b)); DestroyBTNode(b); return 0; }

（4）設計1個算法Level(b,x,h)，返回2叉鏈b中data值為x的節點的層數。

#include #include "btree.h" int Level(BTNode *b,ElemType x,int h) { int l; if (b==NULL) return 0; else if (b->data==x) return h; else { l=Level(b->lchild,x,h+1); if (l==0) return Level(b->rchild,x,h+1); else return l; } } int main() { BTNode *b; CreateBTNode(b,"A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))"); printf("值為K的節點在2叉樹中出現在第 %d 層上n",Level(b,K,1)); DestroyBTNode(b); return 0; }

（5）判斷2叉樹是不是類似（關于2叉樹t1和t2類似的判斷：①t1和t2都是空的2叉樹，類似；②t1和t2之1為空，另外一不為空，則不類似；③t1的左子樹和t2的左子樹是類似的，且t1的右子樹與t2的右子樹是類似的，則t1和t2類似。）

#include #include "btree.h" int Like(BTNode *b1,BTNode *b2) { int like1,like2; if (b1==NULL && b2==NULL) return 1; else if (b1==NULL || b2==NULL) return 0; else { like1=Like(b1->lchild,b2->lchild); like2=Like(b1->rchild,b2->rchild); return (like1 & like2); } } int main() { BTNode *b1, *b2, *b3; CreateBTNode(b1,"B(D,E(H(J,K(L,M(,N)))))"); CreateBTNode(b2,"A(B(D(,G)),C(E,F))"); CreateBTNode(b3,"u(v(w(,x)),y(z,p))"); if(Like(b1, b2)) printf("b1和b2類似 "); else printf("b1和b2不類似 "); if(Like(b2, b3)) printf("b2和b3類似 "); else printf("b2和b3不類似 "); DestroyBTNode(b1); DestroyBTNode(b2); DestroyBTNode(b3); return 0; }

注：用”A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))”創建的用于測試的2叉樹以下――

生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈