|
本文主要是关于树的相关操作，主要包括：二叉树的建立、3种遍历方式、叶子数、节点数、层数等。
#include<iostream>
using namespace std;
typedef struct node
{
struct node *leftChild;
struct node *rightChild;
char data;
}BiTreeNode, *BiTree;
//创建二叉树
void createBiTree(BiTree &T)
{
char c;
cin >> c;
if('#' == c)
{
T = NULL;
}
else
{
T = new BiTreeNode;
T->data = c;
createBiTree(T->leftChild);
createBiTree(T->rightChild);
}
}
//前序遍历
void preoederTrav(BiTree T)
{
if (T)
{
cout<<T->data<<' ';
preoederTrav(T->leftChild);
preoederTrav(T->rightChild);
}
}
//中序遍历
void midaordertravel(BiTree T)
{
if (T)
{
midaordertravel(T->leftChild);
cout<<T->data<<' ';
midaordertravel(T->rightChild);
}
}
//后序遍历
void lastorder(BiTree T)
{
if (T)
{
lastorder(T->leftChild);
lastorder(T->rightChild);
cout<<T->data<<' ';
}
}
//树的节点数
int Nodenum(BiTree T)
{
if (T==NULL)
{
return 0;
}
else
{
return 1+Nodenum(T->leftChild)+Nodenum(T->rightChild);
}
}
//树的深度
int Depth(BiTree T)
{
if (T)
{
return Depth(T->leftChild)>Depth(T->rightChild)? Depth(T->leftChild)+1:Depth(T->rightChild)+1;
}
if(T==NULL)
{
return 0;
}
}
//叶子数
int leafnum(BiTree T)
{
if (!T)
{
return 0;
}
else if ((T->leftChild==NULL)&&(T->rightChild==NULL))
{
return 1;
}
else
{
return (leafnum(T->leftChild))+(leafnum(T->rightChild));
}
}
int main()
{
BiTree T;
createBiTree(T);
cout<<"创建二叉树成功！"<<endl;
cout<<"前序遍历："<<endl;
preoederTrav(T);
cout<<endl;
cout<<"中序遍历："<<endl;
midaordertravel(T);
cout<<endl;
cout<<"后序遍历："<<endl;
lastorder(T);
cout<<endl;
cout<<"树节点数："<<Nodenum(T)<<endl;
cout<<"树深度："<<Depth(T)<<endl;
cout<<"叶子数："<<leafnum(T)<<endl;
return 0;
}
| 
转播
