掌握用指针类型描述、建立、遍历二叉树的运算。.doc

洛阳理工学院实验报告 系部 计算机系 班级 B110505 学号 姓名 李满意 课程名称 数据结构 实验日期 2013.04.24 实验名称 二叉树的建立及遍历 成绩 实验目的： 掌握二叉树的结构特征，掌握用指针类型描述、二叉树的运算。 电脑一台，VC++6.0软件。 实验内容与算法思想： 内容： 建立一棵用二叉链表方式存储的二叉树，并对其进行遍历（先序、中序、后序），打印输出遍历结果。 【基本要求】 从键盘接受输入先序序列，以二叉链表作为存储结构，建立二叉树（以先序来建立）并对其进行遍历（先序、中序、后序），然后将遍历结果打印输出。要求采用递归和非递归两种方法实现。 【测试数据】 ABC～～DE～G ～～F ～～～（其中～表示空格字符） 输出结果：先序序列为ABCDEGF 中序序列为CBEGDFA 后序序列为CGEFDBA 算法思想： 程序中使用递归和非递归两种方法实现对二叉树的先序、中序及后序遍历。递归就是对自身的函数调用，递归遍历中访问根结点、遍历左子树、遍历右子树语句的的顺序决定了是在先序、中序、后序。非递归先序遍历从根结点开始，只要当前结点存在，或者栈不空，则重复操作：①从当前结点开始，访问根结点、出栈，遍历左子树；②退栈，遍历左子树。非递归中序遍历从根结点开始，只要当前结点存在，或者栈不空，则重复操作：①如果当前结点存在，则进栈并遍历左子树；②否则退栈并访问，然后遍历右子树；非递归后序遍历从根结点开始，只要当前结点存在，或者栈不空，则重复操作：①从当前结点开始，进栈并遍历左子树，直到左子树为空；②如果栈顶结点的右子树为空，或者栈顶结点的右孩子为刚访问过的结点，则退栈并访问，然后将当前结点指针置为空；③否则，遍历右子树。 运行结果： 实验总结： 通过这次实验我对二叉树有了更熟练的掌握，更清晰的认识。熟练掌握了二叉树的遍历，并对使用非递归实现对二叉树的遍历，使得我对非递归也更加熟练的掌握，对以往知识起到了复习巩固的作用。另外，感觉自己的编程能力也在不断的进步之中，继续努力，相信自己的数据结构会学的很好，相信自己的编程技能也会提高的，继续努力。 附：源程序： #includestdio.h #includestdlib.h typedef char DataType; #define FALSE 0 #define TRUE 1 typedef struct Node { DataType data; struct Node *Lchild; struct Node *Rchild; }BiTNode,*BiTree; typedef BiTree StackElementType; #define Stack_Size 50 typedef struct { StackElementType elem[Stack_Size]; int top; }SeqStack; void InitStack(SeqStack *S) { S-top=-1; } int IsEmpty(SeqStack *S) { if(S-top==-1)return 1; else return 0; } void GreatBiTree(BiTree *root) { char c; c=getchar(); if(c== ) *root=NULL; else { *root=(BiTNode *)malloc(sizeof(BiTNode)); (*root)-data=c; GreatBiTree((*root)-Lchild); GreatBiTree((*root)-Rchild); } } void PreOrder(BiTree root) /*先序遍历二叉树, root为指向二叉树(或某一子树)根结点的指针*/ { if (root!=NULL) { printf(%c,root-data); /*访问根结点*/ PreOrder(root-Lchild); /*先序遍历左子树*/ PreOrder(root-Rchild); /*先序遍历右子树*/ } } void InOrder(BiTree root) /*中序遍历二叉树, root为指向二叉树(或某一子树)根结点的指针*/ { if (root!=NULL) { InOrder(root -Lchild); /*中序遍历左子树*/ printf(%c,root-data); /*访问根结点*/