《数据结构》 实验报告

题目： 树和二叉树

一、 用二叉树来表示代数表达式

（一）需求分析

输入一个正确的代数表达式，包括数字和用字母表示的数，运算符号+ - * / ^ =及括号。系统根据输入的表达式建立二叉树，按照先括号里面的后括号外面的，先乘后除的原则，每个节点里放一个数字或一个字母或一个操作符，括号不放在节点里。分别先序遍历，中序遍历，后序遍历此二叉树，并输出表达式的前缀式，中缀式和后缀式。

（二）系统设计

1. 本程序中用到的所有抽象数据类型的定义；

typedef struct BiNode //二叉树的存储类型

{ char s[20]; struct BiNode *lchild,*rchild;

}BiTNode,*BiTree;

2. 主程序的流程以及各程序模块之间的层次调用关系，函数的调用关系图：

3．列出各个功能模块的主要功能及输入输出参数

void push(char cc)

初始条件：输入表达式中的某个符号

操作结果：将输入的字符存入buf数组中去

BiTree Create_RTree()

初始条件：给出二叉树的定义表达式

操作结果：构造二叉树的右子树，即存储表达式等号右侧的字符组

BiTree Create_RootTree()

初始条件：给出二叉树的定义表达式

操作结果：构造存储输入表达式的二叉树，其中左子树存储‘X’，根节点存储‘：=’ void PreOrderTraverse(BiTree T)

初始条件：二叉树T存在

操作结果：先序遍历T，对每个节点调用函数Visit一次且仅一次

void InOrderTraverse(BiTree T)

初始条件：二叉树T存在

操作结果：中序遍历T，对每个节点调用函数Visit一次且仅一次

void PostOrderTraverse(BiTree T)

初始条件：二叉树T存在

操作结果：后序遍历T，对每个节点调用函数Visit一次且仅一次

int main()

主函数，调用各方法，操作成功后返回0

（三）调试分析

调试过程中还是出现了一些拼写错误，经检查后都能及时修正。有些是语法设计上的小错误，比如一些参变量的初始值设置错误，使得程序调试出错。还有操作符优先级设计不够合理，在输出遍历表达式结果时有错误。在小组讨论分析后纠正了这些结果，并尽量改进了算法的性能，减小时间复杂度。

有输入表达式建立二叉树的时间复杂度为O(n),先序遍历和中序遍历及后序遍历的时间复杂度都为O(n).

（四）测试结果

X：=(-b+(b^2-4*a*c)^0.5)/(2*a)

（五）用户手册

打开界面后，根据提示，输入代数表达式，包括包括数字和用字母表示的数，运算符号+ - * / ^ =及括号。输入完毕回车后系统将显示表达式的前缀式，中缀式，后缀式。

（六）附录

源程序：

#include<stdio.h>

#include<stdlib.h>

#include <string.h>

