《数据结构实验二 树的二叉链表表示及其遍历》由会员分享,可在线阅读,更多相关《数据结构实验二 树的二叉链表表示及其遍历(6页珍藏版)》请在金锄头文库上搜索。
1、任课教师:数据结构与算法(2012-2013 学年第 2 学期)实验报告学号:姓名: 班级: 实验 2 树的二叉链表表示及其遍历一、 实验目的: 掌握二叉树的链式存储结构及其遍历二、 实验重点:二叉树的链式存储实现方法三、 实验内容:用二叉链表存储结构表示下图所示二叉树的,并用递归方法输出三种遍历结果。实验提示:1、二叉树的链式存储结构表示typedef struct BiTNodeTElemType data;struct BitNode *lchild,*rchild;BiTNode,*BiTree;2、二叉树的链式存储算法实现CreateBiTree(InsertChild(T,p,LR
2、,c);3、二叉树的递归法遍历PreOrderTraverse(T,Visit();InOrderTraverse(T,Visit();PostOrderTraverse(T,Visit();4、示例源程序#include #define ERROR 0;#define OK 1;typedef int ElemType;typedef struct BinaryTreeElemType data;struct BinaryTree *l;struct BinaryTree *r;*BiTree,BiNode;BiNode * new()return( (BiNode *)malloc(siz
3、eof(BiNode) );int CreateSubTree(BiTree *T,ElemType *all,int i)if (alli=0)|i16)*T=NULL;return OK;*T=new();if(*T=NULL) return ERROR;(*T)-data=alli;CreateSubTree(CreateSubTree(int CreateBiTree(BiTree *T)ElemType all16=0,1,2,3,0,0,4,5,0,0,0,0,6,0,0,0,;CreateSubTree(T,all,1);void printelem(ElemType d)pri
4、ntf(%dn,d);int PreOrderTraverse(BiTree T,int (*Visit)(ElemType d)if(T)if(Visit(T-data)if(PreOrderTraverse(T-l,Visit)if(PreOrderTraverse(T-r,Visit) return OK;return ERROR; else return OK;int main()BiTree root;CreateBiTree(PreOrderTraverse(root,printelem);5、程序源码:#include using namespace std;#define ER
5、ROR 0;#define OK 1;typedef struct BinaryTreeint data;struct BinaryTree *l;struct BinaryTree *r;*BiTree,BiNode;BiNode * new1()return( (BiNode *)malloc(sizeof(BiNode) );int CreateSubTree(BiTree *T,int *all,int i)if (alli=0)|i16)*T=NULL;return OK;*T=new1();if(*T=NULL) return ERROR;(*T)-data=alli;Create
6、SubTree(CreateSubTree(return 0;int CreateBiTree(BiTree *T)int all16=0,1,2,3,0,0,4,5,0,0,0,0,6,0,0,0,;CreateSubTree(T,all,1);return 0;int printelem(int d)printf(%d ,d);return OK;/先序遍历int PreOrderTraverse(BiTree T,int (*Visit)(int d)if(T)if(Visit(T-data)if(PreOrderTraverse(T-l,Visit)if(PreOrderTravers
7、e(T-r,Visit) return OK;return ERROR; else return OK;/中序遍历int InOrderTraverse(BiTree T,int (*Visit)(int d)if(T)if(InOrderTraverse(T-l,Visit) if(Visit(T-data)if(InOrderTraverse(T-r,Visit) return OK;return ERROR; else return OK;/后序遍历int PostOrderTraverse(BiTree T,int (*Visit)(int d)if(T)if(PostOrderTraverse(T-l,Visit)if(PostOrderTraverse(T-r,Visit)if(Visit(T-data) return OK;return ERROR; else return OK;int main()BiTree root;CreateBiTree(coutn;return 0;六、运行结果与测试分析:七、实验心得与体会: