问题 21926. -- 数据结构/二叉树/创建与遍历

21926: 数据结构/二叉树/创建与遍历

时间限制: 1 Sec  内存限制: 8 MB
献花: 60  解决: 10
[献花][花圈]

题目描述

实验原理:

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

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

  结点数据的数据类型应该根据实际应用选择,在本次实验中,为了方便输入和输出,我们选用字符类型。

 

  输入创建原理:

  二叉树虽然可以很复杂,但是创建二叉树可以用递归方式进行,代码只需要几行,下面我们用伪代码来描述创建流程:

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

                    定义结点数据;

      输入结点数据;

      如果 结点数据为空 则返回NULL;//这里比较重要,我们规定输入字符^表示本结点不创建

      创建结点* node;

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

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

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

      返回 node;

             }

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

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

    遍历原理:先根遍历、后根遍历、中根遍历原理,请自行补充,

 

实验步骤:

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

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

  3、实现二叉链表的三种遍历方法;

  4、实现主函数

  

思考题:

  1:为什么很多数据结构会有遍历的需求?

  2:如何干净地释放整棵二叉树动态申请的所有结点?

 

程欣宇2014年4月

输入

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

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

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

二叉树

输入是:

AB^DE^^^C^^

^

输出

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

样例输入

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

样例输出

DLR
LDR
LRD
ABDEC
BEDAC
EDBCA

提示


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



  int main(){



    定义结点指针;



             do{



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



      if (结点指针非空){



        先根遍历;换行



        中根遍历;换行



        后根遍历;换行



                   }



    }while(结点指针非空);



    return 0;



      }



2、



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



char ch;

do{

 scanf("%c",&ch);

}while(ch<=32);//确保读到一个非空白非换行的字符



 

来源

[献花][花圈]