赞
踩
建立一棵二叉树,试编程实现二叉树的如下基本操作:
设计要求:
首先设计一个含有多个菜单项的主控菜单程序,然后再为这些菜单项配上相应的功能。
主控菜单设计要求:
程序运行后,给出6个菜单项的内容和输入提示:
请选择菜单1--6:
功能要求:
完成各菜单的功能,并能正确显示遍历结果和叶子数目
从键盘接受输入(先序),以二叉链表作为存储结构,建立二叉树(以先序来建立)
- #include <stdio.h>
- #include <stdlib.h>
-
- #define OVERFLOW -2
- #define OK 1
- typedef char TElemType;
-
-
- //二叉链表结点定义
- typedef struct BiTNode{
- TElemType data;
- struct BiTNode *lchild,*rchild;
- }BiTNode,*BiTree;
-
- BiTree T=NULL;
-
- //先序创建二叉树
- void CreateBiTree(BiTree &T)
- {
- char ch;
- scanf("%c",&ch);
- if(ch==' ')
- T=NULL;
- else{
- if(!(T=(BiTNode*)malloc(sizeof(BiTNode))))
- exit(OVERFLOW);
- T->data=ch;
- CreateBiTree(T->lchild);
- CreateBiTree(T->rchild);
- }
- }
-
-
- //先序遍历并输出遍历序列
- void PreOrder(BiTree T)
- {
- if(T){
- printf("%c",T->data);
- PreOrder(T->lchild);
- PreOrder(T->rchild);
- }
- }
-
-
- //中序遍历并输出遍历序列
- void InOrder(BiTree T)
- {
- if(T){
- InOrder(T->lchild);
- printf("%c",T->data);
- InOrder(T->rchild);
- }
- }
-
-
- //后序遍历并输出遍历序列
- void PostOrder(BiTree T)
- {
- if(T){
- PostOrder(T->lchild);
- PostOrder(T->rchild);
- printf("%c",T->data);
- }
- }
-
-
- //统计二叉树的叶子结点数
- void CountLeaf(BiTree T,int &count)
- {
- if(T){
- if((!T->lchild)&&(!T->rchild))
- count++;
- CountLeaf(T->lchild,count);
- CountLeaf(T->rchild,count);
- }
- }
-
-
-
- //主函数
- int main(){
- int choice;
- int count=0;
-
- printf("**********二叉树的遍历及应用**********\n");
- printf("1.创建二叉树(先序)\n");
- printf("2.先序遍历并输出遍历序列\n");
- printf("3.中序遍历并输出遍历序列\n");
- printf("4.后序遍历并输出遍历序列\n");
- printf("5.统计二叉树的叶子结点数\n");
- printf("6.退出\n");
- while(choice)
- {
- printf("请选择菜单1--6:\n");
- scanf("%d",&choice);
- if(choice>6||choice<=0)
- {
- printf("您输入的数据有误!\n");
- return 0;
- }
- while(choice<=6)
- {
- if(choice==1)
- {
- getchar();
- printf("先序创建二叉树:\n");
- printf("请输入字符串\n");
- CreateBiTree(T);
- break;
- }
- if(choice==2)
- {
- printf("先序遍历并输出遍历序列:\n");
- PreOrder(T);
- printf("\n");
- break;
- }
- if(choice==3)
- {
- printf("中序遍历并输出遍历序列:\n");
- InOrder(T);
- printf("\n");
- break;
- }
- if(choice==4)
- {
- printf("后序遍历并输出遍历序列:\n");
- PostOrder(T);
- printf("\n");
- break;
- }
- if(choice==5)
- {
- printf("统计二叉树的叶子结点数:\n");
- CountLeaf(T,count);
- printf("叶子结点数为:%d\n",count);
- break;
- }
- if(choice==6)
- {
- printf("退出\n");
- return 0;
- }
- }
- }
- }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。