#define TRUE 1
#define FALSE 0
//---------二叉树链式表示-----------
typedef int Status;
typedef struct BiTNode
{
char data;
struct BiTNode * lchild, * rchild;
}BiTNode,* BiTree;
typedef struct Stack
{
BiTree * top, * base;
}Stack;
#include "iostream"
#include "cstdio"
#include "cstdlib"
//----------栈的函数的定义-----------
void InitStack(Stack &S)
{
S.base = S.top = (BiTree
*)malloc(sizeof(BiTree) * 100);
}
Status StackEmpty(Stack S)
{
if(S.top == S.base) return TRUE;
else return FALSE;
}
void Push(Stack &S,BiTree e)
{
* S.top ++ = e;
}
void Pop(Stack &S,BiTree &e)
{
e = *( --S.top );
}
BiTree GetTop(Stack S)
{
return *(S.top-1);
}
//----------二叉树的函数定义----------
void CreateBiTree(BiTree &T)
{//按先序次序输入二叉树中结点的值（一个字符），# 代表空树 ，如：ABC##DE#G##F###
//则前序遍历：ABCDEGF 中序遍历：CBEGDFA
后序遍历：CGEFDBA
char ch = getchar();
if(ch == '#') T = NULL;
else {
if(!(T = (BiTNode
*)malloc(sizeof(BiTNode)))) exit(OVERFLOW);
T->data =
ch; //生成根结点
CreateBiTree(T->lchild); //构造左子树
CreateBiTree(T->rchild); //构造右子树
}
}//CreateBiTree
void Visit(char c)
{
printf("%c",c);
}
void PreOrderTraverse(BiTree T)
{//先序遍历二叉树，递归
if(T){
Visit(T->data);
PreOrderTraverse(T->lchild);
PreOrderTraverse(T->rchild);
}
}
void PostOrderTraverse(BiTree T)
{//先序遍历二叉树，递归
if(T){
PostOrderTraverse(T->lchild);
PostOrderTraverse(T->rchild);
Visit(T->data);
}
}
void InOrderTraverse(BiTree T)
{//中序遍历二叉树，非递归
Stack S;InitStack(S);
BiTree p = T;
while( p ||
!StackEmpty(S)) {
//printf("\n%%%%%%%%%%%%调试%%%%%%%%%%%%%%%%%%%%\n");
//PreOrderTraverse(p);
//PreOrderTraverse(GetTop(S));
//printf("\n%%%%%%%%%%%%调试%%%%%%%%%%%%%%%%%%%%\n");
if(p)
{Push(S,p); p =
p->lchild;}
if( p == NULL &&
!StackEmpty(S)) {
// printf("dddd\n");
Pop(S,p);//空指针退栈
Visit(p->data);
p =
p->rchild;
}//else
}//while
}
void CountLeaf (BiTree T, int& count){
if ( T ) {
if ((!T->lchild)&& (!T->rchild))
count++;
// 对叶子结点计数
CountLeaf( T->lchild, count);
CountLeaf( T->rchild, count);
} // if
} // CountLeaf
int Depth (BiTree T ){ // 返回二叉树的深度
int depthval,depthLeft,depthRight;
if ( !T
) depthval =
0;
else {
depthLeft = Depth( T->lchild
);
depthRight= Depth( T->rchild
);
depthval = 1 + ( depthLeft >
depthRight ? depthLeft : depthRight);
}
return depthval;
}
int main()
{
BiTree T;
int count = 0;
int num,init=0;
int
door=1;//控制是否退出最外层while循环
while( door )
{
printf("-----------------------------------------------------------------\n");
printf("\n
如要对二叉树进行操作，请输入各项前面相应的数字\n");
printf("
************************************\n");
printf("
| 1、创建二叉树
|\n");
printf("
| 2、先序遍历（递归）
|\n");
printf("
| 3、中序遍历（非递归）
|\n");
printf("
| 4、后序遍历（递归）
|\n");
printf("
| 5、求叶子节点个数
|\n");
printf("
| 6、求树的深度
|\n");
printf("
| 0、退出
|\n");
printf("
************************************\n");
printf(" 请输入数字进行操作：");
scanf("%d",&num);
if(num==0||num==1||num==2||num==3||num==4||num==5||num==6)
{
printf("\n-----------------------------------------------------------------\n");
switch( num
)
{
case
0:
door
= 0;
break;
case
1:
printf("请按先序次序输入二叉树的结点(以A、B、C等代表结点，#
代表空)，如ABC##DE#G##F###\n");
getchar();//清屏函数
CreateBiTree(T);
init=1;
break;
case
2:
if(init){
printf("先序遍历为：");
PreOrderTraverse (T);
printf("\n"); break;
}
else{
printf("请先创建二叉树！\n"); break;}
case
3:
if(init){
printf("中序遍历为：");
InOrderTraverse(T);
printf("\n"); break;
}
else{
printf("请先创建二叉树！\n"); break;}
case
4:
if(init){
printf("后序遍历为：");
PostOrderTraverse(T);
printf("\n"); break;
}
else{
printf("请先创建二叉树！\n"); break;}
case
5:
if(init){
CountLeaf(T,count); printf("叶子结点个数为：%d\n",count); break;
}
else{
printf("请先创建二叉树！\n"); break;}
case
6:
if(init){
printf("树的深度为：%d\n",Depth(T)); break;
}
else{
printf("请先创建二叉树！\n"); break;}
}//switch
}//if
else
{printf("输入不正确请重新输入！\n");continue;}
}//while
return 0;
}