【二叉树地创建与遍历实验报告】二叉树的遍历报告

　 数据结构

　课内实验报告书

　一、实验题目： 二叉树的创建与遍历

　二、实验目的：

　通过本次实验， 熟练掌握二叉树的存储结构定义及其遍历算法的实现， 学会

　利用栈编写非递归的遍历算法。

　三、实验要求 ：

　建立一棵用二叉链表方式存储的二叉树， 并对其进行遍历 （先序、 中序和后

　序），打印输出遍历结果。

　要求：从键盘接受扩展先序序列，以二叉链表作为存储结构，建立二叉树，

　并将遍历结果打印输出。采用递归和非递归两种方法实现。

　四、设计与 实现过程

　（1）存储结构定义

　typedef char elemtype;

　typedef struct Node {

　elemtype data;

　struct Node *lchild;

　struct Node *rchild;

　}BitNode;

　（2）算法描述

　Node * creat(Node *pre) {

　char e; Node *head;

　e = getchar();

　if (e != ' '){

　head = (Node *) malloc (sizeof(Node));head->data = e;

　head->Lchild = creat(head);

　if (head->Lchild == NULL){

　head->Lflag = 1; head->Lchild = pre;

　}

　head->Rchild = creat(head);

　if (pre != NULL && pre->Rchild == NULL) {

　pre->Rflag = 1;

　 pre->Rchild = head;}

　return head; } else{

　return NULL;

　 }}

　Node *InPre(Node *root) {

　Node *p;

　if (root->Lflag == 1){

　p = root->Lchild; } else{

　for (p=root->Lchild; p->Rflag==0; p=p->Rchild);

　}

　 return p;}

　Node *InNext(Node *root) {

　Node *p;

　if (root->Rflag == 1){

　p = root->Rchild; } else{

　for (p=root->Rchild; p->Lflag==0; p=p->Lchild); }

　 return p;}

　Node *Infirst(Node *root) {

　Node *p;

　p = root;

　if (!p){

　fprintf(stdout, " n");return NULL;

　}

　while (p->Lflag == 0){

　p = p->Lchild; }

　 return p;}

　void TInOrder(Node *root) {

　Node *p;

　p = Infirst(root);

　while (p != NULL){

　fprintf(stdout, "%c", p->data);p = InNext(p);

　}

　 printf("\n");}

　五、运行结果

　输入 AB E CD输出 BEADC

　六、技巧与体会

　通过实验，锻炼了自己的能力，加深了自己对有关知识的理解。以后要加强

　动手时间能力、多与同学交流算法精髓！在编写程序中尽量做到独立完成、对

　于自己想要完成的问题要主动编程完成、这样自己是一个很大的提升、也能学

　到很多的知识、熟练编程！