第6章(实验6-1).ppt

淮海工学院 数据结构课程 实验二 树型数据结构实验 树和二叉树的应用 一、实验题目 熟练掌握树的基本概念、二叉树的基本操作及在链式存储结构上的实现； 重点掌握二叉树的生成、遍历及求深度等算法； 掌握哈夫曼树的含义及其应用； 掌握运用递归方式描述算法及编写递归C程序的方法，提高算法分析和程序设计能力。 要求独立完成实验内容（提交程序清单、相关实验数据及运行结果）； 要求认真书写实验报告,并按时提交。 二、目的与要求 建立一棵用二叉链表方式存储的二叉树，并对其进行遍历（先序、中序和后序），打印输出遍历结果，求二叉树的深度//叶结点数目。 三、实验内容 # includestdio.h # includestdlib.h # includeconio.h # includemalloc.h # define ERROR 0 # define OK 1 typedef struct BiTNode{ char data; struct BiTNode *lchild,*rchild; }BiTNode,*BiTree; 四、编程举例与要点 二叉树存储结构 先序创建二叉树代码段 Bvoid CreateBiTree(BiTree *bt) { char ch; ch = getchar(); if(ch==.) *bt=NULL; else { *bt=(BiTree)malloc(sizeof(BiTNode)); //生成一个新结点 (*bt)-data=ch; CreateBiTree(((*bt)-LChild)); //生成左子树 CreateBiTree(((*bt)-RChild)); //生成右子树 } } 前序递归遍历程序段 void PreOrder(BiTree root) /*先序遍历二叉树, root为指向二叉树(或某一子树)根结点的指针*/ { if (root!=NULL) { Visit(root -data); /*访问根结点*/ PreOrder(root -LChild); /*先序遍历左子树*/ PreOrder(root -RChild); /*先序遍历右子树*/ } } void Visit(char ch) { printf(%c ,ch); } 中序递归遍历程序段 void InOrder(BiTree root) /*中序遍历二叉树, root为指向二叉树(或某一子树)根结点的指针*/ { if (root!=NULL) { InOrder(root -LChild); /*中序遍历左子树*/ Visit(root -data); /*访问根结点*/ InOrder(root -RChild); /*中序遍历右子树*/ } } 后序递归遍历程序段 void PostOrderTraverse(BiTree T){ if(T!=NULL){ PostOrderTraverse(T-lchild); PostOrderTraverse(T-rchild); printf(%c---,T-data); } } 淮海工学院 数据结构课程