#include "stdio.h"
#include "malloc.h"
#include "string.h"
#include "stdlib.h"
#define Max 20 //结点的最大个数
typedef struct BinTNode{
char data
struct BinTNode *lchild,*rchild
}BinTNode,*BinTree //自定义二叉树的结点类型
//定义二叉树的指针
int NodeNum,leaf //NodeNum为结点数，leaf为叶子数
//==========以广义表显示二叉树==============
void DisTree(BinTree T)
{
if(T)
{
printf("%c",T->data)
if((T->lchild)||(T->rchild))
{
if(T->lchild)
{
printf("%c",'(')
DisTree(T->lchild)
}
if(T->rchild)
{
printf("%c",',')
DisTree(T->rchild)
printf("%c",')')
}
}
}
}
//==========基于先序遍历算法创建二叉树==============
//=====要求输入先序序列，其中加入虚结点"#"以示空指针的位置==========
BinTree CreatBinTree(BinTree T)
{
char ch
ch=getchar()
if(ch=='#')
T=NULL
else
{
if(!(T=(BinTNode *)malloc(sizeof(BinTNode))))
printf("Error!")
T->data=ch
T->lchild=CreatBinTree(T->lchild)
T->rchild=CreatBinTree(T->rchild)
}
return T
}
//========NLR 先序遍历=============
void Preorder(BinTree T)
{
if(T)
{
printf("%c",T->data)
Preorder(T->lchild)
Preorder(T->rchild)
}
}
//========LNR 中序遍历===============
void Inorder(BinTree T)
{
if(T){
Inorder(T->lchild)
printf("%c",T->data)
Inorder(T->rchild)
}
}
//==========LRN 后序遍历============
void Postorder(BinTree T)
{
if(T){
Postorder(T->lchild)
Postorder(T->rchild)
printf("%c",T->data)
}
}
//=====采用后序遍历求二叉树的深度、结点数及叶子数的递归算法========
int TreeDepth(BinTree T)
{
int hl,hr,max
if(T){
hl=TreeDepth(T->lchild) //求左深度
hr=TreeDepth(T->rchild) //求右深度
max=hl>hr? hl:hr //取左右深度的最大值
NodeNum=NodeNum+1//求结点数
if(hl==0&&hr==0)
leaf=leaf+1 //若左右深度为0，即为叶子。
return(max+1)
}
else return(0)
}
//====利用"先进先出"（FIFO）队列，按层次遍历二叉树==========
void Levelorder(BinTree T)
{
int front=0,rear=1
BinTNode *cq[Max],*p //定义结点的指针数组cq
cq[1]=T //根入队
while(front!=rear)
{
front=(front+1)%NodeNum
p=cq[front] //出队
printf("%c",p->data)//出队，输出结点的值
if(p->lchild!=NULL){
rear=(rear+1)%NodeNum
cq[rear]=p->lchild//左子树入队
}
if(p->rchild!=NULL){
rear=(rear+1)%NodeNum
cq[rear]=p->rchild//右子树入队
}
}
}
//==========主函数=================
void main()
{
BinTree T,root
int i,depth
printf("\n")
printf("输入完全二叉树的先序序列:")//输入完全二叉树的先序序列，
// 用#代表虚结点，如ABD###CE##F##
root=CreatBinTree(T) //创建二叉树，返回根结点
DisTree(root)
printf("\n")
do //从菜单中选择遍历方式，输入序号。
{
printf("\t********** 菜单 ************\n")
printf("\n")
printf("\t1: 先序遍历\n")
printf("\t2: 中序遍历\n")
printf("\t3: 后序遍历\n")
printf("\t4: 该树的深度,结点数,叶子数\n")
printf("\t5: 层次遍历\n")//按层次遍历之前，先选择4，求出该树的结点数。
printf("\t0: 退出\n")
printf("\t*******************************\n")
scanf("%d",&i)
//输入菜单序号（0-5）
switch(i)
{
case 1: {printf("Print Bin_tree Preorder: ")
Preorder(root) //先序遍历
}break
case 2: {printf("Print Bin_Tree Inorder: ")
Inorder(root) //中序遍历
}break
case 3: {printf("Print Bin_Tree Postorder: ")
Postorder(root) //后序遍历
}break
case 4: {depth=TreeDepth(root)//求树的深度及叶子数
printf("树深=%d 树总结点数=%d",depth,NodeNum)
printf(" 树叶子数=%d",leaf)
}break
case 5: {printf("LevePrint Bin_Tree: ")
Levelorder(root)//按层次遍历
}break
default: exit(1)
}
}while(i>=0&&i<6)
}
兄弟你看看 不懂再往下留言 记得给我的劳动成果一点点奖励哦！！
#include<iostream>using
namespace
std
#define
OK
1
#define
ERROR
0
#define
OVERFLOW
-1
typedef
int
Status
typedef
char
TElemType
typedef
struct
TreeNode{
//定义的树结点
TElemType
Data
struct
TreeNode
*lchild,*rchild
}TreeNode,*Treep
Treep
CreateTree(Treep
&T)
//使用先序遍历优势创建
{
char
ch
//
cout<<"\n请你输入你要创建的树元素："
cin>>ch
if(ch
==
'#')
//若是"#",代表该节点为空
T
=
NULL
else
{
T
=
new
TreeNode
//申请空间
if(!T)
return
ERROR
//空间申请失败返回错误信息
T->Data
=
ch
//键盘输入结点信息
CreateTree(T->lchild)
//递归调用创建左子树
CreateTree(T->rchild)
//递归调用创建右子树
}
return
T
}
void
TreeTreaverseF(Treep
T)
//二叉树先序遍历
{
if(T)
{
cout<<T->Data
//输出根节点值
TreeTreaverseF(T->lchild)
//递归调用输出左子树
TreeTreaverseF(T->rchild)
//递归调用输出右子树
}
}
void
TreeTreaverseS(Treep
T)
//中序遍历二叉树
{
if(T)
{
TreeTreaverseS(T->lchild)
//递归调用输出左子树
cout<<T->Data
//输出左节点
TreeTreaverseS(T->rchild)
//递归调用输出右子树
}
}
void
TreeTreaverseT(Treep
T)
{
if(T)
{
TreeTreaverseT(T->lchild)
//递归调用输出左子树
TreeTreaverseT(T->rchild)
//递归调用输出右子树
cout<<T->Data
//输出右节点
}
}
int
main()
{
Treep
T=NULL
cout<<"\n开始创建树状结构...\n"
cout<<"\n各元素以空格隔开\n"
CreateTree(T)
cout<<"\n先序遍历输出树...\n"
TreeTreaverseF(T)
cout<<endl<<endl
cout<<"\n中序遍历输出树...\n"
TreeTreaverseS(T)
cout<<endl<<endl
cout<<"\n后序遍历输出树...\n"
TreeTreaverseT(T)
cout<<endl<<endl
return
0
}
以下是我的数据结构实验的作业：肯定好用，里面还包括了统计树的深度和叶子数！记住每次做完一个遍历还要重新输入你的树哦！#include "stdio.h"
#include "string.h"
#define NULL 0
typedef struct BiTNode{
char data
struct BiTNode *lchild,*rchild
}BiTNode,*BiTree
BiTree Create(BiTree T){
char ch
ch=getchar()
if(ch=='#')
T=NULL
else{
if(!(T=(BiTNode *)malloc(sizeof(BiTNode))))
printf("Error!")
T->data=ch
T->lchild=Create(T->lchild)
T->rchild=Create(T->rchild)
}
return T
}
void Preorder(BiTree T){
if(T){
printf("%c",T->data)
Preorder(T->lchild)
Preorder(T->rchild)
}
}
int Sumleaf(BiTree T){
int sum=0,m,n
if(T){
if((!T->lchild)&&(!T->rchild))
sum++
m=Sumleaf(T->lchild)
sum+=m
n=Sumleaf(T->rchild)
sum+=n
}
return sum
}
void zhongxu(BiTree T){
if(T){
zhongxu(T->lchild)
printf("%c",T->data)
zhongxu(T->rchild)
}
}
void houxu(BiTree T){
if(T){
houxu(T->lchild)
houxu(T->rchild)
printf("%c",T->data)
}
}
int Depth(BiTree T){
int dep=0,depl,depr
if(!T) dep=0
else{
depl=Depth(T->lchild)
depr=Depth(T->rchild)
dep=1+(depl>depr?depl:depr)
}
return dep
}
main(){
BiTree T
int sum,dep
T=Create(T)
Preorder(T)
printf("\n")
zhongxu(T)
printf("\n")
houxu(T)
printf("\n")
sum=Sumleaf(T)
printf("%d",sum)
dep=Depth(T)
printf("\n%d",dep)
}
在Turbo C的环境下，先按Ctrl+F9运行程序，此时就是建立二叉树的过程，例如输入序列ABC##DE#G##F###（其中的“#”表示空，并且输入过程中不要加回车，因为回车也有对应的ASCII码，是要算字符的，但是输入完之后可以按回车退出），然后再按ALT+F5显示用户界面，这时候就能够看到结果了。
另外你必须会手动建立一棵二叉树，保证你输入的序列能构成一棵二叉树，否则你怎么输入，按最后按多少回车程序也不会结束！