typedef struct BiNode {

char ch,bt[1024]; int len=0;

void push(char c) {

}

BiTree Create_RTree() {

BiTree T,Q,S; char *p; while(ch!=EOF) { ch=getchar(); if(ch=='\n') { } if(len>0) { } return NULL; //输入结束，堆栈中为右节点的值 if((Q=(BiTNode*)malloc(sizeof(BiTNode)))==NULL) return NULL; memset(Q->s,0x00,sizeof(Q->s)); Q->lchild=NULL; Q->rchild=NULL; memcpy(Q->s,bt,len); len =0; return Q; if (len<1024) bt[len++] = c; char s[20]; struct BiNode *lchild,*rchild; }BiTNode,*BiTree;

else if (ch == '(') {

if((Q=(BiTNode*)malloc(sizeof(BiTNode)))==NULL) return NULL; memset(Q->s,0x00,sizeof(Q->s)); Q->rchild = NULL;

} Q->lchild =Create_RTree(); ch=getchar(); if(ch=='\n') return Q; Q->s[0]=ch; Q->rchild=Create_RTree(); return Q;

else if(ch ==')')

{

} if(len>0) { } return NULL; if((Q=(BiTNode*)malloc(sizeof(BiTNode)))==NULL) return NULL; memset(Q->s,0x00,sizeof(Q->s)); Q->lchild=NULL; Q->rchild=NULL; memcpy(Q->s,bt,len); len=0; return Q;

else if(ch =='+'||ch=='-'||ch =='*'||ch =='/'||ch =='^') {

if((T=(BiTNode*)malloc(sizeof(BiTNode)))==NULL) return NULL; return NULL; if((Q=(BiTNode*)malloc(sizeof(BiTNode)))==NULL) memset(Q->s,0x00,sizeof(Q->s)); memset(T->s,0x00,sizeof(T->s)); T->lchild=NULL; T->rchild=NULL; if(len==0) { if(ch =='+'||ch =='-') { // 只有+-号前面可以不是数字,此时左节点为空 T->s[0]=ch; if((S=(BiTNode*)malloc(sizeof(BiTNode)))==NULL) return NULL; memset(S->s,0x00,sizeof(S->s)); S->lchild=NULL; S->rchild=NULL; p=S->s;

} } else while(1) { } T->rchild=S; ch=getchar(); if(ch=='+'||ch =='-'||ch =='*'||ch =='/'||ch=='^') break; *p++=ch; return NULL;

else

{

}

BiTNode *Create_RootTree()

{

BiTree Q,T; while((ch=getchar())!= EOF) { if (ch=='\n') { } return NULL; } return NULL; } Q->lchild=T; Q->s[0]=ch; if((Q->rchild = Create_RTree()) == NULL) else return Q; return NULL; //堆栈中为左节点值 memcpy(T->s,bt,len); len =0; } else push(ch);

else if(ch==':') //构造根节点：= {

ch=getchar(); if(ch!='=') return NULL; if((Q=(BiTNode*)malloc(sizeof(BiTNode)))==NULL)

} return NULL; memset(Q->s,0x00,sizeof(Q->s)); memcpy(Q->s,bt,len); len =0; Q->lchild = NULL; Q->rchild = NULL; if((T=(BiTNode*)malloc(sizeof(BiTNode)))==NULL) return NULL; T->lchild = Q; memset(T->s,0x00,sizeof(T->s)); memcpy(T->s,":=",2); //继续处理:=后面的数据，作为根节点的右节点 if((T->rchild=Create_RTree())==NULL) return NULL; return T;

else

{

}

void PreOrderTraverse(BiTree T) {

}

void InOrderTraverse(BiTree T) {

if(T) { } else InOrderTraverse(T->lchild); printf("%s ",T->s); InOrderTraverse(T->rchild); if(T) { } else return; printf("%s ",T->s); PreOrderTraverse(T->lchild); PreOrderTraverse(T->rchild); } return NULL; } push(ch);

}

{ } return;

void PostOrderTraverse(BiTree T) {

}

int main()

{

} printf("请输入一个中缀表达式：\n"); BiTree T=NULL; if((T=Create_RootTree())==NULL) return 0; printf("先序遍历："); PreOrderTraverse(T); printf("\n"); printf("中序遍历："); InOrderTraverse(T); printf("\n"); printf("后序遍历："); PostOrderTraverse(T); printf("\n"); return 0; if(T) { } else return; PostOrderTraverse(T->lchild); PostOrderTraverse(T->rchild); printf("%s ",T->s);

测试数据结果：

X：=(-b+(b^2-4*a*c)^0.5)/(2*a)

二、求二叉树中从根结点到叶子节点的路径

（一）需求分析

以无歧义的陈述说明程序设计的任务，强调程序要做什么。明确规定：

（1）．输入的形式和输入值的范围；

（2） 输出的形式

（3） 程序所能达到的功能

（4） 测试数据：包括正确的输入及其输出结果，含有错误的输入及其输出结果。

（二）系统设计

1． 说明本程序中用到的所有抽象数据类型的定义；

typedef char ElemType;

typedef struct node

{ ElemType data;

struct node *lchild;

struct node *rchild;

}BiTNode;

2． 主程序的流程以及各程序模块之间的层次调用关系，画出函数的调用关系图。

3． 列出各个功能模块的主要功能及输入输出参数。

（三）调试分析

内容包括：

（1）．调试过程中遇到的问题是如何解决的及对设计与实现的回顾讨论与分析。

（2） 算法的时间复杂度分析（包括基本操作和其他算法）和改进设想；

（3） 经验与体会等。

（四）测试结果

（五）用户手册

说明如何使用你编写的程序，详细列出每一步操作步骤。

（六）附录

#include <iostream>

#define NULL 0

#define Max 50

using namespace std;

typedef struct node

{

char data;

struct node *lc,*rc;

}btnode;

void creattree(btnode *&b) {//递归创建二叉树

char i;

cin>>i;

if(i=='#') b=NULL;

else{

b=(btnode *)malloc(sizeof(btnode));

b->data=i;

creattree(*&b->lc);

creattree(*&b->rc);

}

}

void findleafnode(btnode *b) {//找出所有叶子结点

}

btnode *st[Max];

int front,rear=-1;

void allpath(btnode *b){ //从叶子结点到根结点的路径

if(b!=NULL){ rear++; if(b!=NULL){ } if(b->lc==NULL&&b->rc==NULL) cout<<b->data<<' '; else{ } findleafnode(b->lc); findleafnode(b->rc);

st[rear]=b;//当前结点入栈

if(b->lc==NULL&&b->rc==NULL){ //当b为叶子结点时 front=rear; while(front>=0){//输出从根节点到叶子结点的路径 cout<<st[front]->data<<' ';

front--;

} cout<<endl; rear--; //栈尾指针退一步

//重设栈头指针

}

else{

allpath(b->lc);

allpath(b->rc);

rear--;

}

void main(){

btnode *b; cout<<"请以先序构造一棵树，无结点时以‘#’代替"; cout<<endl; } }

creattree(b);

cout<<"叶子结点为："<<endl;

findleafnode(b);

cout<<endl;

cout<<"从所有叶子结点到根结点的路径为："<<endl; allpath(b);

}

