C语言算法实验-二叉树_按先序次序输入二叉树中结点的值,空格字符表示空树

实验内容与要求

问题描述：

建立一棵二叉树，试编程实现二叉树的如下基本操作：

 1. 按先序序列构造一棵二叉链表表示的二叉树T；

 2. 对这棵二叉树进行遍历：先序、中序、后序遍历，分别输出结点的遍历序列；

3. 求二叉树的叶结点数目；

要求：

n  设计要求

首先设计一个含有多个菜单项的主控菜单程序，然后再为这些菜单项配上相应的功能。

主控菜单设计要求：程序运行后，给出6个菜单项的内容和输入提示：

1．创建二叉树（先序）

2．先序遍历并输出遍历序列

3．中序遍历并输出遍历序列

4．后序遍历并输出遍历序列

5. 统计二叉树的叶子结点数

6．退出

请选择菜单1—6：

n  功能要求

完成各菜单的功能，并能正确显示遍历结果和叶子数目

从键盘接受输入（先序），以二叉链表作为存储结构，建立二叉树（以先序来建立），

如输入：ABC∅∅DE∅G∅∅F∅∅∅（其中∅表示空格字符）

二叉链表结点定义：

typedef  struct  BiTNode{

TElemType data;

struct BiTNode *lchild,*rchild;

}BiTNode,*BiTree;

n  实现要求

1)       用VC++的引用实现各功能的调用

2)       测试数据：

AB∅∅CDF∅∅∅EG∅∅H∅∅（其中∅表示空格字符）

先序序列：ABCDFEGH

中序序列：BAFDCGEH

后序序列：BFDGHECA

n  实验报告提交要求

1)       实现功能的全部程序

2)       附加输出结果（截屏贴于word文档）

3)       实验程序和运行结果必须于2018.5.25前提交 （电子）

#include <stdio.h> 

#include <stdlib.h> 

#include <malloc.h> 

#define OK 1 

#define ERROR 0 

#define OVERFLOW 0 

#define STACK_INIT_SIZE 100 

#define STACKINCREMENT 10 

typedef char TElemType; 

typedef int Status; 

//定义二叉链表的结点结构 

typedef struct BiTNode { // 结点结构                             

 TElemType data; 

 struct BiTNode  *lchild, *rchild; //左右孩子指针 

} BiTNode, *BiTree; 

typedef BiTree SElemType; 

typedef struct{ 

 SElemType *base;  //栈底指针 

 SElemType *top;   //栈顶指针 

 int stacksize;    //栈的容量 

}SqStack; //定义一个顺序栈 

Status InitStack(SqStack &S){ 

 S.base = (SElemType *)malloc(STACK_INIT_SIZE * sizeof(SElemType)); 

 if (!S.base){ 

  printf("栈溢出！\n"); 

  exit(OVERFLOW); 

 } 

 S.top = S.base; 

 S.stacksize = STACK_INIT_SIZE; 

 return OK; 

}//初始化一个顺序栈 

Status StackEmpty(SqStack S){ 

 if (S.top == S.base){ 

  return OK; 

 } 

 return ERROR; 

}//判断一个栈是否为空 

//往栈里面插入元素e 

Status Push(SqStack &S, BiTree p){ 

 if (S.top - S.base >= S.stacksize){ 

  S.base = (SElemType *)realloc(S.base, (S.stacksize + STACKINCREMENT) * sizeof(SElemType)); 

  if (!S.base){ 

   printf("栈溢出!\n"); 

   return OVERFLOW; 

  } 

  S.top = S.base + S.stacksize; 

  S.stacksize += STACKINCREMENT; 

 }//若栈满，追加存储空间 

 *S.top++ = p; 

 return OK; 

} 

//删除栈顶元素，用指针p返回栈里存放的根指针 

Status Pop(SqStack &S, BiTree &p){ 

 if (StackEmpty(S)) 

  return ERROR; //判空 

 p = *(--S.top); 

 return OK; 

} 

Status CreateBiTree(BiTree &T) 

{//按先序次序输入二叉树中结点的值，空格字符表示空树，构造二叉链表表示的二叉树T。 

char ch; 

scanf("%c",&ch); 

if(ch==' ')T=NULL;//输入n+1个节点

else{ 

    if(!(T=(BiTNode *)malloc(sizeof(BiTNode)))) 

        exit(OVERFLOW); 

    T->data=ch;      //生成根结点 

    CreateBiTree(T->lchild);//构造左子树 

    CreateBiTree(T->rchild);//构造右子树 

} 

return OK; 

} 

