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

1、是我個(gè)人寫的，很簡(jiǎn)單的記錄下來了，呵呵呵。我的百度間：#include <iostream>using namespace std;/ 定義樹的結(jié)構(gòu)typedef struct _binTreechar data;_binTree *lNode,*rNode;binTree;/ 創(chuàng)建二叉樹void createT(binTree *&rootNode,binTree *tempNode)if(rootNode=NULL)rootNode=tempNode; return;elseif(rootNode->data > tempNode->data)crea

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

3、void preTraverse(binTree *rootNode)if(rootNode=NULL)return ;elsecout<<rootNode->data<<" "printT(rootNode->lNode);printT(rootNode->rNode);/ 中序遍歷二叉樹void midTraverse(binTree *rootNode)if(rootNode=NULL)return ;elseprintT(rootNode->lNode);cout<<rootNode->data<

4、;<" "printT(rootNode->rNode);/ 后序遍歷二叉樹void lastTraverse(binTree *rootNode)if(rootNode=NULL)return ;elseprintT(rootNode->lNode);printT(rootNode->rNode);cout<<rootNode->data<<" "/ 計(jì)算結(jié)點(diǎn)的總個(gè)數(shù)int nodeTotal(binTree *rootNode)if(rootNode=NULL)return 0;elseretur

5、n 1+nodeTotal(rootNode->lNode)+nodeTotal(rootNode->rNode); / 計(jì)算二叉樹的深度int treeDepth(binTree *rootNode)if(rootNode=NULL)return -1;elseint lH=treeDepth(rootNode->lNode);int rH=treeDepth(rootNode->rNode);if(lH>rH)return lH+1;return rH+1;/ 計(jì)算葉子結(jié)點(diǎn)的個(gè)數(shù)int leafTotal(binTree *rootNode)if(rootNo

6、de=NULL)return 0;elseif(rootNode->lNode=NULL && rootNode->rNode=NULL)return 1;elseint 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)建二叉樹："<

7、<endl<<"F D B E A C J H K G IL"<<endl;cin>>ch;while(ch!='0')tNode=new binTree;tNode->data=ch; tNode->lNode=NULL; tNode->rNode=NULL;createT(rootNode,tNode);cin>>ch;if(rootNode=NULL)cout<<"Tree is NULL."<<endl;elsecout<<

8、" 正常輸出二叉樹的各節(jié)點(diǎn)數(shù)據(jù)： "printT(rootNode); cout<<endl;cout<<" 先序遍歷二叉樹的各節(jié)點(diǎn)數(shù)據(jù)： " preTraverse(rootNode); cout<<endl;cout<<" 中序遍歷二叉樹的各節(jié)點(diǎn)數(shù)據(jù)： " midTraverse(rootNode); cout<<endl;cout<<" 后序遍歷二叉樹的各節(jié)點(diǎn)數(shù)據(jù)： " lastTraverse(rootNode); cout<&l

9、t;endl;cout<<" 二叉樹的深度為： "<<treeDepth(rootNode)<<endl; cout<<" 二叉樹的結(jié)點(diǎn)的個(gè)數(shù)為： "<<nodeTotal(rootNode)<<endl;cout<<" 二叉樹的葉子結(jié)點(diǎn)的個(gè)數(shù)為： "<<leafTotal(rootNode)<<endl; return 0;在 vc6.0 和 dev-C+ 上都可以順利運(yùn)行，可以看一下啊，呵呵。! !#include <

10、iostream>using namespace std;/*/ 二叉樹結(jié)點(diǎn)類的定義 template<class T> struct BTNodeT data;BTNode <T> * Lchild,*Rchild;BTNode(T nodeValue = T(),BTNode<T>* leftNode = NULL,BTNode<T>* rightNode = NULL) :data(nodeValue),Lchild(leftNode),Rchild(rightNode) / 可選擇參數(shù) 的默認(rèn)構(gòu)造函數(shù);/*/ 二叉樹的建立 temp

