南的开大学 数据结构Week9 树与二叉树.pdf

树和二叉树 树型结构是一类非常重要的非线性结构。直观 地，树型结构是以分支关系定义的层次结构。 树在计算机领域中也有着广泛的应用，例如在 编译程序中，用树来表示源程序的语法结构；在数据库 系统中，可用树来组织信息；在分析算法的行为时，可 用树来描述其执行过程等等。 本章将详细讨论树和二叉树数据结构，主要介 绍树和二叉树的概念、术语，二叉树的遍历算法。树和 二叉树的各种存储结构以及建立在各种存储结构上的操 作及应用等。 树的基本概念 树的定义和基本术语 1 树的定义 树(Tree)是n(n≧0)个结点的有限集合T，若n=0 时称为空树，否则： ⑴ 有且只有一个特殊的称为树的根(Root)结点； ⑵ 若n1时，其余的结点被分为m(m0)个互不相交的子集 T , T , T …T ，其中每个子集本身又是一棵树，称其为根的 1 2 3 m 子树(Subtree)。 这是树的递归定义，即用树来定义树，而只有一个 结点的树必定仅由根组成。 2 树的基本术语 ⑴ 结点(node)：一个数据元素及其若干指向其子树的分支。 ⑵ 结点的度(degree) 、树的度：结点所拥有的子树的棵数称 为结点的度。树中结点度的最大值称为树的度。 A的度是3 树的度是3 B的度是2 A K的度是0 B C D A E F G H I J (a) 只有根结点 K L M N 树的示例形式 (b) 一般的树 ⑶ 叶子(leaf)结点、非叶子结点：树中度为0的结点称为叶子 结点(或终端结点)。相对应地，度不为0的结点称为非叶子结 点(或非终端结点或分支结点)。除根结点外，分支结点又称为 内部结点。 结点H、I、J 、K、L、M、N是叶子结点，而所有其它结 点都是分支结点。 ⑷ 孩子结点、双亲结点、兄弟结点 一个结点的子树的根称为该结点的孩子结点(child)或子结点； 相应地，该结点是其孩子结点的双亲结点(parent)或父结点。 结点B 、C、D是结点A 的子结点，而结点A是结点B 、C、D 的父 结点；类似地结点E 、F是结点B 的子结点，结点B是结点E 、F 的父结点。 同一双亲结点的所有子结点互称为兄弟结点。 结点B 、C、D是兄弟结点；结点E 、F是兄弟结点。 ⑸ 层次、堂兄弟结点 规定树中根结点的层次为1，其余结点的层次等于其双亲结 点的层次加1。 若某结点在第l(l ≧1)层，则其子结点在第l+1层。 双亲结点在同一层上的所有结点互称为堂兄弟结点。结点E、 F、G、H、I、J 。 ⑹ 结点的层次路径、祖先、子孙 从根结点开始，到达某结点p所经过的所有结点成为结点p 的 层次路径 (有且只有一条)。 结点p 的层次路径上的所有结点（p除外）称为p 的祖先 (ancester) 。 以某一结点为根的子树中的任意结点称为该结点的子孙结点 (descent) 。 ⑺ 树的深度(depth)：树中结点的最大层次值，又称为树的高 度。 ⑻ 有序树和无序树：对于一棵树，若其中每一个结点的子树 （若