Status PrintElement(TElemType e) 

    { 

        printf("%c",e);//输出元素e的值

        return OK; 

    } 

Status PreOrderTraverse(BiTree T,Status(* Visit)(TElemType e)) 

{//采用二叉链表存储结构，Visit是对数据元素操作的应用函数 

    //先序遍历二叉树T的递归算法，对每个数据元素调用Visit函数 

    if(T){ 

        if(Visit(T->data)) 

            if(PreOrderTraverse(T->lchild,Visit)) 

                if(PreOrderTraverse(T->rchild,Visit)) return OK; 

                return ERROR; 

                } 

    else return OK; 

} 

Status InOrderTraverse(BiTree T,Status(*Visit)(TElemType e)) 

{//中序遍历二叉树T的递归算法，对每个数据元素调用函数Visit 

    if(T){ 

        if(InOrderTraverse(T->lchild,Visit))

            if(Visit(T->data)) 

                if(InOrderTraverse(T->rchild,Visit)) return OK; 

                return ERROR; 

                } 

    else return OK; 

} 

Status PostOrderTraverse(BiTree T,Status(*Visit)(TElemType e)) 

{//后序遍历二叉树T的递归算法，对每个数据元素调用Visit函数 

    if(T){ 

            if(PostOrderTraverse(T->lchild,Visit)) 

                if(PostOrderTraverse(T->rchild,Visit)) 

                    if(Visit(T->data))return OK; 

                return ERROR; 

                } 

    else return OK; 

} 

void CountLeaf(BiTree T,int& count) 

{//计算叶子结点数 

    if(T) 

    { 

        if((!T->lchild)&&(!T->rchild)) 

            count++; 

        CountLeaf(T->lchild,count); 

        CountLeaf(T->rchild,count); 

    } 

} 

void Welcome()

{

  printf("\n\n");

  printf("\t\t┏━━━━━━━━━━━━━━━┓\n");

  printf("\t\t┃    二叉树的遍历与运用        ┃\n");

  printf("\t\t┣━━━━━━━━━━━━━━━┫\n");

  printf("\t\t┃     1  创建二叉树（先序）    ┃\n");

  printf("\t\t┃     2  先序遍历并输出        ┃\n");

  printf("\t\t┃     3  中序遍历并输出        ┃\n");

  printf("\t\t┃     4  后序遍历并输出        ┃\n");

  printf("\t\t┃     5  统计叶子节点          ┃\n");

  printf("\t\t┃     6  退出系统              ┃\n");

  printf("\t\t┗━━━━━━━━━━━━━━━┛\n");

  printf("\t\t请选择:");

}

int main() 

{ 

    int n0=0;

       int choice;

    BiTree T; 

       do{

       Welcome();

       scanf("%d",&choice);

       switch(choice){

       case 1:

              printf("按先序次序输入一个二叉树的结点值(在结尾加入n+1个空格)：\n"); 

              if(CreateBiTree(T)) 

              { 

                     printf("创建二叉树成功\n"); 

              } 

              else 

                     printf("创建二叉树失败\n");

              break;

       case 2:

              printf("先序遍历结果为：\n"); 

              if(PreOrderTraverse(T,PrintElement)) 

              { 

                     printf("\n"); 

              } 

              else 

                     printf("遍历失败\n");

              break;

       case 3:

              printf("中序遍历结果为：\n"); 

              if(InOrderTraverse(T,PrintElement)) 

              { 

                      printf("\n"); 

              }    

              else 

                     printf("遍历失败\n"); 

              break;

    case 4:

              printf("后序遍历结果为：\n"); 

              if(PostOrderTraverse(T,PrintElement)) 

              { 

                     printf("\n"); 

              } 

              else 

                     printf("遍历失败\n");

              break;

       case 5:

              CountLeaf(T,n0); 

        printf("叶子的结点数位：%d\n",n0);

              break;

       case 6:

              return 0;

       default:

              printf("您的输入有误，请重新输入!");

       }

       }while(choice!=6);

    return 0; 

}