资源描述：
《二叉树的存储与遍历实现实验报告.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、数据结构实验报告实验五学院软件学院班级13级.NET班学号1328624004姓名刘振龙二叉树的存储与遍历实现实验报告学号1328624004姓名刘振龙时间2014.10.10专业计算机科学与技术班级.Net实验题目：二叉树的存储与遍历的实现一、实验目的：1.了解二叉树的存储与遍历的运算算法的实现；2.分析算法的空间复杂度和插入和删除及遍历的时间复杂度；3.总结二叉树顺序存储与遍历的特点。4.了解二叉树的基本操作在顺序存储上的实现和遍历上的实现；5.以二叉树的各种操作（建立、插入、删除和遍历等）
2、；6.掌握二叉树顺序存储结构的定义和基本操作的实现；二、实验分析：（1）.二叉树的顺序存储的实现。建立一个二叉树（先中后都可），在演示过程中必须按ENTER键，方可看到运行结果。（1）本实验建立一个中序二叉树；（2）进行二叉树的遍历。二．概要设计1.二叉树的存储：ADTTree{数据对象D：D是具有相同特性的数据元素的集合。数据关系R：若D为空集，则称为空树；若D中仅含一个数据元素，则关系R为空集； 否则R={H}，H是如下二元关系：(1)在D中存在唯一的称为根的数据元素root，它在关系H下
3、无前驱；(2)若D-{root}≠⌽，则存在D-{root}的一个划分D1,D2,D3,…,Dm(m>0),即对于任意的j≠k(1≤j,k≤m)有Dj∩Dk=⌽，且对任意的i=1,2,…,m。惟一存在数据元素xi∈Di,有∈H；3)对应于D-{root}的以上划分，H-{,,…,}有惟一的一个划分H1,H2,H3,…,Hm(m>0),即对于任意的j≠k(1≤j,k≤m)有Hj∩Hk=，且对任意的i(1≤i≤m),Hi是Di上
4、的二元关系，（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);R
5、ightChild(T,e);LeftSibling(T,e);RightSibling(T,e);PreOrderTraverse(T,Visit());InOrderTraverse(T,Visit());PostOrderTraverse(T,Visit());LevelOrderTraverse(T,Visit());typedefstructTriTNode{//结点结构TElemTypedata;structTriTNode*lchild,*rchild;//左右孩子指针struct
6、TriTNode*parent;//双亲指针}TriTNode,*TriTree;2.#defineMAX_TREE_SIZE100//二叉树的最大结点数typedefTElemTypeSqBiTree[MAX_TREE_SIZE];//0号单元存储根结点SqBiTreebt;voidPreOrderTraverse(BiTreeT,void(*visit)(TElemTypee)){//先序遍历二叉树if(T){visit(T->data);//访问根结点PreOrderTraverse(T-
7、>lchild,visit);//先序遍历左子树PreOrderTraverse(T->rchild,visit);//先序遍历右子树}}voidPreOrderTraverse(BiTreeT,void(*visit)(TElemTypee)){//先序遍历二叉树的非递归算法InitStack(S);push(S,T);while(!StackEmpty(S)){while(GetTop(S,P)&&P){visit(P->data);push(S,P->lchild);}pop(S,P);i
8、f(!StackEmpty(S)){pop(S,P);push(S,P->rchild);}//if}//while}//PreOrderTraversevoidInOrderTraverse(BiTreeT,void(*visit)(TElemTypee)){//中序遍历二叉树if(T){InOrderTraverse(T->lchild,visit);//中序遍历左子树visit(T->data);//访问根结点1:InOrderTraverse(T->rchild,visit);//中序遍
