发布时间 : 星期五 文章实验三 二叉树的基本运算更新完毕开始阅读4713edd0195f312b3169a510
计科092 200900814212 刘亚红
实验三 二叉树的基本运算
一、实验内容
[问题描述]
建立一棵二叉树，试编程实现二叉树的如下基本操作： 1. 按先序序列构造一棵二叉链表表示的二叉树T；
2. 对这棵二叉树进行遍历：先序、中序、后序以及层次遍历，分别输出结点的遍历序列；
3. 求二叉树的深度/结点数目/叶结点数目；(选做) 4. 将二叉树每个结点的左右子树交换位置。（选做）
[基本要求]
从键盘接受输入（先序），以二叉链表作为存储结构，建立二叉树（以先序来建立），
二、概要设计
算法设计：
要实现二叉树的基本操作，先建立一个二叉树，用先序建立二叉树，采用递归创建二叉树；对二叉树进行遍历操作的时候，先序、中序和后序遍历的算法递归时，只有执行的语句顺序有所变化；层次遍历的时候，要用队列的性质，先进先出，建立一位数组，定义两个指针，指向队首和队尾，然后开始遍历，若树不为空时，让树根先进队列，利用递归遍历该结点的左子树，左子树不为空则进队列，然后遍历右子树，若右子树不为空，也进队列；求深度，则是遍历该树的左子树和右子树，比较哪个结点多，则加一，就是该树的深度；在求结点的个数的时候，则遍历树的时候，定义一个count，遍历一个结点则count加一，直到结束；求叶结点个数和结点总数只有一个条件上的差别，就是该结点没有左孩子和右孩子，则count加一；要进行左右子树的交换，首先要确定该循环的结束条件，该结点的左右孩子不能同时为空，在这个前提下，定义一个指针，然后利用参数的传递，交换左右孩子，当然，要采用递归，遍历该结点的左孩子和右孩子，否则只有根节点的左右孩子交换，而其他结点的孩子没有交换。
流程图：
1
计科092 200900814212 刘亚红
开始 建立一个二叉树
用递归算法计算二叉树的叶结用递归算法对二叉树进行先序中序后序和层次遍历
点，总结点、树的深度 用递归算法交换左右孩子 结束 算法：
主函数main() CreateBiTree(BiTree &T) hoorderT) inorderT) preordee T) Levelorder(BiTree T) CountLeaf(BiTree T,int &countCountNode(BiTree T,int &node) depth(T) ChangeiTree &T) (BiTree (BiTree r(BiTreBiTree child(B 模块：
在分析了实验要求和进行了算法分析之后，可以将程序分成九个功能函
2
计科092 200900814212 刘亚红
数，分别如下:
首先定义一个二叉树的结构： typedef struct BiTNode{ char data;
struct BiTNode *lchild,*rchild;//左右孩子指针 }BiTNode,*BiTree;
CreateBiTree(BiTree &T)：按先序次序输入二叉树中的结点的值，#字
符表示空树，构造二叉链表表示的二叉树T：每一个空孩子用#输入： 开始 按先序输入字符 输入字符是 否为空 是 否 按先序建立二叉树，采根结点为空 用递归算法 返回1 结束 preorder(BiTree T)：先序遍历， 开始 按照根左右孩子的顺序，输出二叉树
根结点是否 为空 是
否
先输出根结点，再递归
调用自身依次输出左孩
子和右孩子
结束 3
计科092 200900814212 刘亚红
inorder(BiTree T)：中序遍历， 开始 按照左根右孩子的顺序，输出二叉树
根结点是否 为空 是
否
递归调用自身输出左孩
子，再输出根结点，递 归调用输出右孩子
结束
hoorder(BiTree T)：后序遍历， 开始 按照左右孩子根的顺序，输出二叉树
根结点是否 为空 是
否
递归调用自身输出左孩
子和右孩子，再输出根 结点
结束 Levelorder(BiTree T)：层次遍历，按照每层上的结点输出二叉树
4