【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;}