树的基本概念

• 1.树的定义和基本术语
• • 1.1. 树的递归定义
  • 1.2. 树的基本术语
  • • 1.2.1. 树的结点
    • 1.2.1. 树的规模
    • 1.2.3. 结点
    • 1.2.4. 兄弟的关系
    • 1.2.5. 兄弟间的关系
• 2. 树的表示
• 3. 树中相关操作

1.树的定义和基本术语

1.1. 树的递归定义

树是根和子树构成的一对多的多层次结构。所以树是一种递归的定义。

1.2. 树的基本术语

1.2.1. 树的结点

包含一个数据元素以及若干指向其子树的的分支。

1.2.1. 树的规模

（1）结点的度：结点拥有的子树数。
（2）树的度：树中结点度的最大值。
（3）结点的层次：根为第一层，根的孩子是第二层，以此类推。
（4）树的深度（高度）：树中结点的人最大层次。
（5）树的宽度：树中各层结点数的最大值。

1.2.3. 结点

（1）根结点：无前驱。
（2）叶子：无后继。
（3）分支结点：一个前驱，多个后继。

1.2.4. 兄弟的关系

（1）孩子：结点子树的根是该结点的孩子。
（2）兄弟：同一双亲的孩子之间互为兄弟。
（3）祖先：结点的祖先是从根到该结点所经分支上的所有结点。
（4）子孙：以某结点为根的子树中的任意结点都是该结点的子孙。

1.2.5. 兄弟间的关系

左右顺序不一样，分为有序树和无序数。

2. 树的表示

（1）结点连接表示
（2）二元组表示
（3）集合图表示
（4）凹凸表表示
（4）广义表表示

3. 树中相关操作

（1）初始化化树
（2）求根结点
（3）求当前结点的双亲结点
（4）求树T中结点x的第i个孩子
（5）求结点的x的右兄弟
（6）以结点x为根，并以F为子树森林构造树T
（7）将以x为根的子树作为结点Y的第i棵子树插入到树T中。
（8）将树T结点x的第i棵子树删除
（9）按某种次序依次访问树中各个结点，并使每个结点只访问一次。
（10）销毁树结构