信息学奥赛之 数据结构――树 1 树及其应用 树的定义 树是由 n (n >= 0)个结点组成的有限集合。如果 n = 0，称为空树；如果 n > 0，则 （1）有一个特定的称之为根(root)的结点，它只有直接后继，但没有直接前驱； （2）除根以外的其它结点划分为 m (m >=0)个互不相交的有限集合 T0, T1, …, Tm-1，每个集合又是一棵树，并且称之为根的子树(subTree)。每棵子树的根结点有且仅有一个直接前驱，但可以有 0个或多个直接后继。 结点(node):各元素及其子树的分支 结点的度(degree)：子树的数目 分支(branch)结点：度不为 0的结点 叶(leaf)结点：度为 0的结点 子女(child)、双亲(parent)结点：如 B、C、D为 A的子女，A是 B、C、D的双亲 兄弟(sibling)、祖先(ancestor)、子孙(descendant)结点：EF为兄弟，L的祖先是 EBA， 结点所处层次(level) 树的高度(depth)：树的最大层次数 树的度(degree)：各结点度的最大值 二叉树 (Binary Tree) 一棵二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。 二叉树的五种不同形态 二叉树的性质 性质 1 若二叉树的层次从 0开始, 则在二叉树的第 i 层最多有 2i 个结点。(i>= 0) 信息学奥赛之 数据结构――树 2 性质 2 高度为 k的二叉树最多有 2k+1-1个结点。(k ＞＝1) 性质 3 对任何一棵二叉树, 如果其叶结点个数为 n0, 度为 2的非叶结点个数为 n2, 则有 n0＝n2＋1 两种特殊的二叉树：满二叉树(Full Binary Tree) 完全二叉树(Complete Binary Tree) 二叉树是一个有根树，并且每个结点最多有 2 个子结点。 满二叉树是每个结点都有 0个或 2个子结点的树。 一棵有 n 个结点的二叉树，按满二叉树的编号方式对它进行编号，若树中所有结点和满二叉树 1 ～n 编号完全一致，则称该树为完全二叉树。 二叉树的抽象数据表示 1．数组表示 问题：右图所示为一棵单支二叉树 请用数组表示其存储结构 信息学奥赛之 数据结构――树 3 链表表示 对上述的二叉链表，采用以下表示形式： （1）静态链式表示（用数组模拟链表），如右图。 该二叉树的生成完成采用给数组赋值的方法 （2）动态链式结构的 Pascal描述 type tree=^struct struct=record data:treetype; ltree,rtree:tree; end; 该二叉树的生成，可按照根、左子树、右子树的顺...
