【Java数据结构】二叉树
1.树型结构
1.1树的概念
树是一种非线性的数据结构，由n个结点组成的具有层次关系的集合。下面是它的特点：
- 根结点是没有前驱的结点（没有父结点的结点）
- 子结点之间互不相交
- 除了根结点外，其它结点都只有一个父结点
- n个结点有n-1条边
下面介绍一些常见的概念：
- 结点的度：该结点有多少子节点，度就为几
- 树的度：一个树中每个结点度中最大的那个就是树的度
- 叶子结点：度为0的结点（不唯一）
- 根结点：没有前驱的结点（也就是没有父结点的结点）
- 双亲结点（父结点）：该结点的父结点（唯一）
- 孩子结点（子结点）：该结点的子结点（不唯一）
- 结构的层次：从根结点为第一层，往后数
下面这些就是了解即可：
- 树的高度：有几层树就有多高
- 非终端结点（分支节点）：除根结点和叶子结点外的结点
- 兄弟结点：相同父结点之间称兄弟
- 堂兄弟结点：父结点在同一层但不是同一个的结点之间称为堂兄弟
- 结点的祖先：在一棵树上，根结点是所有结点的祖先
- 子孙：该结点为根，往后层数与它相关的结点都是它的子孙
- 森林：由m个互不相交的树组成的就是森林
1.2树的表现形式
树的表现形式分多种，如双亲表示法、孩子表示法、孩子双亲表示法、孩子兄弟表示法等等，常用的就是孩子兄弟表示法。
2.二叉树
2.1二叉树的概念
一颗二叉树是结点的一个有限集合， 其中二叉树不存在度大于2的结点，并且二叉树的左子树和右子树是不能互换的，空树也是二叉树。
2.2特殊二叉树
- 满二叉树：满二叉树就是每层的结点数都达到该层最大值。如果由k层，那么结点总数就是2^（k-1）；
- 完全二叉树：完全二叉树就是假设有k层，其k-1层中每一层都是满的，在第k层中必须要从左到右依次放结点，如果中间出现空那么就不是二叉树；
2.3二叉树的性质
- 第i层上最多有2^（i-1）个结点；
- 深度为k的二叉树最大结点数为2^k-1（将每一层的结点数相加=>等比数列求和）；
- 叶子结点有n0个，度为2的结点有n2个，就会出现n0 = n2 + 1这个式子；
- n个结点的完全二叉树的深度k为log (n+)向上取整；
- n个结点的二叉树，从上到下，从左到右排序。（1）已知父结点下标为i，求孩子结点下标。左孩子下标：(2*i)+1；右孩子下标：(2*i)+2 ；（2）已知孩子结点下标i，求父结点下标。父结点下标：(i-1)/2;
下面是一些关于二叉树性质的题目：
由于度为0的结点数等于度为2的结点数加1，题目已知度为2的结点数就可以得到度为0的结点数，所以答案选B。
如果总结点数为偶数，那么度为1的结点个数是1个；如果结点为奇数，那么度为1的结点个数为0，再根据n0 = n2 + 1，就可以求出叶子结点个数，所以答案选A。
由于log (n+1) 向上取整就是这个二叉树的高度，2^9 = 512 < 531 < 2^10 = 1024，所以答案选B。
2.4二叉树的存储
二叉树的存储分顺序存储和类似于链表的链式存储，现在主要讲解链式存储。
链式存储是将一个一个结点连起来，一个结点有数据域和引用域（可多个），每个表示法的引用域都不是一样的，举一个例子：
// 孩子表示法
class Node {
int val; // 数据域
Node left; // 左孩子的引用
Node right; // 右孩子的引用
}
2.5二叉树的创建（简单型）
首先和之前的线性表一样，使用内部类创建结点，然后再创建二叉树对应的结点个数，然后再将它们串连成二叉树，下面是孩子表示法结点创建：
public class BrinaryTree {
static class Node{
public char val;
public Node left;
public Node right;
public Node(char val){
this.val = val;
}
}
//创建二叉树
public Node creatTree(){
Node A = new Node('A');
Node B = new Node('B');
Node C = new Node('C');
Node D = new Node('D');
Node E = new Node('E');
Node F = new Node('F');
Node G = new Node('G');
Node H = new Node('H');
A.left = B;
A.right = C;
B.left = D;
B.right = E;
C.left = F;
C.right = G;
E.right = H;
return A;
}2.6二叉树的遍历
以上是三种遍历，如果只是想要了解如何遍历而不是想通过常规手段得到答案的话，上面的方法就是最简单的理解方式。如果是前序遍历首先在结点左边（也可以称结点前面）做一个记号；如果是中序遍历首先在结点下面（也可以称结点中间）做一个记号；如果是后序遍历首先在结点右边（也可以称结点后面）做一个记号，然后从根结点的左边开始，围绕二叉树外延走一圈，最后到的根结点的右边为结束，在这过程中接触记号的顺序就是遍历的结果。
如果是按照常规思路来讲，就是什么遍历根结点就在哪个位置。比如前序遍历就是根左右，中序遍历就是左根右，后序遍历就是左右根。如果这个结点又是左结点又是根结点，那就根结点，其它的情况一样的。
下面我们用代码来实现这些遍历：
- 前序遍历
不管如何第一步都是判断这棵树是否为空，然后就是打印该根结点，然后用递归将根结点的左边的树遍历一遍，再用递归把根结点右边的树遍历一遍。下面是一棵二叉树的代码及遍历过程：
public void preOrder(Node root){
if(root == null)
return ;
System.out.print(root.val+" ");
preOrder(root.left);
preOrder(root.right);
}
前序遍历返回链表结构
如果是返回一个链表结构，那就要利用返回的链表实现遍历，看图更能直观理解意思以及代码。（理解前序后，中序后序都是一个道理）
public List<Node> preOrder2(Node root){
List<Node> ret = new ArrayList<>();
if (root == null)
return ret;
ret.add(root);
List<Node> Left = preOrder2(root.left);
ret.addAll(Left);
List<Node> Right = preOrder2(root.right);
ret.addAll(Right);
return ret;
}- 中序遍历
中序遍历道理差不多，开始也是判断是否为空，然后通过递归遍历根结点左边的树，再打印根结点，最后再递归遍历根结点右边的树。
public void inOrder(Node root){
if (root == null)
return;
inOrder(root.left);
System.out.print(root.val+" ");
inOrder(root.right);
}中序遍历返回链表结构
public List<Node> inOrder2(Node root) {
List<Node> ret = new ArrayList<>();
if (root == null)
return ret;
List<Node> leftTree = inOrder2(root.left);
ret.addAll(leftTree);
ret.add(root);
List<Node> rightTree = inOrder2(root.right);
ret.addAll(rightTree);
return ret;
}- 后序遍历
后序遍历也是一样道理，只是换成了左右根，先根遍历结点左边的树，然后遍历根结点右边的树，最后在打印。
public void postOrder(Node root){
if (root == null)
return ;
postOrder(root.left);
postOrder(root.right);
System.out.print(root.val+" ");
}后序遍历返回链表结构
public List<Node> postOrder2(Node root) {
List<Node> ret = new ArrayList<>();
if (root == null)
return ret;
List<Node> leftTree = postOrder2(root.left);
ret.addAll(leftTree);
List<Node> rightTree = postOrder2(root.right);
ret.addAll(rightTree);
ret.add(root);
return ret;
}