实验六二叉树实验报告

实验四 二叉树的操作 班级：计算机1002 班 姓名：唐自鸿 学号：201003010207 完成日期：2010.6.14 题目：对于给定的一二叉树，实现各种约定的遍历。 一、实验目的： （1）掌握二叉树的定义和存储表示，学会建立一棵特定二叉树的方法； （2）掌握二叉树的遍历算法（先序、中序、后序遍历算法）的思想，并学会遍历算法的递归实现和非递归实现。 二、实验内容：构造二叉树，再实现二叉树的先序、中序、后序遍历，最后统计二叉树的深度。 三、实验步骤： (一) 需求分析 1. 二叉树的建立首先要建立一个二叉链表的结构体，包含根节点和左右子树。因为树的每一个左右子树又是一颗二叉树，所以用递归的方法来建立其左右子树。二叉树的遍历是一种把二叉树的每一个节点访问并输出的过程，遍历时根结点与左右孩子的输出顺序构成了不同的遍历方法，这个过程需要按照不同的遍历的方法，先输出根结点还是先输出左右孩子，可以用选择语句来实现。 2．程序的执行命令为： 1）构造结点类型，然后创建二叉树。 2）根据提示，从键盘输入各个结点。 3）通过选择一种方式（先序、中序或者后序）遍历。 4）输出结果，结束。 (二)概要设计 1.二叉树的二叉链表结点存储类型定义 typedef struct Node { DataType data; struct Node *LChild; struct Node *RChild; }BitNode,*BitTree; 2.建立如下图所示二叉树：v oid CreatBiTree(BitTree *bt)用扩 展 先序遍历序列 创建二叉树，如果是当 前 树根置 为空 ，否 则 申 请 一个新 节点。 3.本 程序包含四个模 块 1) 主程序模块： 2)先序遍历模块 3)中序遍历模块 4)后序遍历模块 4.模块调用关系： 主程序模块 （三）详细设计 1 .建立二叉树存储类型 //==========构造二叉树======= void CreatBiTree(BitTree *bt)//用扩展先序遍历序列创建二叉树，如果是当前树根置为空，否则申请一个新节点// { char ch; ch=getchar(); if(ch=='.')*bt=NULL; else { *bt=(BitTree)malloc(sizeof(BitNode));//申请一段关于该节点类型的存储空间 (*bt)->data=ch; //生成根结点 CreatBiTree(&((*bt)->LChild)); //构造左子树 CreatBiTree(&((*bt)->RChild)); //构造右子树 } } 2 . 编程实现以上二叉树的前序、中序和后序遍历操作，输出遍历序列 1 ）先序遍历二叉树的递归算法如下： void PreOrder(BitTree root) { if (root!=NULL) { Visit(roo...