cout<<"以上路径中第一条最长路径是："<<endl;

 

第二篇：树和二叉树实验报告

                           树和二叉树

                                           

一、实验目的

1.      掌握二叉树的结构特征，以及各种存储结构的特点及适用范围。

2.      掌握用指针类型描述、访问和处理二叉树的运算。

二、实验要求

1.      认真阅读和掌握本实验的程序。

2.      上机运行本程序。

3.      保存和打印出程序的运行结果，并结合程序进行分析。

4.      按照二叉树的操作需要，重新改写主程序并运行，打印出文件清单和运行结果。

三、实验内容

1.      输入字符序列，建立二叉链表。

2.      按先序、中序和后序遍历二叉树（递归算法）。

3.      按某种形式输出整棵二叉树。

4.      求二叉树的高度。

5.      求二叉树的叶节点个数。

6.      交换二叉树的左右子树。

7.      借助队列实现二叉树的层次遍历。

8.      在主函数中设计一个简单的菜单，分别调试上述算法。

为了实现对二叉树的有关操作，首先要在计算机中建立所需的二叉树。建立二叉树有各种不同的方法。一种方法是利用二叉树的性质5来建立二叉树，输入数据时要将节点的序号（按满二叉树编号）和数据同时给出：（序号，数据元素0）。另一种方法是主教材中介绍的方法，这是一个递归方法，与先序遍历有点相似。数据的组织是先序的顺序，但是另有特点，当某结点的某孩子为空时以字符“#”来充当，也要输入。若当前数据不为“#”，则申请一个结点存入当前数据。递归调用建立函数，建立当前结点的左右子树。

四、解题思路

1、先序遍历：1访问根结点，2先序遍历左子树，3先序遍历右子树

