数据结构和算法-01树与二叉树基本概念

树形结构是一类重要的非线性数据结构. 期中以树和二叉树最为常用, 直观看来, 树是以分支关系定义的层次结构. 树结构在客观世界中广泛存在, 如人类社会的族谱和各种社会组织机构都可树来形象表示. 本文重点内容是树的定义和基本术语, 以及二叉树的定义, 主要分为三部分 :

• 树的定义
• 基本术语
• 二叉树结构

一.树的定义 :

• (a)只有根结点的树
• (b)一般的树

图1

树(Tree)是 n (n ≥ 0) 个结点的有限集. 在任意非空树中:

• (1)有且仅有一个特定的称为根 (Root) 的结点;

• (2)当 n > 1 时, 其余结点可分为 m (m > 0) 个互不相交的有限集 T1 , T2 ... Tm ;
  其中每个集合本身又是一棵树, 并且称为根的子树 (SubTree).

• 例如在上图中, (a)是只有一个根结点的树, (b)是有13个结点的树, 其中 A 是根, 其余结点分成 3 个互不相交的子集: 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}, F是 B的子树, 同时其本身又是只有一个根结点的树.

二. 基本术语 :

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

• 结点的度: 结点拥有的子树的数量称为结点的度(Degree).
  例如，在图1(b) 中，A 的度为 3，C的度为 1，F的度为 0。

• 叶子: 度为 0 的结点称为叶子 (Leaf) 或终端结点。
  图1(b) 中的结点K、L、F、G、M、1、]都是树的叶子.

• 非终端结点 / 分支结点: 度不为 0 的结点称为非终端结点或分支结点。
  除根结点之外，分支结点也称为内部结点，

• 树的度: 树的度是树内各结点的度的最大值。
  如图1(b)的树的度为 3。

• 孩子: 结点的子树的根称为该结点的孩子 (Child),

• 双亲 : 该结点称为孩子的双亲 (Parent)。
  例如，在图1(b所示的树中，D为A的子树T的根，则D是A的孩子，而A则是D的双亲，

• 兄弟 : 同一个双亲的孩子之间互称兄弟 (Sibling)。
  例如，H、I和J互为兄弟。将这些关系进一步推广，可认为D是M的祖父。

• 祖先 : 结点的祖先是从根到该结点所经分支上的所有结点。
  例如，M 的祖先为 A、D和H。

• 子孙 : 以某结点为根的子树中的任一结点都称为该结点的子孙。如B的子孙为E、K、L和F。

• 结点的层 : 结点的层 (Level)从根开始定义起，根为第一层，根的孩子为第二层。
  若某结点在第l层，则其子树的根就在第l+1层。

• 堂兄弟 : 其双亲在同一层的结点互为堂兄弟。
  例如，结点G与E、F、H、I、J互为堂兄弟。

• 树的深度 / 树的高度 : 树中结点的最大层次称为树的深度 (Depth) 或 高度，
  图1 (b)所示的树的深度为 4。

• 有序树 / 有序树 : 如果将树中结点的各子树看成从左至右是有次序的(即不能互换)，则称该树为有序树，否则称为无序树。

• 第一个孩子 / 最后一个孩子 : 在有序树中最左边的子树的根称为第一个孩子，最右边的称为最后一个孩子.

• 森林 : 森林 (Forest)是 m (m ≥ 0）棵互不相交的树的集合。
  对树中每个结点而言，其子树的集合即为森林。由此，也可以森林 和 树相互递归的定义来描述树。

就逻辑结构而言，任何一棵树是一个二元组 Tree = (root, F)，其中：root 是数据元素，称做树的根结点；F 是m (m = 0) 棵树的森林，F = (T1，T2, ... , Tm)，其中 Ti = (ri，Fi）称做根 root 的第 i 棵子树：当m 为非 0 时，在树根和其子树森林之间存在下列关系：

RF = {< root, ri > | i = 1, 2, … , m, m > 0}.

这个定义将有助于得到森林和树与二叉树之间转换的递归定义。

树的度, 结点的度, 层次, 高度

三. 二叉树

1. 定义
二叉树 (Binary Tree)是另一种树型结构，它的特点是每个结点至多只有两棵子树(即二叉树中不存在度大于 2 的结点)，并且，二叉树的子树有左右之分，其次序不能任意颠倒。

二叉树

2. 性质 (由于有公式, 此处用截图)

二叉树性质

二叉树基本术语

• 满二叉树 : 一棵深度为 k 且有 2的k次方减1 个结点的二叉树称为 满二叉树.
  

  满二叉树

• 完全二叉树 : 深度为 k 的, 有 n 个结点的二叉树, 当且仅当其每个结点都与深度为 k的满二叉树中编号从 1 至 n 的结点一一对应时, 称之为 *完全二叉树.
  

  完全二叉树