文档介绍：1 题目:假设二叉树采用二叉链表结构。设计并实现如下算法:先序递归建树, 中序非递归遍历该树, 输出各个结点的值, 并求该树中单分支结点的个数。一、需求分析 1. 用户可以根据自己的需求分别输入任意的一个二叉树, 并且能够实现中序非递归遍历该树输出各个结点的数值。 2. 通过已有的二叉树能够求出该树的单分支结点的个数。 3. 程序执行的命令包括: (1 )构造二叉树 T(2 )遍历二叉树(3 )求二叉树单分支结点的个数(4 )求二叉树的总结点数二、概要设计⒈为实现上述算法,需要链表的抽象数据类型: ADT Binarytree { 数据对象: D 是具有相同特性的数据元素的集合数据关系 R: 若D 为空集,则 R 为空集,称 binarytree 为空二叉树; 若D 不为空集,则 R为{H} ,H 是如下二元关系; (1)在D 中存在唯一的称为根的数据元素 root ,它在关系 H 下无前驱; (2)若D- {root} 不为空, 则存在 D- {root} = {D1 , Dr} ,且 D1∩ Dr 为空集; (3)若 D1 不为空,则 D1 中存在唯一的元素 x1, <root , x1> ∈H ,且存在 D1 上的关系 H1是H 的子集;若 Dr 不为空集,则 Dr 中存在唯一的元素 Xr, <root , Xr> ∈H, 且存在Dr 上的关系Hr为H 的子集; H={<root , x1>,<root , Xr>,H1,Hr}; (4) (D1,{H1}) 是一颗符合本定义的二叉树, 称为根的左子树, (Dr,{Hr}) 是一颗符合本定义的二叉树,称为根的右子树。基本操作:C reatbitree(&S , definition) 初始条件: definition 给出二叉树 S 的定义操作结果:按 definition 构造二叉树 S counter(T) 初始条件:二叉树 T 已经存在操作结果:返回二叉树的总的结点数 onecount(T) 初始条件:二叉树 T 已经存在操作结果:返回二叉树单分支的节点数 C learbintree(S) 初始条件:二叉树 S 已经存在操作结果:将二叉树 S 清为空树 B itreeempty(S) 2 初始条件:二叉树 S 已经存在操作结果:若 S 为空二叉树,则返回 TRUE ,否则返回 FALSE B itreedepth(S,&e) 初始条件:二叉树 S 已经存在操作结果:返回 S 的深度 Parent(S) 初始条件:二叉树 S 已经存在, e是S 中的某个结点操作结果:若 e是T 的非根结点,则返回它的双亲,否则返回空 Preordertraverse(S) 初始条件:二叉树 S 已经存在, Visit 是对结点操作的应用函数。操作结果:先序遍历 S ,对每个结点调用函数 visit 一次且仅一次。一旦 visit 失败,则操作失败。 Inordertraverse (S,&e) 初始条件:二叉树 S 已经存在, Visit 是对结点操作的应用函数。操作结果:中序遍历 S ,对每个结点调用函数 visit 一次且仅一次。一旦 visit 失败,则操作失败。 Postordertraverse (&S,e) 初始条件:二叉树 S 已经存在, Visit 是对结点操作的应用函数。操作结果:后序遍历