2、中序遍历：1中序遍历左子树，2访问根结点，3中序遍历右子树

3、后序遍历：1后序遍历左子树，2后序遍历右子树，3访问根结点

4、层次遍历算法：采用一个队列q，先将二叉树根结点入队列，然后退队列，输出该结点；若它有左子树，便将左子树根结点入队列；若它有右子树，便将右子树根结点入队列，直到队列空为止。因为队列的特点是先进后出，所以能够达到按层次遍历二叉树的目的。

五、程序清单

#include<stdio.h>

#include<stdlib.h>

#define M 100

typedef char Etype;                               //定义二叉树结点值的类型为字符型

typedef struct BiTNode                            //树结点结构

{ 

    Etype data;

    struct BiTNode *lch,*rch;

}BiTNode,*BiTree;

BiTree que[M];

int front=0,rear=0;

//函数原型声明

BiTNode *creat_bt1();

BiTNode *creat_bt2();

void preorder(BiTNode *p);

void inorder(BiTNode *p);

void postorder(BiTNode *p);

void enqueue(BiTree);

BiTree delqueue( );

void levorder(BiTree);

int treedepth(BiTree);

void prtbtree(BiTree,int);

void exchange(BiTree);

int leafcount(BiTree);

void paintleaf(BiTree);

BiTNode *t;

int count=0;

//主函数

void main()

{

    char ch;

    int k;

    do{

        printf("\n\n\n");

        printf("\n===================主菜单===================");

        printf("\n\n   1.建立二叉树方法1");

        printf("\n\n   2.建立二叉树方法2");

        printf("\n\n   3.先序递归遍历二叉树");

        printf("\n\n   4.中序递归遍历二叉树");

        printf("\n\n   5.后序递归遍历二叉树");

        printf("\n\n   6.层次遍历二叉树");

        printf("\n\n   7.计算二叉树的高度");

        printf("\n\n   8.计算二叉树中叶结点个数");

        printf("\n\n   9.交换二叉树的左右子树");

        printf("\n\n   10.打印二叉树");

        printf("\n\n   0.结束程序运行");

        printf("\n============================================");

        printf("\n   请输入您的选择(0,1,2,3,4,5,6,7,8,9,10)");

        scanf("%d",&k);

        switch(k)

        {

            case 1:t=creat_bt1( );break;                  //调用性质5建立二叉树算法

            case 2:printf("\n请输入二叉树各结点值:");fflush(stdin);

            t=creat_bt2();break;                        //调用递归建立二叉树算法

            case 3:if(t)

                   {printf("先序遍历二叉树:");

                   preorder(t);

                   printf("\n");

                   }

                   else printf("二叉树为空!\n");

                   break;

            case 4:if(t)

                   {printf("中序遍历二叉树:");

                   inorder(t);

                   printf("\n");

                   }

                   else printf("二叉树为空!\n");

                   break;

            case 5:if(t)

                   {printf("后序遍历二叉树:");

                   postorder(t);

                   printf("\n");

                   }

                   else printf("二叉树为空!\n");

                   break;

            case 6:if(t)

                   {printf("层次遍历二叉树：");

                    levorder(t);

                    printf("\n");

                   }

                   else printf("二叉树为空！\n");

                   break;

            case 7:if(t)

                   {printf("二叉树的高度为：%d",treedepth(t));

                    printf("\n");

                   }

                   else printf("二叉树为空！\n");

                   break;

            case 8:if(t)

                   {printf("二叉树的叶子结点数为：%d\n",leafcount(t));

                    printf("二叉树的叶结点为：");paintleaf(t);

                    printf("\n");

                   }

                   else printf("二叉树为空！\n");

                   break;

            case 9:if(t)

                   {printf("交换二叉树的左右子树：\n");

                    exchange(t);

                    prtbtree(t,0);

                    printf("\n");

                   }

                   else printf("二叉树为空！\n");

                   break;

            case 10:if(t)

                    {printf("逆时针旋转90度输出的二叉树：\n");

                     prtbtree(t,0);

                     printf("\n");

                    }

                    else printf("二叉树为空！\n");

                    break;

            case 0:exit(0);

            }   //switch

    }while(k>=1&&k<=10);

        printf("\n再见！按回车键，返回…\n");

        ch=getchar();

}   //main

