+循环链表 Day26 Java中的数据结构概念(4)

树是由一个集合以及在该集合上定义的一种关系构成的。+循环链表集合中的元素称为树的结点，所定义的关系称为父子关系。

父子关系在树的结点之间建立了一个层次结构。

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

在这种层次结构中有一个结点具有特殊的地位，这个结点称为该树的根结点，或简称为树根。

我们可以形式地给出树的递归定义如下：

树（tree ）是 n（n ≥ 0）个结点的有限集。它

1) 或者是一棵空树（n = 0），空树中不包含任何结点。

2) 或者是一棵非空树（n > 0），此时有且仅有一个特定的称为 根（root ）的结点；

当n > 1 时，其余结点可分为m（m > 0）个互不相交的有限集T 1 ，T 2 ，…，T m ，

其中每一个本身又是一棵树，并且称为根的 子树（sub tree） ）。

例如图 （a）是一棵空树、（b）是只有一个根节点的树、（c）是一棵有 10个结点的树，其中A是根，

其余的结点分成 3 个不相交的集合：T1 ={B,E,F}、T2 ={C,G}、T3 ={D,H,I,J}，每个集合都构成一棵树，且都是根A的子树。

生活案例：树：单位组织架构、族谱

技术案例：文件系统。

结点拥有的子树的数目称为结点的 度（Degree） ）。

度为 0 的结点称为 叶子（leaf ）或终端结点。

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

树内各结点的度的最大值称为树的度

父亲、儿子、兄弟

父亲（parent）：一个结点的直接前驱结点

儿子（child）：一个结点的直接后继结点

兄弟（sibling） ：同一个父亲结点的其他结点

结点 A 是结点 B、C、D 的父亲，结点 B、C、D 是结点 A 的孩子。

由于结点 H、I、J 有同一个父结点 D，因此它们互为兄弟。

祖先、子孙、堂兄弟

将父子关系进行扩展，就可以得到祖先、子孙、堂兄弟等关系。

结点的 祖先是从根到该结点路径上的所有结点。

以某结点为根的树中的任一结点都称为该结点的 子孙。

父亲在同一层次的结点互为 堂兄弟

每个结点的度均不超过 2 的有序树，称为 二叉树（binary tree） 。

与树的递归定义类似，二叉树的递归定义如下：

二叉树或者是一棵空树，或者是一棵由一个根结点和两棵互不相交的分别称为根的左子树和右子树的子树所组成的非空树。

由以上定义可以看出，

二叉树中每个结点的孩子数只能是 0、1 或 2 个，并且每个孩子都有左右之分。

位于左边的孩子称为左孩子，位于右边的孩子称为右孩子；

以左孩子为根的子树称为左子树，以右孩子为根的子树称为右子树。

满二叉树：

高度为k并且有 2k+1 -1 个结点的二叉树。

在满二叉树中，每层结点都达到最大数，即每层结点都是满的，因此称为满二叉树。+循环链表

完全二叉树：

若在一棵满二叉树中，在最下层从最右侧起去掉相邻的若干叶子结点，得到的二叉树即为完全二叉树。

二叉树的存储结构有两种：顺序存储结构和链式存储结构。

顺序存储结构

对于满二叉树和完全二叉树来说，可以将其数据元素逐层存放到一组连续的存储单元中，如图所示。

用一维数组来实现顺序存储结构时，将二叉树中编号为 i 的结点存放到数组中的第 i 个分量中。

如此根据二叉树性质，可以得到结点 i 的父结点、左右孩子结点分别存放在 、2i 以及 2i+1 分量中

这种存储方式对于满二叉树和完全二叉树是非常合适也是高效方便的。

因为满二叉树和完全二叉树采用顺序存储结构既不浪费空间，也可以根据公式很快的确定结点之间的关系。

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-62503-4.html