二叉树的建立与遍历,叶子结点的数目以及树的深度的求法,采用递归求解

1、是我个人写的，很简单的记录下来了，呵呵呵。我的百度间：#include <iostream>using namespace std;/ 定义树的结构typedef struct _binTreechar data;_binTree *lNode,*rNode;binTree;/ 创建二叉树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);/ 打印已创建的数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<<" "/ 计算结点的总个数int nodeTotal(binTree *rootNode)if(rootNode=NULL)return 0;elseretur

5、n 1+nodeTotal(rootNode->lNode)+nodeTotal(rootNode->rNode); / 计算二叉树的深度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;/ 计算叶子结点的个数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<<" 按照下面给出的顺序进行输入构建二叉树："<

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、" 正常输出二叉树的各节点数据： "printT(rootNode); cout<<endl;cout<<" 先序遍历二叉树的各节点数据： " preTraverse(rootNode); cout<<endl;cout<<" 中序遍历二叉树的各节点数据： " midTraverse(rootNode); cout<<endl;cout<<" 后序遍历二叉树的各节点数据： " lastTraverse(rootNode); cout<&l

9、t;endl;cout<<" 二叉树的深度为： "<<treeDepth(rootNode)<<endl; cout<<" 二叉树的结点的个数为： "<<nodeTotal(rootNode)<<endl;cout<<" 二叉树的叶子结点的个数为： "<<leafTotal(rootNode)<<endl; return 0;在 vc6.0 和 dev-C+ 上都可以顺利运行，可以看一下啊，呵呵。! !#include <

10、iostream>using namespace std;/*/ 二叉树结点类的定义 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) / 可选择参数 的默认构造函数;/*/ 二叉树的建立 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<<" "/*/ 统计二叉树中结点的个数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) / 消毁函数，用来消毁二叉 树中的各个结点if(p)return destroy(p->Lchild);return destroy(p->Rchild);delete p;/* / 主函数的设计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<<"、创建二叉树、中序遍历二叉树、统计结点总数、消毁二叉树请选择操作： "主界面 -nnn"2、先序遍历二叉4、后序遍历二叉6、查看树深度0、退出 nn"cin>>choiced;if(choiced = 0)return 0;else if(choiced = 1) system("cls"); cout<<"请输入每个结点，回车确认，并

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

18、ystem("pause");else if(choiced = 4)system("cls");cout<<" 后序遍历二叉树结果： n"levelOrder(rootNode);cout<<endl;system("pause");else if(choiced = 5)system("cls");int count = countNode(rootNode);cout<<" 二叉树中结点总数为 "<<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错误选择！ n"那么输入时的序列为: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预编译命令结构体定义整型数结构

21、指针/函数体结束;/ 被调用函数 insert ，将结点插入二叉树 void insert(TREE *&pRoot,TREE *pNode)if(pRoot=NULL) /pRoot=pNode; / return; /else /如果根结点为空将结点 pNode 插入根结点 返回根结点不为空/ 如果 pNode 结点数据小于等于根结点数据 if(pNode->data<=pRoot->data)insert(pRoot->L,pNode);/插入左子树else / 如果 pNode 结点数据大于根结点数据 insert(pRoot->R,pNode);

22、/插入左子树木/函数体结束/被调用函数，形参为 TREE结构指针，输出二叉树内容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<<" 请输入要插入结点的数据 n"/cout<<"

23、 如果输入 -1 表示插入过程结束 n"cin>>temp; /while(temp!=-1) / / 为待插入结点分配内存单元pNode=new TREE;pNode->data=temp; / pNode->L=NULL;/pNode->R=NULL;/insert(pRoot,pNode);/的根中cout<<"请输入待插入结点的数据 n"cout<<"如果输入 -1 表示插入过程结束cin>>temp; / / 循环体结束if(pRoot=NULL)/cout<<&qu

24、ot; 这是一棵空树。 n"/函数体开始根或子树根结点为空返回输出左子树内容输出数据输出右子树内容被调用函数结束 主函数开始 函数体开始 型结构指针临时变量，用于用户输入数据 初始化二叉树根结点为空 初始化待插入结点的指针为空 提示信息/ 提示信息 输入待插入结点数据当型循环， -1 为结束标志 循环体开始elseprint(pRoot);/容return 0; /将赋值给结点的数据域 将结点的左右 指针域置为空将pNode结点插入到根为 pRoo/ 提示信息 n" / 提示信息输入待插入结点数据如果根结点为空 输出空树信息调用 insert 函数，输出二叉树内主函数结束语

25、根据楼主给出的图，可以用下面的代码来进行构建来构建，代码经过实际的运行验证， 无错，运行结果是楼主所给的二叉树。思想：结合先序和中序遍历来构建给定的二叉树。 所给的二叉树图中，先序： A,B,D,E,C,F,G 中序： D,B,E,A,F,C,G下面直接贴出代码 ( 建立工程后，贴上下面代码可直接运行 ) ：#include "stdafx.h"#include <malloc.h>/ 二叉树结构体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'/*二叉树创建函数 dCre