//利用二叉树性质5，借助一维数组V建立二叉树

BiTNode *creat_bt1()

{ BiTNode *t,*p,*v[20];int i,j;Etype e;

/*输入结点的序号i、结点的数据e*/

printf("\n请输入二叉树各结点的编号和对应的值（如1，a）：");

scanf("%d,%c",&i,&e);

while(i!=0&&e!='#')                                //当i为0，e为'#'时，结束循环

{

    p=(BiTNode*)malloc(sizeof(BiTNode));

    p->data=e;

    p->lch=NULL;

    p->rch=NULL;

    v[i]=p;

    if(i==1)

    t=p;   //序号为1的结点是根

    else

    {

        j=i/2;

        if(i%2==0)v[j]->lch=p;                        //序号为偶数，作为左孩子

        else  v[j]->rch=p;                            //序号为奇数，作为右孩子

    }

    printf("\n请继续输入二叉树各结点的编号和对应的值：");

    scanf("%d,%c",&i,&e);

}

return(t);

}//creat_bt1;

//模仿先序递归遍历方法，建立二叉树

BiTNode *creat_bt2()

{

    BiTNode *t;

    Etype e;

    scanf("%c",&e);

    if(e=='#')t=NULL;   //对于'#'值，不分配新结点

    else{

            t=(BiTNode *)malloc(sizeof(BiTNode));

            t->data=e;

            t->lch=creat_bt2();                               //左孩子获得新指针值

            t->rch=creat_bt2();                               //右孩子获得新指针值

          }

return(t);

}   //creat_bt2

//先序递归遍历二叉树

void preorder(BiTNode *p)

{if(p){

        printf("%3c",p->data);

        preorder(p->lch);

        preorder(p->rch);

    }

}    //preorder

//中序递归遍历二叉树

void inorder(BiTNode *p)

{if(p){

        inorder(p->lch);

        printf("%3c",p->data);

        inorder(p->rch);

    }

} //inorder

//后序递归遍历二叉树

void postorder(BiTNode *p)

{ if(p){ postorder(p->lch);

         postorder(p->rch);

         printf("%3c",p->data);

     }

} //postorder

void enqueue(BiTree T)

{

    if(front!=(rear+1)%M)

    {rear=(rear+1)%M;

    que[rear]=T;}

}

BiTree delqueue( )

{

    if(front==rear)return NULL;

    front=(front+1)%M;

    return(que[front]);

}

void levorder(BiTree T)                                          //层次遍历二叉树

{

    BiTree p;

    if(T)

    {enqueue(T);

       while(front!=rear){

        p=delqueue(  );

        printf("%3d",p->data);

        if(p->lch!=NULL)enqueue(p->lch);

        if(p->rch!=NULL)enqueue(p->rch);

        }

    }

}

int treedepth(BiTree bt)                                        //计算二叉树的高度

{

    int hl,hr,max;

    if(bt!=NULL)

    {  hl=treedepth(bt->lch);

       hr=treedepth(bt->rch);

       max=(hl>hr)?hl:hr;

       return (max+1);

    }

    else return (0);

}

void prtbtree(BiTree bt,int level)                       //逆时针旋转90度输出二叉树树形

{int j;

if(bt)

{prtbtree(bt->rch,level+1);

for(j=0;j<=6*level;j++)printf(" ");

printf("%c\n",bt->data);

prtbtree(bt->lch,level+1);

}

}

void exchange(BiTree bt)  //交换二叉树左右子树

{BiTree p;

if(bt)

{p=bt->lch;bt->lch=bt->rch;bt->rch=p;

exchange(bt->lch);exchange(bt->rch);

}

}

