# 1. 问题描述
通过实验达到:
- 加深对二叉树的概念、基本运算的理解;
- 熟练掌握二叉树的逻辑结构与物理结构的关系;
- 以二叉链表作为物理结构,熟练掌握二叉树基本运算的实现。
## 1.1 具体问题
依据最小完备性和常用性相结合的原则,以函数形式定义了二叉树的创建二叉树、销毁二叉树、清空二叉树、判定空二叉树和求二叉树深度等 14 种基本运算。具体运算功能定义和说明如下。
(1) 创建二叉树:函数名称是CreateBiTree(T,definition);初始条件是definition 给出二叉树T的定义,如带空子树的二叉树前序遍历序列、或前序+中序、或后序+中序;操作结果是按definition构造二叉树T。
(2) 注:①要求T中各结点关键字具有唯一性。后面各操作的实现,也都要满足一棵二叉树中关键字的唯一性,不再赘述;②CreateBiTree中根据definition生成T,不应在CreateBiTree中输入二叉树的定义。
(3) 销毁二叉树:函数名称是DestroyBiTree(T);初始条件是二叉树T已存在;操作结果是销毁二叉树T。
(4) 清空二叉树:函数名称是ClearBiTree (T);初始条件是二叉树T存在;操作结果是将二叉树T清空。
(5) 判定空二叉树:函数名称是BiTreeEmpty(T);初始条件是二叉树T存在;操作结果是若T为空二叉树则返回TRUE,否则返回FALSE。
(6) 求二叉树深度:函数名称是BiTreeDepth(T);初始条件是二叉树T存在;操作结果是返回T的深度。
(7) 查找结点:函数名称是LocateNode(T,e);初始条件是二叉树T已存在,e是和T中结点关键字类型相同的给定值;操作结果是返回查找到的结点指针,如无关键字为e的结点,返回NULL。
(8) 结点赋值:函数名称是Assign(T,e,value);初始条件是二叉树T已存在,e是和T中结点关键字类型相同的给定值;操作结果是关键字为e的结点赋值为value。
(9) 获得兄弟结点:函数名称是GetSibling(T,e);初始条件是二叉树T存在,e是和T中结点关键字类型相同的给定值;操作结果是返回关键字为e的结点的(左或右)兄弟结点指针。若关键字为e的结点无兄弟,则返回NULL。
(10) 插入结点:函数名称是InsertNode(T,e,LR,c);初始条件是二叉树T存在,e是和T中结点关键字类型相同的给定值,LR为0或1,c是待插入结点;操作结果是根据LR为0或者1,插入结点c到T中,作为关键字为e的结点的左或右孩子结点,结点e的原有左子树或右子树则为结点c的右子树。
(11) 删除结点:函数名称是DeleteNode(T,e);初始条件是二叉树T存在,e是和T中结点关键字类型相同的给定值。操作结果是删除T中关键字为e的结点;同时,如果关键字为e的结点度为0,删除即可;如关键字为e的结点度为1,用关键字为e的结点孩子代替被删除的e位置;如关键字为e的结点度为2,用e的左孩子代替被删除的e位置,e的右子树作为e的左子树中最右结点的右子树。
(12) 前序遍历:函数名称是PreOrderTraverse(T,Visit());初始条件是二叉树T存在,Visit是一个函数指针的形参(可使用该函数对结点操作);操作结果:先序遍历,对每个结点调用函数Visit一次且一次,一旦调用失败,则操作失败。
(13) 中序遍历:函数名称是InOrderTraverse(T,Visit));初始条件是二叉树T存在,Visit是一个函数指针的形参(可使用该函数对结点操作);操作结果是中序遍历t,对每个结点调用函数Visit一次且一次,一旦调用失败,则操作失败。
(14) 后序遍历:函数名称是PostOrderTraverse(T,Visit));初始条件是二叉树T存在,Visit是一个函数指针的形参(可使用该函数对结点操作);操作结果是后序遍历t,对每个结点调用函数Visit一次且一次,一旦调用失败,则操作失败。
(15) 按层遍历:函数名称是LevelOrderTraverse(T,Visit));初始条件是二叉树T存在,Visit是对结点操作的应用函数;操作结果是层序遍历t,对每个结点调用函数Visit一次且一次,一旦调用失败,则操作失败。
(16) 实现二叉树的文件形式保存:函数名称是SaveTree(T,path)和LoadTree(T,path);初始条件是二叉树存在,操作结果是实现二叉树的文件形式保存。
# 2. 系统设计
## 2.1 总体设计
- 使用一个大的 while 语句实现整体功能;
- 使用 switch 语句实现菜单栏的操作选择;
- 在每个 case 语句先进行对二叉树是否存在的判断;
## 2.2 算法设计
(1)CreateBiTree(TNode* T, char* definition);
设计思路:按带空节点的前序遍历顺序输入每个key的值(输入包括叶节点的两个空子树),存在字符串中。用一个全局变量改变字符串指针的移动,用递归的思想按照前序创建二叉树的结点。
(2)DestroyBiTree(TNode* T);
设计思路:使用递归释放每一个结点,最后将全局变量isNull(判定表是否存在)改为TRUE值;
(3)ClearBiTree(TNode& T);
设计思路:使用递归释放每一个结点,最后将根节点指针T的key值设置为“#”;
(4)BiTreeEmpty(TNode T);
设计思路:判断根节点T的key值是否为“#”,是则返回true,否则返回false;
(5)BiTreeDepth(TNode T);
设计思路:创建两个计数变量L和R,递归遍历二叉树的左右子树,返回值为L和R中较大的一个并加一的值;
(6)LocateNode(TNode T, KeyType e);
设计思路:设置全局变量Findnode默认为空结点,递归遍历二叉树,当找到对应结点时令Findnode等于该结点。函数返回值为Findnode;
(7)Assign(TNode* T, KeyType e, TElemType value);
设计思路:调用LocateNode函数查找对应结点,如果找到结点则给该结点的value赋值,否则返回ERROR;
(8)GetSibling(TNode T, KeyType e);
设计思路:递归遍历二叉树,如果找到一结点的左孩子是查找的结点,且其右孩子存在,则返回其右孩子,另一方向同理;反之返回ERROR;
(9)InsertNode(TNode* T, KeyType e, int LR, TNode c);
设计思路:新建一个结点,为它初始化赋值;调用LocateNode函数查找插入位置的结点;若找到,则判断LR的值分类情况完成插入;插入成功返回OK,否则返回ERROR;
(10)DeleteNode(TNode* T, KeyType e);
设计思路:新建一个结点delnode代表被删除结点;先调用LocateNode函数查找需要被删除的结点,如果找到该结点则进行是否为根节点的分类讨论;调用查找父节点的函数GetParent找到delnode的父节点,根据结点度数为0,1,2再进行分类讨论进行删除;删除成功返回OK,否则返回ERROR;
(11)PreOrderTraverse(TNode T);
设计思路:按照根-左子树-右子树的顺序进行递归遍历;
(12)InOrderTraverse(TNode T);
设计思路:用栈实现的非递归中序遍历。先让指针遍历到最左结点,push经过的结点到栈中,在指针指向空的时候pop并将弹出的结点赋给当前指针位置,遍历右子树,直到整棵树遍历完成且栈内无元素,返回OK;
(13)PostOrderTraverse(TNode T);
设计思路:按照左子树-右子树-根的顺序进行递归遍历。
(14)LevelOrderTraverse(TNode T);
设计思路:利用队列完成二叉树的按层遍历。首先将二叉树的根节点push到队列中,判断队列不为NULL,就输出队头的元素,判断节点如果有孩子,就将孩子push到队列中,遍历过的节点出队列,循环以上操作,直到遍历完成,返回OK。
(15) Sav
- 1
- 2
- 3
前往页