二叉樹的建立與遍歷葉子結(jié)點的數(shù)目以及樹的深度的求法采用遞歸求解

1、是我個人寫的，很簡單的記錄下來了，呵呵呵。我的百度空間:/heihei_shaweiwei/blog/item/eec5a3de6bb28c.html#include using namespace std;/定義樹的結(jié)構(gòu)typedef struct _binTree char data; _binTree *lNode,*rNode;binTree;/創(chuàng)建二叉樹void createT(binTree *&rootNode,binTree *tempNode) if(rootNode=NULL) rootNode=tempNode; return; els

2、e if(rootNode-data tempNode-data) createT(rootNode-lNode,tempNode); else if(rootNode-data data) createT(rootNode-rNode,tempNode); /打印已創(chuàng)建的數(shù)void printT(binTree *rootNode) if(rootNode=NULL)return ; else printT(rootNode-lNode); coutdatarNode); /先序遍歷二叉樹void preTraverse(binTree *rootNode) if(rootNode=NULL

3、)return ; else coutdatalNode); printT(rootNode-rNode); /中序遍歷二叉樹void midTraverse(binTree *rootNode) if(rootNode=NULL)return ; else printT(rootNode-lNode); coutdatarNode); /后序遍歷二叉樹void lastTraverse(binTree *rootNode) if(rootNode=NULL)return ; else printT(rootNode-lNode); printT(rootNode-rNode); coutda

4、talNode)+nodeTotal(rootNode-rNode); /計算二叉樹的深度int treeDepth(binTree *rootNode) if(rootNode=NULL)return -1; else int lH=treeDepth(rootNode-lNode); int rH=treeDepth(rootNode-rNode); if(lHrH)return lH+1; return rH+1; /計算葉子結(jié)點的個數(shù)int leafTotal(binTree *rootNode) if(rootNode=NULL)return 0; else if(rootNode-

5、lNode=NULL & rootNode-rNode=NULL)return 1; else int lH=leafTotal(rootNode-lNode); int rH=leafTotal(rootNode-rNode); return rH+lH; int main() binTree *rootNode,*tNode; rootNode=NULL; tNode=NULL; char ch; cout按照下面給出的順序進行輸入構(gòu)建二叉樹：endlF D B E A C J H K G I Lch; while(ch!=0) tNode=new binTree; tNode-data=

6、ch; tNode-lNode=NULL; tNode-rNode=NULL; createT(rootNode,tNode); cinch; if(rootNode=NULL) coutTree is NULL.endl; else cout正常輸出二叉樹的各節(jié)點數(shù)據(jù)：; printT(rootNode); coutendl; cout先序遍歷二叉樹的各節(jié)點數(shù)據(jù)：; preTraverse(rootNode); coutendl; cout中序遍歷二叉樹的各節(jié)點數(shù)據(jù)：; midTraverse(rootNode); coutendl; cout后序遍歷二叉樹的各節(jié)點數(shù)據(jù)：; lastTrav

7、erse(rootNode); coutendl; cout二叉樹的深度為：treeDepth(rootNode)endl; cout二叉樹的結(jié)點的個數(shù)為：nodeTotal(rootNode)endl; cout二叉樹的葉子結(jié)點的個數(shù)為：leafTotal(rootNode)endl; return 0;在vc6.0和dev-C+上都可以順利運行，可以看一下 啊，呵呵。 !#include using namespace std;/*/二叉樹結(jié)點類的定義templatestruct BTNode T data; BTNode * Lchild,*Rchild; BTNode(T nodeVa

8、lue = T(),BTNode* leftNode = NULL,BTNode* rightNode = NULL ) :data(nodeValue),Lchild(leftNode),Rchild(rightNode) /可選擇參數(shù)的默認構(gòu)造函數(shù);/*/二叉樹的建立template void createBinTree(BTNode * &root ) BTNode* p = root; BTNode* k; T nodeValue ; cinnodeValue; if(nodeValue=-1) root=NULL; else root=new BTNode(); root-data

9、= nodeValue; createBinTree(root-Lchild); createBinTree(root-Rchild); /*/二叉樹的先序遍歷template void preOrder( BTNode * & p) if(p) coutdataLchild); preOrder(p-Rchild); /*/二叉樹的中序遍歷template void inOrder(BTNode * & p) if(p) inOrder(p-Lchild); coutdataRchild); /*/二叉樹的后序遍歷template void levelOrder(BTNode *& p) i

10、f(p) levelOrder(p-Lchild); levelOrder(p-Rchild); coutdata ; /*/統(tǒng)計二叉樹中結(jié)點的個數(shù)templateint countNode(BTNode * & p) if(p = NULL) return 0; return 1+countNode(p-Lchild)+countNode(p-Rchild);/*/求二叉樹的深度templateint depth(BTNode *& p) if(p = NULL) return -1; int h1 = depth(p-Lchild); int h2 = depth(p-Rchild); i

11、f(h1h2)return (h1+1); return h2+1;/*/二叉樹的消毀操作templateBTNode* destroy(BTNode* p) /消毀函數(shù)，用來消毀二叉樹中的各個結(jié)點 if(p) return destroy(p-Lchild); return destroy(p-Rchild); delete p; /*/主函數(shù)的設(shè)計 int main () BTNode * rootNode = NULL; int choiced = 0; while(true) system(cls); coutnnn -主界面-nnn; cout 1、創(chuàng)建二叉樹 2、先序遍歷二叉樹n;

