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

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

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

我的百度空间:http://doc.guandang.net/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)
{
…… 此处隐藏：6965字，全部文档内容请下载后查看。喜欢就下载吧 ……