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

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

二叉树的建立与遍历,叶子结点的数目以及树的深度的求法,采用递归求解.txt我不奢望什么，只希望你以后的女人一个不如一个。真怀念小时候啊，天热的时候我也可以像男人一样光膀子！是我个人写的，很简单的记录下来了，呵呵呵。

我的百度空间:/heihei_shaweiwei/blog/item/eec5a3de6bb28c0462279805.html

#include <iostream>

using namespace std;


//定义树的结构
typedef struct _binTree
{
char data;
_binTree *lNode,*rNode;
}binTree;

//创建二叉树
void createT(binTree *&rootNode,binTree *tempNode)
{
if(rootNode==NULL)
{
rootNode=tempNode; return;
}
else
{
if(rootNode->data > tempNode->data)
{
createT(rootNode->lNode,tempNode);
}
else if(rootNode->data < tempNode->data)
{
createT(rootNode->rNode,tempNode);
}
}
}
//打印已创建的数
void printT(binTree *rootNode)
{
if(rootNode==NULL)return ;
else
{
printT(rootNode->lNode);
cout<<rootNode->data<<" ";
printT(rootNode->rNode);
}
}
//先序遍历二叉树
void preTraverse(binTree *rootNode)
{
if(rootNode==NULL)return ;
else
{
cout<<rootNode->data<<" ";
printT(rootNode->lNode);
printT(rootNode->rNode);
}
}
//中序遍历二叉树
void midTraverse(binTree *rootNode)
{
if(rootNode==NULL)return ;
else
{
printT(rootNode->lNode);
cout<<rootNode->data<<" ";
printT(rootNode->rNode);
}
}
//后序遍历二叉树
void lastTraverse(binTree *rootNode)
{
if(rootNode==NULL)return ;
else
{
printT(rootNode->lNode);
printT(rootNode->rNode);
cout<<rootNode->data<<" ";
}
}
//计算结点的总个数
int nodeTotal(binTree *rootNode)
{
if(rootNode==NULL)return 0;
else
{
return 1+nodeTotal(rootNode->lNode)+nodeTotal(rootNode->rNode);
}
}
//计算二叉树的深度
int treeDepth(binTree *rootNode)
{
if(rootNode==NULL)return -1;
else
{
int lH=treeDepth(rootNode->lNode);
int rH=treeDepth(rootNode->rNode);
if(lH>rH)return lH+1;
return rH+1;
}
}
//计算叶子结点的个数
int leafTotal(binTree *rootNode)
{
if(rootNode==NULL)return 0;
else
{
if(rootNode->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<<"按照下面给出的顺序进行输入构建二叉树："<<endl<<"F D B E A C J H K G I L"<<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;
}
else
{
cout<<"正常输出二叉树的各节点数据："
;;
printT(rootNode); cout<<endl;
cout<<"先序遍历二叉树的各节点数据：";
preTraverse(rootNode); cout<<endl;
cout<<"中

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

序遍历二叉树的各节点数据：";
midTraverse(rootNode); cout<<endl;
cout<<"后序遍历二叉树的各节点数据：";
lastTraverse(rootNode); cout<<endl;
cout<<"二叉树的深度为："<<treeDepth(rootNode)<<endl;
cout<<"二叉树的结点的个数为："<<nodeTotal(rootNode)<<endl;
cout<<"二叉树的叶子结点的个数为："<<leafTotal(rootNode)<<endl;
}
return 0;
}



在vc6.0和dev-C++上都可以顺利运行，可以看一下 啊，呵呵。


!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!


#include <iostream>

using namespace std;

//*************************************************************************************
//二叉树结点类的定义
template<class T>
struct BTNode
{
T data;
BTNode <T> * Lchild,*Rchild;
BTNode(T nodeValue = T(),BTNode<T>* leftNode = NULL,BTNode<T>* rightNode = NULL )
:data(nodeValue),Lchild(leftNode),Rchild(rightNode){} //可选择参数的默认构造函数
};
//**************************************************************************************
//二叉树的建立
template <class T>
void createBinTree(BTNode<T> * &root )
{
BTNode<T>* p = root;
BTNode<T>* k;
T nodeValue ;
cin>>nodeValue;
if(nodeValue==-1)
{
root=NULL;
}
else
{
root=new BTNode<T>();
root->data = nodeValue;
createBinTree(root->Lchild);
createBinTree(root->Rchild);
}
}
//************************************************************************************
//二叉树的先序遍历
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->data<<" ";
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)
{
if(p == NULL) return 0;
return 1+countNode(p->Lchild)+countNode(p->Rchild);
}
//***********************************************************************************
//求二叉树的深度
template<class T>
int depth(BTNode&l
t;T> *& p)
{
if(p == NULL)
return -1;
int h1 = depth(p->Lchild);
int h2 = depth(p->Rchild);
if(h1>h2)return (h1+1);
retur

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

n h2+1;
}
//***********************************************************************************
//二叉树的消毁操作
template<class T>
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<<"\n\n\n ---主界面---\n\n\n";
cout<<" 1、创建二叉树 2、先序遍历二叉树\n";
cout<<" 3、中序遍历二叉树 4、后序遍历二叉树\n";
cout<<" 5、统计结点总数 6、查看树深度 \n";
cout<<" 7、消毁二叉树 0、退出\n\n";
cout<<" 请选择操作：";
cin>>choiced;
if(choiced == 0)
return 0;
else if(choiced == 1)
{
system("cls");
cout<<"请输入每个结点，回车确认，并以-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;
system("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<<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<<endl;
system("pause");
}

else
{
system("cls");
cout<<"\n\n\n\n\n\t错误选择！\n";
}

}
}