12、 cout 3、中序遍歷二叉樹 4、后序遍歷二叉樹n; cout 5、統(tǒng)計結(jié)點總數(shù) 6、查看樹深度 n; cout 7、消毀二叉樹 0、退出nn; coutchoiced; if(choiced = 0) return 0; else if(choiced = 1) system(cls); cout請輸入每個結(jié)點，回車確認，并以-1結(jié)束：n; createBinTree(rootNode ); else if(choiced = 2) system(cls); cout先序遍歷二叉樹結(jié)果：n; preOrder(rootNode); coutendl; system(pause); else

13、 if(choiced = 3) system(cls); cout中序遍歷二叉樹結(jié)果：n; inOrder(rootNode); coutendl; system(pause); else if(choiced = 4) system(cls); cout后序遍歷二叉樹結(jié)果：n; levelOrder(rootNode); coutendl; system(pause); else if(choiced = 5) system(cls); int count = countNode(rootNode); cout二叉樹中結(jié)點總數(shù)為countendl; system(pause); else

14、if(choiced = 6) system(cls); int dep = depth(rootNode); cout此二叉樹的深度為dependl; system(pause); else if(choiced = 7) system(cls); cout二叉樹已被消毀！n; destroy(rootNode); coutendl; system(pause); else system(cls); coutnnnnnt錯誤選擇！n; 如 5 / 3 8 / / 2 4 6 9 / / / / 1 -1-1-1-17 -1 -1 / / -1 -1 -1 -1那么輸入時的序列為:5321-1

15、-1-14-1-186-17-1-19-1-1#include /預(yù)編譯命令 using namespace std; struct TREE /結(jié)構(gòu)體定義 int data; /整型數(shù) struct TREE *L,*R; /TREE結(jié)構(gòu)指針 ; /被調(diào)用函數(shù)insert，將結(jié)點插入二叉樹 void insert(TREE *&pRoot,TREE *pNode) if(pRoot=NULL) /如果根結(jié)點為空 pRoot=pNode; /將結(jié)點pNode插入根結(jié)點 return; /返回 else /根結(jié)點不為空 /如果pNode結(jié)點數(shù)據(jù)小于等于根結(jié)點數(shù)據(jù) if(pNode-datadat

16、a) insert(pRoot-L,pNode); /插入左子樹 else /如果pNode結(jié)點數(shù)據(jù)大于根結(jié)點數(shù)據(jù) insert(pRoot-R,pNode); /插入左子樹木 /函數(shù)體結(jié)束 /被調(diào)用函數(shù)，形參為TREE結(jié)構(gòu)指針，輸出二叉樹內(nèi)容 void print(TREE *pRoot) /函數(shù)體開始 if(pRoot=NULL) /根或子樹根結(jié)點為空 return; /返回 print(pRoot-L); /輸出左子樹內(nèi)容 coutdataR); /輸出右子樹內(nèi)容 /被調(diào)用函數(shù)結(jié)束 int main() /主函數(shù)開始 /函數(shù)體開始 struct TREE *pRoot,*pNode; /

17、TREE型結(jié)構(gòu)指針 int temp; /臨時變量，用于用戶輸入數(shù)據(jù) pRoot=NULL; /初始化二叉樹根結(jié)點為空 pNode=NULL; /初始化待插入結(jié)點的指針為空 cout請輸入要插入結(jié)點的數(shù)據(jù)n; /提示信息 couttemp; /輸入待插入結(jié)點數(shù)據(jù) while(temp!=-1) /當型循環(huán)，-1為結(jié)束標志 /循環(huán)體開始 /為待插入結(jié)點分配內(nèi)存單元 pNode=new TREE; pNode-data=temp; /將賦值給結(jié)點的數(shù)據(jù)域 pNode-L=NULL; /將結(jié)點的左右 pNode-R=NULL; /指針域置為空 insert(pRoot,pNode); /將pNode

18、結(jié)點插入到根為pRoo的根中 cout請輸入待插入結(jié)點的數(shù)據(jù)n; /提示信息 couttemp; /輸入待插入結(jié)點數(shù)據(jù) /循環(huán)體結(jié)束 if(pRoot=NULL) /如果根結(jié)點為空 cout這是一棵空樹。n; /輸出空樹信息 else print(pRoot); /調(diào)用insert函數(shù)，輸出二叉樹內(nèi)容 return 0; /主函數(shù)結(jié)束語 根據(jù)樓主給出的圖，可以用下面的代碼來進行構(gòu)建來構(gòu)建，代碼經(jīng)過實際的運行驗證，無錯，運行結(jié)果是樓主所給的二叉樹。思想：結(jié)合先序和中序遍歷來構(gòu)建給定的二叉樹。所給的二叉樹圖中，先序：A,B,D,E,C,F,G中序：D,B,E,A,F,C,G下面直接貼出代碼(建立工程后，貼上下面代碼可直接運行)：#include stdafx.h#include /二叉樹結(jié)構(gòu)體struct BTNode char data; BTNode *rchild; BTNode *lchild;char PreNode8 =A,B,D,F,E,G,H,C;char MidNode8 =D,F,B,G,E,H,A,C;/* 二叉樹創(chuàng)建函數(shù)dCreateBranchTree3() 已知二叉樹的前,中序遍歷序列串,構(gòu)造對應(yīng)的二叉