11817: 数据结构/二叉树/创建与遍历(软件1、2)

Memory Limit:8 MB Time Limit:1.000 S
Judge Style:Text Compare Creator:
Submit:2 Solved:0

Description

 

实验原理:

  二叉树是最重要的一类树型结构,而二叉链表是二叉树的一种比较直观和灵活的存储结构。在二叉链表中的每个结点由三部分组成:左孩子指针、右孩子指针和结点数据。

  其中左右孩子指针分别指向本结点的左右孩子结点,如果一个结点的左右孩子不存在,则对应的指针记录为空值,C语言用NULL表示,画图时用^表示。

  结点数据的数据类型应该根据实际应用进行选择,在本次实验中,选用字符类型。

 

  输入创建原理:

  创建二叉树可以用递归方式进行,下面用伪代码来描述创建流程:

  1、结点* 创建结点函数(){

                    定义结点数据;

      输入结点数据;

      如果 结点数据为空 则返回NULL;//规定输入字符^表示本结点不创建

      创建结点* node;

      赋值node的数据为刚刚输入的结点数据;

      node.左孩子=创建结点函数();

      node.右孩子=创建结点函数();

      返回 node;

             }

  2、在需要创建整棵二叉树的地方写上:

       二叉树根结点 = 创建结点函数()

    遍历原理:要自己描述先序遍历、中序遍历原理。

 

实验步骤:

  1、定义二叉链表结点类型;

  2、实现二叉链表创建方法;

  3、实现二叉链表的先序、中序遍历方法;

  4、实现主函数

Input

 

 

每行一棵非空的二叉树,每棵二叉树按先序遍历形式,空指针用字符^占位,如图的一棵二叉树。

如果读到一行的第一个字符就是^,表示没有更多输入了,程序退出。

测试时,每棵树不会超过20个结点。

输入是:

AB^DE^^^C^^

^

 

   

Output

 

对于每个二叉树,分别进行先序遍历、中序遍历,每种遍历结果输出一行。

Sample Input Copy

DL^^R^^
AB^DE^^^C^^
^

Sample Output Copy

DLR
LDR
ABDEC
BEDAC

HINT

1、主函数可以采用以下流程

  int main(){

    定义结点指针;

             do{

      结点指针=创建结点函数();

      if (结点指针非空){

        先序遍历;换行

        中序遍历;换行

                   }

    }while(结点指针非空);

    return 0;

      }

2、

如果不采用一次输入一行字符串处理其中每个字符,而是采用每次输入一个字符处理,需要略过空白换行等字符,如下:

char ch;
do{
 scanf("%c",&ch);
}while(ch<=32);//确保读到一个非空白非换行的字符