如 5
/ \
3

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

8
/ \ / \
2 4 6 9
/ \ / \ / \ / \
1 -1-1-1-17 -1 -1
/ \ / \
-1 -1 -1 -1

那么输入时的序列为: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结构指针
};
//被调用函数insert，将结点插入二叉树
void insert(TREE *&pRoot,TREE *pNode)
{
if(pRoot==NULL) //如果根结点为空
{
pRoot=pNode; //将结点pNode插入根结点
return; //返回
}
else //根结点不为空
{
//如果pNode结点数据小于等于根结点数据
if(pNode->data<=pRoot->data)
insert(pRoot->L,pNode); //插入左子树
else //如果pNode结点数据大于根结点数据
insert(pRoot->R,pNode); //插入左子树木
} //函数体结束

}
//被调用函数，形参为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; //TREE型结构指针
int temp; //临时变量，用于用户输入数据
pRoot=NULL; //初始化二叉树根结点为空
pNode=NULL; //初始化待插入结点的指针为空
cout<<"请输入要插入结点的数据\n"; //提示信息
cout<<"如果输入-1表示插入过程结束\n"; //提示信息
cin>>temp; //输入待插入结点数据
while(temp!=-1) //当型循环，-1为结束标志
{ //循环体开始
//为待插入结点分配内存单元
pNode=new TREE;
pNode->data=temp;
//将赋值给结点的数据域
pNode->L=NULL; //将结点的左右
pNode->R=NULL; //

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

指针域置为空
insert(pRoot,pNode); //将pNode结点插入到根为pRoo的根中
cout<<"请输入待插入结点的数据\n"; //提示信息
cout<<"如果输入-1表示插入过程结束\n"; //提示信息
cin>>temp; //输入待插入结点数据
} //循环体结束
if(pRoot==NULL) //如果根结点为空
cout<<"这是一棵空树。\n"; //输出空树信息
else
print(pRoot); //调用insert函数，输出二叉树内容
return 0;
} //主函数结束语


根据楼主给出的图，可以用下面的代码来进行构建来构建，代码经过实际的运行验证，无错，运行结果是楼主所给的二叉树。
思想：结合先序和中序遍历来构建给定的二叉树。
所给的二叉树图中，先序：A,B,D,E,C,F,G
中序：D,B,E,A,F,C,G
下面直接贴出代码(建立工程后，贴上下面代码可直接运行)：

#include "stdafx.h"
#include <malloc.h>

//二叉树结构体
struct BTNode
{
char data;
BTNode *rchild;
BTNode *lchild;
};
char PreNode[8] ={'A','B','D','F','E','G','H','C'};
char MidNode[8] ={'D','F','B','G','E','H','A','C'};
/*
二叉树创建函数dCreateBranchTree3()<非递归算法>
已知二叉树的前,中序遍历序列串,构造对应的二叉树
<编程思想>:
首先,在前序遍历序列中的首元素是二叉树的根节点,接着
,在中序遍历序列中找到此节点,那么在此节点以前的节点必为
其左孩子节点,以后的必为其右孩子节点;
然后,在中序遍历序列中,根节点的左子树和右子树再分别
对应子树前序遍历序列的首字符确定子树的根节点,再由中序
遍历序列中根节点的位置分别确定构成它们的左子树和右子树
的节点;
依次类推,确定二叉树的全部节点,构造出二叉树.
参数描述：
char *pre: 前序遍历序列
char *mid: 中序遍历序列
int n: 遍历序列中节点个数
返回值:
dCreateBranchTree3 = 新建二叉树的根节点指针
*/
BTNode *dCreateBranchTree3(char *pre,char *mid,int n)
{
BTNode *p;
char *t;
int left;
if(n<=0)
return(NULL);
p = (BTNode *)malloc(sizeof(BTNode));
p->data = *pre;
for(t=mid;t<mid+n;t++)
if(*t==*pre) break; /*在中序遍历序列中查找根节点*/
left = t - mid; /*左子树的节点个数*/
p->lchild = dCreateBranchTree3(pre+1,mid,left);
p->rchild = dCreateBranchTree3(pre+1+left,t+1,n-1-left);

return(p);
}
int _tmain(int argc, _TCHAR* argv[])
{
BTNode *pTree = dCreateBranchTree3(PreNode, MidNode, 8);
_getch();
return 0;
}

本文来源：https://www.bwwdw.com/article/i2f1.html