Java中的数据结构（树）

1.什么是树？

树是一组有限结点的集合，满足每个结点只有一个结点指向他，一个结点可以指向多个结点

2.树的相关概念

根：没有前驱结点（没有任何结点指向它） 子节点：存在前驱结点的结点 叶子结点：没有后继结点（不指向任何结点，一种特殊的子节点） 兄弟结点：他们的前驱结点为同一个结点 树的高度：从所有叶节点开始数高度到根节点，其中的最大值；也就是从结点x向下到某个叶结点最长简单路径中边的条数。 树的深度（层）：树根下中所有分支结点层数的最大值，递归定义。（树的高度-1）

3. 二叉树（树的一种特殊形式）

特点： 二叉树每个结点最多有两个子节点。

二叉树的两种思想： ①.遍历思想（前，中，后序遍历，层序遍历） ②.迭代思想（根 + 左子树 +右子树）

完全二叉树和满二叉树

完全二叉树：若设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。 满二叉树（完全二叉树的一种特殊形式）：高度为h，由2^h-1个节点构成的二叉树称为满二叉树。

完全二叉树的特点： 高度 h = log(n) +1;r 左子树下标 leftIndex = （index - 1 ） * 2 + 1; 右子树下标 rightIndex = (index - 1) * 2 ;