11、late <class T> void createBinTree(BTNode<T> * &root ) BTNode<T>* p = root;BTNode<T>* k;T nodeValue ; cin>>nodeValue; if(nodeValue=-1)root=NULL;elseroot=new BTNode<T>(); root->data = nodeValue; createBinTree(root->Lchild); createBinTree(root->Rchild);/

12、*/ 二叉樹的先序遍歷 template <class T> void preOrder( BTNode<T> * & p) if(p)cout<<p->data<<" " preOrder(p->Lchild); preOrder(p->Rchild); /*/ 二叉樹的中序遍歷 template <class T> void inOrder(BTNode<T> * & p) if(p)inOrder(p->Lchild);cout<<p->d

13、ata<<" "inOrder(p->Rchild);/*/ 二叉樹的后序遍歷template <class T>void levelOrder(BTNode<T> *& p)if(p)levelOrder(p->Lchild);levelOrder(p->Rchild);cout<<p->data<<" "/*/ 統(tǒng)計(jì)二叉樹中結(jié)點(diǎn)的個(gè)數(shù)template<class T>int countNode(BTNode<T> * & p)i

14、f(p = NULL) return 0;return 1+countNode(p->Lchild)+countNode(p->Rchild);/*/ 求二叉樹的深度template<class T>int depth(BTNode<T> *& p)if(p = NULL)return -1;int h1 = depth(p->Lchild);int h2 = depth(p->Rchild);if(h1>h2)return (h1+1);return h2+1;/* / 二叉樹的消毀操作template<class T>

15、;BTNode<T>*destroy(BTNode<T>* p) / 消毀函數(shù)，用來消毀二叉 樹中的各個(gè)結(jié)點(diǎn)if(p)return destroy(p->Lchild);return destroy(p->Rchild);delete p;/* / 主函數(shù)的設(shè)計(jì)int main ()BTNode<int> * rootNode = NULL;int choiced = 0;while(true)system("cls"); cout<<"nnn cout<<"1樹 n"co

16、ut<<"3樹 n"cout<<"5n"cout<<"7cout<<"、創(chuàng)建二叉樹、中序遍歷二叉樹、統(tǒng)計(jì)結(jié)點(diǎn)總數(shù)、消毀二叉樹請(qǐng)選擇操作： "主界面 -nnn"2、先序遍歷二叉4、后序遍歷二叉6、查看樹深度0、退出 nn"cin>>choiced;if(choiced = 0)return 0;else if(choiced = 1) system("cls"); cout<<"請(qǐng)輸入每個(gè)結(jié)點(diǎn)，回車確認(rèn)，并

17、以 -1 結(jié)束： n"createBinTree(rootNode );else if(choiced = 2)system("cls");cout<<"先序遍歷二叉樹結(jié)果： n"preOrder(rootNode);cout<<endl;system("pause");else if(choiced = 3)system("cls");cout<<" 中序遍歷二叉樹結(jié)果： n"inOrder(rootNode);cout<<endl;s

18、ystem("pause");else if(choiced = 4)system("cls");cout<<" 后序遍歷二叉樹結(jié)果： n"levelOrder(rootNode);cout<<endl;system("pause");else if(choiced = 5)system("cls");int count = countNode(rootNode);cout<<" 二叉樹中結(jié)點(diǎn)總數(shù)為 "<<count<&l

19、t;endl; system("pause");else if(choiced = 6)system("cls");int dep = depth(rootNode);cout<<" 此二叉樹的深度為 "<<dep<<endl;system("pause");else if(choiced = 7)system("cls");cout<<" 二叉樹已被消毀！ n"destroy(rootNode);cout<<end

20、l;system("pause");elsesystem("cls");如5/ 3 8/ / 2 4 6 9/ / / / 1 -1-1-1-17 -1 -1/ / -1 -1-1 -1cout<<"nnnnnt錯(cuò)誤選擇！ n"那么輸入時(shí)的序列為:5321-1-1-14-1-186-17-1-19-1-1#include <iostream> / using namespace std;struct TREE /int data; / struct TREE *L,*R;/TREE預(yù)編譯命令結(jié)構(gòu)體定義整型數(shù)結(jié)構(gòu)

21、指針/函數(shù)體結(jié)束;/ 被調(diào)用函數(shù) insert ，將結(jié)點(diǎn)插入二叉樹 void insert(TREE *&pRoot,TREE *pNode)if(pRoot=NULL) /pRoot=pNode; / return; /else /如果根結(jié)點(diǎn)為空將結(jié)點(diǎn) pNode 插入根結(jié)點(diǎn) 返回根結(jié)點(diǎn)不為空/ 如果 pNode 結(jié)點(diǎn)數(shù)據(jù)小于等于根結(jié)點(diǎn)數(shù)據(jù) if(pNode->data<=pRoot->data)insert(pRoot->L,pNode);/插入左子樹else / 如果 pNode 結(jié)點(diǎn)數(shù)據(jù)大于根結(jié)點(diǎn)數(shù)據(jù) insert(pRoot->R,pNode);

22、/插入左子樹木/函數(shù)體結(jié)束/被調(diào)用函數(shù)，形參為 TREE結(jié)構(gòu)指針，輸出二叉樹內(nèi)容void print(TREE *pRoot)/if(pRoot=NULL)/return;/print(pRoot->L);/cout<<pRoot->data<<endl;/print(pRoot->R);/int main()/struct TREE *pRoot,*pNode;/TREEint temp;/pRoot=NULL;/pNode=NULL;/cout<<" 請(qǐng)輸入要插入結(jié)點(diǎn)的數(shù)據(jù) n"/cout<<"

23、 如果輸入 -1 表示插入過程結(jié)束 n"cin>>temp; /while(temp!=-1) / / 為待插入結(jié)點(diǎn)分配內(nèi)存單元pNode=new TREE;pNode->data=temp; / pNode->L=NULL;/pNode->R=NULL;/insert(pRoot,pNode);/的根中cout<<"請(qǐng)輸入待插入結(jié)點(diǎn)的數(shù)據(jù) n"cout<<"如果輸入 -1 表示插入過程結(jié)束cin>>temp; / / 循環(huán)體結(jié)束if(pRoot=NULL)/cout<<&qu

24、ot; 這是一棵空樹。 n"/函數(shù)體開始根或子樹根結(jié)點(diǎn)為空返回輸出左子樹內(nèi)容輸出數(shù)據(jù)輸出右子樹內(nèi)容被調(diào)用函數(shù)結(jié)束 主函數(shù)開始 函數(shù)體開始 型結(jié)構(gòu)指針臨時(shí)變量，用于用戶輸入數(shù)據(jù) 初始化二叉樹根結(jié)點(diǎn)為空 初始化待插入結(jié)點(diǎn)的指針為空 提示信息/ 提示信息 輸入待插入結(jié)點(diǎn)數(shù)據(jù)當(dāng)型循環(huán)， -1 為結(jié)束標(biāo)志 循環(huán)體開始elseprint(pRoot);/容return 0; /將賦值給結(jié)點(diǎn)的數(shù)據(jù)域 將結(jié)點(diǎn)的左右 指針域置為空將pNode結(jié)點(diǎn)插入到根為 pRoo/ 提示信息 n" / 提示信息輸入待插入結(jié)點(diǎn)數(shù)據(jù)如果根結(jié)點(diǎn)為空 輸出空樹信息調(diào)用 insert 函數(shù)，輸出二叉樹內(nèi)主函數(shù)結(jié)束語

25、根據(jù)樓主給出的圖，可以用下面的代碼來進(jìn)行構(gòu)建來構(gòu)建，代碼經(jīng)過實(shí)際的運(yùn)行驗(yàn)證， 無錯(cuò)，運(yùn)行結(jié)果是樓主所給的二叉樹。思想：結(jié)合先序和中序遍歷來構(gòu)建給定的二叉樹。 所給的二叉樹圖中，先序： A,B,D,E,C,F,G 中序： D,B,E,A,F,C,G下面直接貼出代碼 ( 建立工程后，貼上下面代碼可直接運(yùn)行 ) ：#include "stdafx.h"#include <malloc.h>/ 二叉樹結(jié)構(gòu)體struct BTNodechar 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ù) dCre