二叉树的存储与遍历实现实验报告.doc

数据结构实验报告实验五 学院 软 件 学 院 班级13 级 .NET班 学号132862 4 0 0 4 姓名 刘 振 龙 二叉树的存储与遍历实现实验报告学号1328624004姓名刘振龙时间2014.10.10专业计算机科学与技术班级.Net实验题目：二叉树的存储与遍历的实现一、实验目的： 1.了解二叉树的存储与遍历的运算算法的实现；2.分析算法的空间复杂度和插入和删除及遍历的时间复杂度；3.总结二叉树顺序存储与遍历的特点。4.了解二叉树的基本操作在顺序存储上的实现和遍历上的实现；5.以二叉树的各种操作（建立、插入、删除和遍历等）；6.掌握二叉树顺序存储结构的定义和基本操作的实现；二、实验分析：（1）.二叉树的顺序存储的实现。建立一个二叉树（先中后都可），在演示过程中必须按ENTER键，方可看到运行结果。（1）本实验建立 一个中序二叉树；（2）进行二叉树的遍历。二概要设计1.二叉树的存储：ADT Tree 数据对象D：D是具有相同特性的数据元素的集合。 数据关系R：若 D 为空集，则称为空树； 若 D 中仅含一个数据元素，则关系R为空集；否则 R=H，H是如下二元关系： (1) 在D中存在唯一的称为根的数据元素 root，它在关系H下无前驱； (2) 若D-root，则存在D-root的一个划分D1,D2,D3,Dm(m0) ,即对于任意的j k(1j,km)有DjDk=，且对任意的i=1,2,m。惟一存在数据元素xiDi, 有 H； 3)对应于D-root的以上划分，H- , 有惟一的一个划分H1,H2,H3,Hm(m0) ,即对于任意的j k(1j,km)有HjHk= ，且对任意的i(1im),Hi是Di上的二元关系，（ Di，Hi）是一棵符合本定义的树，称为根root的子树。InitBiTree(&T); DestroyBiTree(&T); BiTreeEmpty(T); CreateBiTree(&T, definition); BiTreeDepth(T); Value(T, e); ClearBiTree(&T); DeleteChild(T, p, LR); Root(T); Assign(T, &e, value); InsertChild(T, p, LR, c); Parent(T, e); LeftChild(T, e); RightChild(T, e);LeftSibling(T, e); RightSibling(T, e);PreOrderTraverse(T, Visit();InOrderTraverse(T, Visit();PostOrderTraverse(T, Visit();LevelOrderTraverse(T, Visit(); typedef struct TriTNode / 结点结构 TElemType data; struct TriTNode *lchild, *rchild; / 左右孩子指针 struct TriTNode *parent; /双亲指针 TriTNode, *TriTree;2. #define MAX_TREE_SIZE 100 / 二叉树的最大结点数typedef TElemType SqBiTreeMAX_TREE_SIZE; / 0号单元存储根结点SqBiTree bt; void PreOrderTraverse (BiTree T, void( *visit)(TElemType e) / 先序遍历二叉树 if (T) visit(T-data); / 访问根结点 PreOrderTraverse(T-lchild, visit); /先序遍历左子树 PreOrderTraverse(T-rchild, visit);/先序遍历右子树 void PreOrderTraverse (BiTree T, void( *visit)(TElemType e) / 先序遍历二叉树的非递归算法 InitStack(S); push(S,T); while (! StackEmpty(S) while(GetTop(S, P)&P) visit(P-data); push(S, P-lchild); pop(S,P); if(! StackEmpty(S) pop(S,P); push(S,P-rchild); /if /while / PreOrderTraverse void InOrderTraverse (BiTree T,void( *visit)(TElemType e) / 中序遍历二叉树 if (T) InOrderTraverse(T-lchild, visit); /中序遍历左子树 visit(T-data); / 访问根结点 1: InOrderTraverse(T-rchild, visit);/中序遍历右子树 / 2:/ InOrderTraverse void LevelOrderTraverse(BiTree T, Status (*viste)(TElemType e) /按层次遍历二叉链表存储的二叉树 if(T) InitQueue(Q);/初始化一个队列 EnQueue(Q,T);/根进队列 while(!QueueEmpty(Q) DelQueue(Q,P); viste(p-data);/访问 if(P-lchild) EnQueue(Q, P-lchild); /左孩子进队列 if(P-rchild) EnQueue(Q, P-rchild); /右孩子进队列 / while / if/ LevelOrderTraverse 三实验步骤（包括主要步骤、代码分析等）#include#include#define MAXSIZE 100 typedef struct BiTNode char data; struct BiTNode *lchild, *rchild; BiTNode,*BiTree; BiTree CreateBiTree() BiTree T; char ch=getchar(); if(ch=#) T=NULL; else T=(BiTNode *)malloc(sizeof(BiTNode); T-data=ch; T-lchild=CreateBiTree(); T-rchild=CreateBiTree(); return T; /递归生成二叉树，用#代表空子树 void preorder(BiTree t) if(t) printf(%c ,t-data); preorder(t-lchild); preorder(t-rchild); /递归先序遍历 void Inorder(BiTree T) if(T) Inorder(T-lchild); printf(%c ,T-data); Inorder(T-rchild); /递归中序遍历 void postorder(BiTree t) if(t) preorder(t-lchild); preorder(t-rchild); printf(%c ,t-data); /递归后序遍历 void NInorder(BiTree T) BiTree stackMAXSIZE; BiTree p=T; int top=-1; while(p|top!=-1) if(p) top+; stacktop=p; p=p-lchild; else p=stacktop; top-; printf(%c ,p-data); p=p-rchild; /非递归中序遍历 main() BiTree T; printf(please input the tree: ); T=CreateBiTree(); printf(n); getch(); printf(the tree after preorder is: );preorder(T); printf(n); getch(); printf(the tree after ineorder is: ); Inorder(T); printf(n); getch(); printf(the tree after postorder is: ); postorder(T) ; printf(n); getch(); printf(the tree after noinorder is: ); NInorder(T) ; printf(n); getch(); 四体验分析：（1）本次实验是完成二叉树的存储和遍历，通过本次实验我学会了如何建立一个二叉树的存储及遍历，存储为顺序遍历分为先中后三次遍历，本次试验中先完成了建立即存储，儿后依次完成了三次遍历，由于本次试验的使用性比较高因而学好了（2）