《树结构的定义和基本操作.ppt

第6章 树 6.1　树结构的定义和基本操作 6.2　二叉树 6.3　遍历二叉树 6.4　树和森林 6.5　树的应用 习题 前面谈的基本上是线性表结构，线性表,栈、队列、串、一维数组，即使二维数组(矩阵结构、十字类别)也不过只是线性表的组合，即：除首元素和尾元素以外，每一个元素有唯一的前驱和后续元素。 树形结构是一种重要的非线性结构，讨论的是层次和分支关系，即：除了有一个根元素没有前驱以外，每一个元素都有唯一的前驱元素；另外，每一个元素有零个或多个后继元素。例如，人类社会的族谱和各种社会组织机构都可以用树来形象表示。树在计算机领域中也得到广泛应用。 6.1 树结构的定义和基本操作 6.1.1 树的定义 递归定义： 树(tree)是n(n0)个结点的有限集。在任意一棵树中： (1)有且只有一个特定的称为根(root)的结点。 (2)当n1时，其余结点可分为m(m0)个互不相交的有限集T1，T2，…，Tm，其中每一个集合本身又是一棵树，称为子树(subtree)。 图6.1所示，在图中的树有13个结点，A是树根，其余结点构成三个互不相交的子集：T1={B，E，F，K，L}，T2={C，G}，T3={D，H，I，J，M}；T1，T2和T3都是根A的子树，且它们本身也是一棵树。如在T1中，B是该子树根，其余结点又构成两个互不相交子集，T11={E，K，L}和T12={F}，T11和T12都是根B的子树，且它们本身也是一棵树。 6.1.2 树的常用术语 结点：是包含一个数据元素和若干指向其子树的分支 (即关系). 结点的度：结点拥有的子树数。 叶子：度为0的结点。 分支结点：度不为0的结点。 树的度：树内各结点的度的最大值，图6.1所示树是 一 个3叉树. 孩子结点(child)：结点的后继，结点子树的根结点。 双亲结点(parent)：孩子结点的前驱。s是f的孩子,则f是s的双亲. 兄弟结点(sibling)：同一个双亲的孩子之间互称为兄弟。 祖先结点：从根到该结点的所经过分支上的所有结点, 图6.1树中L结点的祖先结点是A，B，F。 子孙结点：以某结点为根的子树中任一结点都称为该结点 的子孙. 图6.1树中D的子孙结点为H，I，J，M. 结点的层次：根是第1层，依次为第2层…。 树的深度：树中结点的最大层次，图6.1所示的树深度为4. 有序树：树中结点的各子树看成从左至右是有次序的,例 如, 人类社会的族谱就是一个有序树。 无序树：树中结点的各子树没有次序的，孩子结点的顺 序可以调整。 森林：m(m≥0)棵互不相交的树的集合。森林和树之 间的联系是：一棵树取掉根，其子树构成一个 森林；同样，一个森林增加一个根结点成为树. 6.1.3 树的基本操作 (1)initiate(T)：T树的初始化，包括建树。 (2)root(T)：求T树的根。 (3)parent(T,x)：求T树中x结点的双亲结点。 (4)child(T,x,i)：求T树中x结点的第i个孩子结点。 (5)right_sibling(T,x)：求T树中x结点的右兄弟。 (6)Insert_child(y,i,x)：将根为x的子树置为y结点的第i个孩子 (7)del_child(x,i)：删除x结点的第i个孩子(整个子树)。 (8)traverse(T)：遍历T树。按某个次序依次访问树中每一个结点，并使每个结点都被访问且只被访问一次。 (9)clear(T)??置空T树。 以上操作的具体实现，依赖于采用的存储结构。 6.2 二叉树 6.2.1 定义及其操作 二叉树是另一种树形结构，它的特点是每一个结点