从树的定义和图71(a)的示例可以看出,树具有下面两个 特点: (1)树的根结点没有前驱结点,除根结点之外的所有结点 有且只有一个前驱结点。 (2)树中所有结点可以有零个或多个后继结点 由此特点可知,下图所示的都不是树结构。 A ( 2021年1月21日 数据结构讲义
2021年1月21日 数据结构讲义 6 从树的定义和图7.1(a)的示例可以看出，树具有下面两个 特点： ⑴树的根结点没有前驱结点，除根结点之外的所有结点 有且只有一个前驱结点。 ⑵树中所有结点可以有零个或多个后继结点。 由此特点可知，下图所示的都不是树结构
2.相关术语 在二叉树中介绍的有关概念在树中仍然适用。除此之外, 再介绍两个关于树的术语。 (1)有序树和无序树。如果一棵树中结点的各子树丛左到右 是有次序的,即若交换了某结点各子树的相对位置,则构成 不同的树,称这棵树为有序树;反之,则称为无序树 )森林。零棵或有限棵不相交的树的集合称为森林。自然 界中树和森林是不同的概念,但在数据结构中,树和森林只 有很小的差别。任何一棵树,删去根结点就变成了森林。 2021年1月21日 数据结构讲义
2021年1月21日 数据结构讲义 7 2．相关术语 在二叉树中介绍的有关概念在树中仍然适用。除此之外， 再介绍两个关于树的术语。 ⑴有序树和无序树。如果一棵树中结点的各子树丛左到右 是有次序的，即若交换了某结点各子树的相对位置，则构成 不同的树，称这棵树为有序树；反之，则称为无序树。 ⑵森林。零棵或有限棵不相交的树的集合称为森林。自然 界中树和森林是不同的概念，但在数据结构中，树和森林只 有很小的差别。任何一棵树，删去根结点就变成了森林
7.1.2树的表示 树的表示方法有四种,各用于不同的目的。 1.直观表示法 树的直观表示法就是以倒着的分支树的形式表示,下 图就是一棵树的直观表示。其特点就是对树的逻辑结构的描 述非常直观。是数据结构中最常用的树的描述方法 2021年1月21日
2021年1月21日 数据结构讲义 8 7.1.2 树的表示 树的表示方法有四种，各用于不同的目的。 1．直观表示法 树的直观表示法就是以倒着的分支树的形式表示，下 图就是一棵树的直观表示。其特点就是对树的逻辑结构的描 述非常直观。是数据结构中最常用的树的描述方法
2.嵌套集合表示法 所谓嵌套集合是指一些集合的集体,对于其中任何两个 集合,或者不相交,或者一个包含另一个。用嵌套集合的 形式表示树,就是将根结点视为一个大的集合,其若干棵 子树构成这个大集合中若干个互不相交的子集,如此嵌套 下去,即构成一棵树的嵌套集合表示。下图就是一棵树的 嵌套集合表示。 F 2021年1月21日
2021年1月21日 数据结构讲义 9 2．嵌套集合表示法 所谓嵌套集合是指一些集合的集体，对于其中任何两个 集合，或者不相交，或者一个包含另一个。用嵌套集合的 形式表示树，就是将根结点视为一个大的集合，其若干棵 子树构成这个大集合中若干个互不相交的子集，如此嵌套 下去，即构成一棵树的嵌套集合表示。下图就是一棵树的 嵌套集合表示
3.凹入表示法 树的凹入表示法如左图所示。 ABDHI 4.广义表表示法 树用广义表表示,就是将根作为 由子树森林组成的表的名字写在表 的左边,这样依次将树表示出来 (A(BE(HDF),C(GD) 2021年1月21日 数据结构讲义 10
2021年1月21日 数据结构讲义 10 3．凹入表示法 树的凹入表示法如左图所示。 4．广义表表示法 树用广义表表示，就是将根作为 由子树森林组成的表的名字写在表 的左边，这样依次将树表示出来。 (A(B(D,E(H,I),F),C(G)))