1、是我個(gè)人寫(xiě)的，很簡(jiǎn)單的記錄下來(lái)了，呵呵呵。我的百度空間:/heihei_shaweiwei/blog/item/eec5a3de6bb28c.html#include using namespace std;/定義樹(shù)的結(jié)構(gòu)typedef struct _binTree char data; _binTree *lNode,*rNode;binTree;/創(chuàng)建二叉樹(shù)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); /先序遍歷二叉樹(shù)void preTraverse(binTree *rootNode) if(rootNode=NULL

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

4、talNode)+nodeTotal(rootNode-rNode); /計(jì)算二叉樹(shù)的深度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; /計(jì)算葉子結(jié)點(diǎn)的個(gè)數(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按照下面給出的順序進(jìn)行輸入構(gòu)建二叉樹(shù)：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正常輸出二叉樹(shù)的各節(jié)點(diǎn)數(shù)據(jù)：; printT(rootNode); coutendl; cout先序遍歷二叉樹(shù)的各節(jié)點(diǎn)數(shù)據(jù)：; preTraverse(rootNode); coutendl; cout中序遍歷二叉樹(shù)的各節(jié)點(diǎn)數(shù)據(jù)：; midTraverse(rootNode); coutendl; cout后序遍歷二叉樹(shù)的各節(jié)點(diǎn)數(shù)據(jù)：; lastTrav

7、erse(rootNode); coutendl; cout二叉樹(shù)的深度為：treeDepth(rootNode)endl; cout二叉樹(shù)的結(jié)點(diǎn)的個(gè)數(shù)為：nodeTotal(rootNode)endl; cout二叉樹(shù)的葉子結(jié)點(diǎn)的個(gè)數(shù)為：leafTotal(rootNode)endl; return 0;在vc6.0和dev-C+上都可以順利運(yùn)行，可以看一下 啊，呵呵。 !#include using namespace std;/*/二叉樹(shù)結(jié)點(diǎn)類(lèi)的定義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ù)的默認(rèn)構(gòu)造函數(shù);/*/二叉樹(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); /*/二叉樹(shù)的先序遍歷template void preOrder( BTNode * & p) if(p) coutdataLchild); preOrder(p-Rchild); /*/二叉樹(shù)的中序遍歷template void inOrder(BTNode * & p) if(p) inOrder(p-Lchild); coutdataRchild); /*/二叉樹(shù)的后序遍歷template void levelOrder(BTNode *& p) i

10、f(p) levelOrder(p-Lchild); levelOrder(p-Rchild); coutdata ; /*/統(tǒng)計(jì)二叉樹(shù)中結(jié)點(diǎn)的個(gè)數(shù)templateint countNode(BTNode * & p) if(p = NULL) return 0; return 1+countNode(p-Lchild)+countNode(p-Rchild);/*/求二叉樹(shù)的深度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;/*/二叉樹(shù)的消毀操作templateBTNode* destroy(BTNode* p) /消毀函數(shù)，用來(lái)消毀二叉樹(shù)中的各個(gè)結(jié)點(diǎn) if(p) return destroy(p-Lchild); return destroy(p-Rchild); delete p; /*/主函數(shù)的設(shè)計(jì) int main () BTNode * rootNode = NULL; int choiced = 0; while(true) system(cls); coutnnn -主界面-nnn; cout 1、創(chuàng)建二叉樹(shù) 2、先序遍歷二叉樹(shù)n;

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

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

14、if(choiced = 6) system(cls); int dep = depth(rootNode); cout此二叉樹(shù)的深度為dependl; system(pause); else if(choiced = 7) system(cls); cout二叉樹(shù)已被消毀！n; destroy(rootNode); coutendl; system(pause); else system(cls); coutnnnnnt錯(cuò)誤選擇！n; 如 5 / 3 8 / / 2 4 6 9 / / / / 1 -1-1-1-17 -1 -1 / / -1 -1 -1 -1那么輸入時(shí)的序列為: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é)點(diǎn)插入二叉樹(shù) void insert(TREE *&pRoot,TREE *pNode) if(pRoot=NULL) /如果根結(jié)點(diǎn)為空 pRoot=pNode; /將結(jié)點(diǎn)pNode插入根結(jié)點(diǎn) return; /返回 else /根結(jié)點(diǎn)不為空 /如果pNode結(jié)點(diǎn)數(shù)據(jù)小于等于根結(jié)點(diǎn)數(shù)據(jù) if(pNode-datadat

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

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

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