数据结构二叉树

实验项目名称：二叉树操作的实现
实验目的与要求:
1.基础知识:掌握数据结构中二叉树的相关知识;
2.参考教材相关算法，完成以下程序功能: .
(1)能够采用二叉链存储结构实现二叉树的建立;
(2)完成已建立的二叉树的三种遍历，并分别打印其结果;
(3)至少完成教材P121-122中其它任意一种操作，或者二叉树中特定结点的统计操作，如统计用户给定的元素数目、叶子数目、只有左或右孩子的结点数目等;
(4)程序中有友好的操作设计.
实验性质:验证性(4学时)
说明:程序包含的主要函数:主函数、操作界面、建树、独立的
三种遍历、其它自定义的操作算法，及相关注释;
注意:在主函数调用子函数流程中体现先建树后遍历和其它操作
的条件控制，即在调用除建树算法以外的其它所有算法前，先判
断树是否已经建立，若没建树，只能先建树，不能做其它操作。

二叉树源代码：

#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#define ERROR 0
#define OK 1
#define NULL 0
typedef int Status;
typedef char TElemType;
typedef struct BiTNode
{
    TElemType data;
    struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;

Status CreateBiTree(BiTree&T)//按先序次序输入二叉树结点的值（一个字符），#表示空树
{
       char ch;
       scanf("%c",&ch);
       if(ch=='#')
       T=NULL;   
       else{
       if(!(T=(BiTNode*)malloc(sizeof(BiTNode))))exit(ERROR);
       T->data=ch;
       CreateBiTree(T->lchild);
       CreateBiTree(T->rchild);}
    return 0;
}

LRD(BiTree T)//后序遍历
{
    if(T!=NULL)
    {
        LRD(T->lchild);
        LRD(T->rchild);
        printf("%c",T->data);
    }
    return OK;
}

LDR(BiTree T)//中序遍历
{
    if(T!=NULL)
    {
        LDR(T->lchild);
        printf("%c",T->data);
        LDR(T->rchild);
    }
    return OK;
}

DLR(BiTree T)//先序遍历
{
    if(T!=NULL)
    {
        printf("%c",T->data);
        DLR(T->lchild);
        DLR(T->rchild);
    }
    return OK;
}


Status TreeDeapth(BiTree T)
{
	int height,leftH,rightH;     //左右子树的深度和最深的深度
	if(T==NULL)
		height=0;
	else{
		leftH=TreeDeapth(T->lchild);
		rightH=TreeDeapth(T->rchild);
		if(leftH>rightH)
			height=leftH+1;
		else
			height=rightH+1;;
	}
	return height;

}
Status TreeEmpty(BiTree T)//判断树是否存在
{
    if(T==NULL)
    return ERROR;
    else
    return OK;
}

Status OperateMenu(int num)
{
    printf("------****操作菜单****------\n");
	printf("------    0 退出系统\n");
    printf("------    1 后序遍历\n");
    printf("------    2 中序遍历\n");
    printf("------    3 先序遍历\n");
    printf("------    4 判断树是否存在\n");
    printf("------    5 二叉树的深度\n");
    printf("------    6 创建二叉树\n");
    printf("------    请选择你所需要的操作\n");
    scanf("%d",&num);
	return num;
}
main()
{
    BiTree T;
    T=NULL;
    int num=-1,h;  
    while(num!=0)
    {
        {
       num=OperateMenu(num);
    }
    switch(num)
    {
        case 1:
        if(T==NULL)
        {printf("树不存在");}
        LRD(T);
        printf("\n");
        break;//后序遍历
        case 2: 
        if(T==NULL)
        {printf("树不存在");}
        LDR(T);
        printf("\n");
        break;//中序遍历
        case 3:
        if(T==NULL)
        {printf("树不存在");}
        DLR(T);
        printf("\n");
        break;//先序遍历
        case 4:
        if(TreeEmpty(T))
        printf("树存在\n");
        else
        printf("树不存在\n");break;
        case 5:
        if(T==NULL)
        {printf("树不存在\n");}
        else
        {h=TreeDeapth(T);
        printf("该树的最大深度为%d\n",h);}break;
        case 6:
        fflush(stdin);
        printf("按先序次序输入二叉树结点的值（一个字符）#表示空树\n");
        CreateBiTree(T);break;

    }
}
}