数据结构实验二 树的二叉链表表示和其遍历.docVIP

任课教师： 《数据结构与算法》 （2012-2013学年第2学期） 实 验 报 告 学号： 姓名： 班级： 实验2 树的二叉链表表示及其遍历 实验目的： 掌握二叉树的链式存储结构及其遍历 实验重点： 二叉树的链式存储实现方法 实验内容： 用二叉链表存储结构表示下图所示二叉树的，并用递归方法输出三种遍历结果。 实验提示: 1、二叉树的链式存储结构表示 typedef struct BiTNode{ TElemType data; struct BitNode *lchild,*rchild; }BiTNode,*BiTree; 2、二叉树的链式存储算法实现 CreateBiTree(T,definition); InsertChild(T,p,LR,c); 3、二叉树的递归法遍历 PreOrderTraverse(T,Visit()); InOrderTraverse(T,Visit()); PostOrderTraverse(T,Visit()); 示例源程序 #include alloc.h #define ERROR 0; #define OK 1; typedef int ElemType; typedef struct BinaryTree { ElemType data; struct BinaryTree *l; struct BinaryTree *r; }*BiTree,BiNode; BiNode * new() { return( (BiNode *)malloc(sizeof(BiNode)) ); } int CreateSubTree(BiTree *T,ElemType *all,int i) { if ((all[i]==0)||i16) { *T=NULL; return OK; } *T=new(); if(*T==NULL) return ERROR; (*T)-data=all[i]; CreateSubTree(((*T)-l),all,2*i); CreateSubTree(((*T)-r),all,2*i+1); } int CreateBiTree(BiTree *T) { ElemType all[16]={0,1,2,3,0,0,4,5,0,0,0,0,6,0,0,0,}; CreateSubTree(T,all,1); } void printelem(ElemType d) { printf(%d\n,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(root); PreOrderTraverse(root,printelem); } 程序源码： #include iostream using namespace std; #define ERROR 0; #define OK 1; typedef struct BinaryTree { int 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 ((all[i]==0)||i16) { *T=NULL; return OK; } *T=new1(); if(*T==NULL) return ERROR; (*T)-data=all[i]; CreateSubTree(((*T)-l),all,2*i); CreateSubTree(((*T)-r),all,2*i+1); return 0; } int CreateBiTree(BiTree *T) { int all[16]={0,1,2,3,0,0,4,5,0,0,0,0,6,0,0,0,}; CreateSu