pascal-树.doc

树及其应用 树的定义 树是由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 高度为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）静态链式表示（用数组模拟链表），如右图。 该二叉树的生成完成采用给数组赋值的方法 （2）动态链式结构的Pascal描述 type tree=^struct struct=record data:treetype; ltree,rtree:tree; end; 该二叉树的生成，可按照根、左子树、右子树的顺序进行，对应的输入顺序是ABC..DE..FG...,其中点号表示nil。将其定义成一个过程Enter(var P:tree),P为指向根结点的指针变量。具体编码如右： 二叉树遍历(Binary Tree Traversal) 所谓树的遍历，就是按某种次序访问树中的结点，要求每个结点访问一次且仅访问一次。其目标是通过完整而有规则的遍历方法，使得对非线性的二叉树结构能获得其中各结点信息的一个线性排列。 现设访问根结点记作 V 、访问根的左子树记作 L 、访问根的右子树记作 R 则可能的遍历次序有6种： 前序:VLR/VRL 中序:LVR/RVL 后序:LRV/RLV 中根遍历 (Inorder Traversal) 中根遍历二叉树的算法框架是： 若二叉树为空，则空操作； 否则中根遍历左子树 (L)； 访问根结点 (V)； 中根遍历右子树 (R)。 右图所示树的中根 遍历结果： a + b * c - d - e / f 前序遍历 (Preorder Traversal) 前根遍历二叉树的算法框架是 若二叉树为空，则空操作； 否则 访问根结点 (V)； 前根遍历左子树 (L)； 前根遍历右子树 (R)。 遍历结果： + a * b - c d / e f 后根遍历 (Postorder Traversal) 后根遍历二叉树的递归算法框架是 若二叉树为空，则空操作； 否则 后根遍历左子树 (L)； 后根遍历右子树 (R)； 访问根结点 (V)。 遍历结果：a b c d - * + e f / - 二叉树的应用――二叉排序树 二叉排序树又称二叉查找树，它必须符合下列条件： 若存在左子树，则左子树中所有结点的值均小于根结点的值； 右存在右子树，则右子树中所有结点的值均大于根结点的值； 左右子树也是二叉排序树。 这是一种动态树表。这种树通常不是一次生成的，而是在查找过程中，若给定的关键值在树中不存在时再进行插入。插入的原则是：