int leafcount(BiTree bt)  //计算叶结点数

{

if(bt!=NULL)

{leafcount(bt->lch);

leafcount(bt->rch);

if((bt->lch==NULL)&&(bt->rch==NULL))

    count++;

}

return(count);

}

void paintleaf(BiTree bt)   //输出叶结点

{if(bt!=NULL)

    {if(bt->lch==NULL&&bt->rch==NULL)

        printf("%3c",bt->data);

    paintleaf(bt->lch);

  

 paintleaf(bt->rch);

    }

}

图11.2所示二叉树的输入数据顺序应该是：abd#g###ce#h##f##。

图11.2  二叉树示意图

运行结果：

===================主菜单===================

   1.建立二叉树方法1

   2.建立二叉树方法2

   3.先序递归遍历二叉树

   4.中序递归遍历二叉树

   5.后序递归遍历二叉树

   6.层次遍历二叉树

   7.计算二叉树的高度

   8.计算二叉树中叶结点个数

   9.交换二叉树的左右子树

   10.打印二叉树

   0.结束程序运行

============================================

   请输入您的选择(0,1,2,3,4,5,6,7,8,9,10) 1

请输入二叉树各结点的编号和对应的值（如1，a）：1，a

请继续输入二叉树各结点的编号和对应的值：2，b

请继续输入二叉树各结点的编号和对应的值：3，c

请继续输入二叉树各结点的编号和对应的值：4，d

请继续输入二叉树各结点的编号和对应的值：6，e

请继续输入二叉树各结点的编号和对应的值：7，f

请继续输入二叉树各结点的编号和对应的值：9，g

请继续输入二叉树各结点的编号和对应的值：13，h

请继续输入二叉树各结点的编号和对应的值：0，#

===================主菜单===================");

   1.建立二叉树方法1

   2.建立二叉树方法2

   3.先序递归遍历二叉树

   4.中序递归遍历二叉树

   5.后序递归遍历二叉树

   6.层次遍历二叉树

   7.计算二叉树的高度

   8.计算二叉树中叶结点个数

   9.交换二叉树的左右子树

   10.打印二叉树

   0.结束程序运行

============================================

   请输入您的选择(0,1,2,3,4,5,6,7,8,9,10) 3

先序遍历二叉树：a  b  d  g  c  e  h  f

===================主菜单===================");

   1.建立二叉树方法1

   2.建立二叉树方法2

   3.先序递归遍历二叉树

   4.中序递归遍历二叉树

   5.后序递归遍历二叉树

   6.层次遍历二叉树

   7.计算二叉树的高度

   8.计算二叉树中叶结点个数

   9.交换二叉树的左右子树

   10.打印二叉树

   0.结束程序运行

============================================

   请输入您的选择(0,1,2,3,4,5,6,7,8,9,10) 4

中序遍历二叉树：d  g  b  a  e  h  c  f

===================主菜单===================");

   1.建立二叉树方法1

   2.建立二叉树方法2

   3.先序递归遍历二叉树

   4.中序递归遍历二叉树

   5.后序递归遍历二叉树

   6.层次遍历二叉树

   7.计算二叉树的高度

   8.计算二叉树中叶结点个数

   9.交换二叉树的左右子树

   10.打印二叉树

   0.结束程序运行

============================================

   请输入您的选择(0,1,2,3,4,5,6,7,8,9,10) 5

后序遍历二叉树：g  d  b  h  e  f  c  a 

===================主菜单===================");

   1.建立二叉树方法1

   2.建立二叉树方法2

   3.先序递归遍历二叉树

   4.中序递归遍历二叉树

   5.后序递归遍历二叉树

   6.层次遍历二叉树

   7.计算二叉树的高度

   8.计算二叉树中叶结点个数

   9.交换二叉树的左右子树

   10.打印二叉树

   0.结束程序运行

============================================

   请输入您的选择(0,1,2,3,4,5,6,7,8,9,10) 6

