Java DataStructure-Tree

树的基本概念

树是数据元素之间具有次层关系的非线性的结构，树是由n(n≥0)个结点组成的有限集合，n=0的树是空树，n大于0的树T由以下两个条件约定构成：

• ⑴.有一个特殊的结点，称为根结点（root），它没有前驱结点只有后继结点。

• ⑵.除了根结点之外的其他结点分为m(0≤m≤n)个互不相交的集合T0,T1,T2,…,Tm−1T0,T1,T2,…,Tm−1,其中吧每个集合TiTi也是一个树型结构，称之为子树(Subtree)。

树的结构如下：

相关术语：

（1）根结点： 根结点是没有双亲的结点，一棵树中最多有一个根结点（如上图的A结点）。

（2）孩子结点： 一棵树中，一个结点的子树的根结点称为其孩子结点，如上图的A的孩子结点右B、C、D。

（3）父母结点： 相对于孩子结点而已其前驱结点即为父母结点，如上图的B、C、D 三个结点的父母结点都为A，当然E、F结点的父母结点则是B。

（4）兄弟结点： 拥有相同的父母结点的所有孩子结点叫作兄弟结点，如上图B、C、D 三个结点共同父结点为>A，因此它们是兄弟结点，E、F也是兄弟结点，但是F、G就肯定不是兄弟结点了
。
（5）祖先结点： 如果存在一条从根结点到结点Q的路径，而且结点P出现在这条路径上，那么P就是Q的祖先结点，而结点Q也称为P的子孙结点或者后代。如上图的E的祖先结点有A和B，而E则是A和B的子孙结点。

（6）叶子结点： 没有孩子结点的结点叫作叶子结点，如E、F、G、H等。

（7）结点的度： 指的是结点所拥有子树的棵数。如A的度为3，F的度为0，即叶子结点的度为0，而树的度则是树中各个结点度的最大值，如图（d）树的度为3（A结点）

（8）树的层： 又称结点的层，该属性反映结点处于树中的层次位置，我们约定根结点的层为1，如上图所示，A层为1，B层为2，E的层为3。

（9）树的高度(深度)： 是指树中结点的最大层数，图（d）的高度为3。

（10）边： 边表示从父母结点到孩子结点的链接线，如上图（d）中A到B间的连线则称为边。

---

BinaryTree

二叉树的定义： 二叉树（Binary Tree）是n(n≥0)个结点组成的有限集合，n=0时称为空二叉树；n>0的二叉树由一个根结点和两棵互不相交、分别称为左子树和右子树的子二叉树构成，二叉树也是递归定义的，在树种定义的度、层次等术语，同样适用于二叉树。

BinaryTree-Wiki

BinaryTree的重要特性：

1. 若根结点的层次为1，则二叉树第i层最多有2^i−1(i≥1)个结点

数学归纳法：
步骤① 假设根为i=1层上唯一结点，则有2^i−1=2^0=1成立。
步骤② 设第i-1层最多有2^i−2，由于二叉树中每个结点的度最多为2，因此第i层最多有2^i−1个结点也成立。

2. 在高度为h的二叉树中，最多有2h−1个结点（h≥0）

由第一个性质可以推出

3.满二叉树和完全二叉树

完全二叉树：
叶节点只能出现在最下层和次下层，并且最下面一层的结点都集中在该层最左边的若干位置的二叉树。

满二叉树：
一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为K，且结点总数是(2^k) -1 ，则它就是满二叉树。

4.棵具有n个结点的完全二叉树，对于序号为i(0≤i＜n)的结点，则有如下规则

* 若i=0，则i为根结点，无父母结点；若i>0，则i的父母结点序号为⌊(i−1)/2⌋(向下取整)
* 若2i+1＜n,则i的左孩子结点序号为2i+1，否则i无左孩子。
* 若2i+2＞n,则i的右孩子结点序号为2i+2，否则i无右孩子。