第 1 页 共 7 页 宁波工程学院电信学院计算机教研室 实验报告 一、实验目的 1、熟悉二叉树树的基本操作。 2、掌握二叉树的实现以及实际应用。 3、加深二叉树的理解，逐步培养解决实际问题的编程能力。 二、实验环境 1 台 WINDOWS 环境的 PC 机，装有 Visu al C++ 6.0。 三、实验内容 【问题描述】 现需要编写一套二叉树的操作函数，以便用户能够方便的利用这些函数来实现自己的应用。其中操作函数包括： 1> 创建二叉树 CreateBTNode(*b,*str)：根据二叉树括号表示法的字符串*str 生成对应的链式存储结构。 2> 输出二叉树 DispBTNode(*b)：以括号表示法输出一棵二叉树。 3> 查找结点 FindNode(*b,x )：在二叉树 b 中寻找 data 域值为 x 的结点,并返回指向该结点的指针。 4> 求高度 BTNodeDepth(*b)：求二叉树 b 的高度。若二叉树为空,则其高度为 0；否则,其高度等于左子树与右子树中的最大高度加 l。 5> 求二叉树的结点个数 NodesCou nt(BTNode *b) 6> 先序遍历的递归算法：v oid PreOrder(BTNode *b) 7> 中序遍历的递归算法：v oid InOrder(BTNode *b) 8> 后序遍历递归算法：v oid PostOrder(BTNode *b) 9> 层次遍历算法 v oid Lev elOrder(BTNode *b) 【基本要求】 实现以上 9 个函数。 主函数中实现以下功能： 创建下图中的树 b 输出二叉树 b 找到’H’节点，输出其左右孩子值 输出 b 的高度 输出 b 的节点个数 第 2 页 共 7 页 输出b 的四种遍历顺序 上图转化为二叉树括号表示法为A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I))) 程序: #include #include #define MaxSize 100 typedef char ElemType; typedef struct node { ElemType data; /*数据元素*/ struct node *lchild; /*指向左孩子*/ struct node *rchild; /*指向右孩子*/ } BTNode; void CreateBTNode(BTNode *&b,char *str);//创建 BTNode *FindNode(BTNode *b,ElemType x);//查找节点 int BTNodeHeight(BTNode *b);//求高度 void DispBTNode(BTNode *b);//输出 int NodesCount(BTNode *b);//二叉树的结点个数 void PreOrder(BTNode *b);//先序遍历递归 void InOrder(BTNode *b);//中序遍历递归 void PostOrder(BTNode *b);//后序遍历递归 A B D C E H J K L M N F G I 第 3 页 共 ...
VIP