层次遍历二叉树： 97 98 99100101102103104

===================主菜单===================");

   1.建立二叉树方法1

   2.建立二叉树方法2

   3.先序递归遍历二叉树

   4.中序递归遍历二叉树

   5.后序递归遍历二叉树

   6.层次遍历二叉树

   7.计算二叉树的高度

   8.计算二叉树中叶结点个数

   9.交换二叉树的左右子树

   10.打印二叉树

   0.结束程序运行

============================================

   请输入您的选择(0,1,2,3,4,5,6,7,8,9,10) 7

二叉树的高度为：4

===================主菜单===================");

   1.建立二叉树方法1

   2.建立二叉树方法2

   3.先序递归遍历二叉树

   4.中序递归遍历二叉树

   5.后序递归遍历二叉树

   6.层次遍历二叉树

   7.计算二叉树的高度

   8.计算二叉树中叶结点个数

   9.交换二叉树的左右子树

   10.打印二叉树

   0.结束程序运行

============================================

   请输入您的选择(0,1,2,3,4,5,6,7,8,9,10) 8

二叉树的叶子结点数为：3

二叉树的叶结点为： g  h  f

===================主菜单===================");

   1.建立二叉树方法1

   2.建立二叉树方法2

   3.先序递归遍历二叉树

   4.中序递归遍历二叉树

   5.后序递归遍历二叉树

   6.层次遍历二叉树

   7.计算二叉树的高度

   8.计算二叉树中叶结点个数

   9.交换二叉树的左右子树

   10.打印二叉树

   0.结束程序运行

============================================

   请输入您的选择(0,1,2,3,4,5,6,7,8,9,10) 9

交换二叉树的左右子树：

            d

                   g

      b

 a

            e

                   h

      c

            f

===================主菜单===================");

   1.建立二叉树方法1

   2.建立二叉树方法2

   3.先序递归遍历二叉树

   4.中序递归遍历二叉树

   5.后序递归遍历二叉树

   6.层次遍历二叉树

   7.计算二叉树的高度

   8.计算二叉树中叶结点个数

   9.交换二叉树的左右子树

   10.打印二叉树

   0.结束程序运行

============================================

   请输入您的选择(0,1,2,3,4,5,6,7,8,9,10) 10

逆时针旋转90度输出的二叉树：

            d

                   g

      b

 a

            e

                   h

      c

            f

===================主菜单===================");

   1.建立二叉树方法1

   2.建立二叉树方法2

   3.先序递归遍历二叉树

   4.中序递归遍历二叉树

   5.后序递归遍历二叉树

   6.层次遍历二叉树

   7.计算二叉树的高度

   8.计算二叉树中叶结点个数

   9.交换二叉树的左右子树

   10.打印二叉树

   0.结束程序运行

============================================

   请输入您的选择(0,1,2,3,4,5,6,7,8,9,10) 2

请输入二叉树各结点值：abd#g###ce#h##f##

===================主菜单===================");

   1.建立二叉树方法1

   2.建立二叉树方法2

   3.先序递归遍历二叉树

   4.中序递归遍历二叉树

   5.后序递归遍历二叉树

   6.层次遍历二叉树

   7.计算二叉树的高度

   8.计算二叉树中叶结点个数

   9.交换二叉树的左右子树

   10.打印二叉树

   0.结束程序运行

============================================

   请输入您的选择(0,1,2,3,4,5,6,7,8,9,10) 0

请按任意键继续. . .

六、调试心得及收获

建立二叉树有两种方法：一种方法是利用二叉树的性质5来建立二叉树；另一种方法是主教材中介绍的方法，这是一个递归方法，与先序遍历有点相似。建立后，通过先序、中序、后序遍历，对二叉树有了进一步的理解与掌握。对二叉树中各种计算也更了解了！

七、其他所想到的

一个二叉树，有许多部分构成，每一个部分都需要精心编写，才能对其进行操作，不至于出错。