树形结构是一类重要的非线性数据结构. 期中以树和二叉树最为常用, 直观看来, 树是以分支关系定义的层次结构. 树结构在客观世界中广泛存在, 如人类社会的族谱和各种社会组织机构都可树来形象表示. 本文重点内容是树的定义和基本术语, 以及二叉树的定义, 主要分为三部分 :
- 树的定义
- 基本术语
- 二叉树结构
一.树的定义 :
- (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 的结点一一对应时, 称之为 *完全二叉树.
完全二叉树
网友评论