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

1、数据结构实验报告实验五学院软件学院 班级13级.NET班 学号 132862 4 0 0 4 姓名刘 振 龙二叉树的存储与遍历实现实验报告学号1328624004姓名刘振龙时间2014.10.10专业计算机科学与技术班级.Net实验题目：二叉树的存储与遍历的实现一、实验目的：1 .了解二叉树的存储与遍历 的运算算法的实现；2 .分析算法的空间复杂度和插入和删除及遍历的时间复杂度；3 .总结二叉树顺序存储与遍历的特点。4 .了解二叉树的基本操作在顺序存储上的实现和遍历上的实现；5 .以二叉树的各种操作(建立、插入、删除和遍历等)；6 .掌握二叉树顺序存储结构的定义和基本操作的实现； 二、实验分析

2、：(1).二叉树的顺序存储的实现。O建立一个二叉树(先中后都可)，在演示过程中必须按ENTE瞰，方可看到运行结果。 (1)本实验建立 一个中序二叉树；(2)进行二叉树的遍历。二.概要设计1 .二叉树的存储：ADT Tree 数据对象D: D是具有相同特性的数据元素的集合。数据关系R若D为空集，则称为空树；若D中仅含一个数据元素，则关系R为空集；否则R=H , H是如下二元关系：(1) 在D中存在唯一的称为根的数据元素root ,它在关系H下无前驱；(2) 若 D-root ?？，则存在D-root 的一个划分 D,D2,D3,Dm(m>0),即对于任意的 j ?k(1Wj,k Wm)有

3、DAR=?, 且对任意的i=1,2,m。惟一存在数据元素Xi6D,有<。« i> H3)对应于D-root的以上划分，H-<root,x i> ,<root,x 2>,<root,x m> 有惟一的一个划分 Hi,H2,H,Hm(m>0),即对于任意的j ?k(1Wj,k Wm)有HH=,且对 任意的i(1 wi Wm),Hi是D上的二元关系，(Di, H)是一棵符合本 定义的树，称为根 root 的子树。InitBiTree(&T);DestroyBiTree(&T); BiTreeEmpty(T);Create

4、BiTree(&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();P

5、ostOrderTraverse(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 Pre

6、OrderTraverse (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 (! StackEmpt

7、y(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/ PreOrderTraversevoid InOrderTraverse (BiTree T,void( *visit)(TElemType e) /中序遍历二叉树if (T)InOrderTraverse(T->lchild, visit); /中序遍历左子树visit(T->data); /访

8、问根结点1:InOrderTraverse(T->rchild, visit);/中序遍历右子树/ 2: InOrderTraversevoid 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); /左孩子进队

9、列if(P->rchild) EnQueue(Q, P->rchild); /右孩子进队列/ while/ if/ LevelOrderTraverse三实验步骤(包括主要步骤、代码分析等)#include<stdio.h>#include<stdary.h>#define MAXSIZE 100*lchild,typedef struct BiTNode char data; struct BiTNode*rchild; BiTNode,*BiTree;BiTree CreateBiTree() BiTree T;char ch=getchar(); if

10、(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(

11、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

12、(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

13、");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()；邺八炉4a的人数3;8

14、展次籍"个权值(整型)：6 4 3 7 e 11 9遍遍遍 :先程 样归归归出 It.诗通递退进以的示梃 更表X 埼一二艮林以三个空档后回军结束口2 3 4 5 6 向车，EC DE G F二立二叉树已经完毕！请输入遍历的F ：'iff：.递归先生遍历.递归中南遍历归中序褊历二叉树:C B E G D F fl归先序遍历二又树二。B C D E G F的编码为沏1团超停您的烹鸳.树I为6的字符的编明为物二屋为4的字符的编明为:1网工 我的字例的编用为二1小 为V的生处的愈刑为:1师为8的空椅的编叫为力工8：1011T x值为11的字符的编码为二00 便将为9的字符也编有为11 hress anu key to continue四.体验分析：(1)本次实验是完成二叉树的存储和遍历，通过本次实验我学会了如何建立个二叉树的存储及遍历，存储为顺序遍历分为先中后三次遍历， 本次试验中先完 成了建立即存储，儿后依次完成了三次遍历，由于本次试验的使用性比较高因而 学好了(2)本次实验以后在工作中也会有很大的帮助，我学到了很多关于二叉树的相 关技术。(通过本实验我对二叉树的