二叉树
文章参考：
1.https://blog.csdn.net/xiaoquantouer/article/details/65631708
2.https://www.cnblogs.com/fly-me/p/wei-ti-jiaoer-cha-shu-de-si-zhong-bian-li-fang-fa.html
3.https://www.cnblogs.com/xinchrome/p/4905608.html
4. https://www.cnblogs.com/fengziwei/p/7891965.html
二叉树是一种常见的数据结构，结合了有序数组和链表的优点。二叉树中查找数据的速度与数组一样快，添加删除数据的速度也与链表一样高效。
1. 二叉树的基本概念
二叉树的递归定义为二叉树或者是一棵空树，或者是一棵由一个根节点和两个不相交的分别称为根节点的左子树和右子树的非空树。左子树和右子树同样是一棵二叉树。
1.1 二叉树常见的基本概念：
若一个结点有子树，那么该结点称为子树根的“双亲”，子树的根称为该结点的“孩子”。有相同双亲的结点互为“兄弟”。一个结点的所有子树上的任何结点都是该结点的后裔。从根结点到某个结点的路径上的所有结点都是该结点的祖先。
节点的度：节点所拥有的子树的个数。
叶子节点：度为0的节点，或者称为终端节点。
分支节点：度不为0的节点。
节点的层数：规定树的根节点的层数为1，其余节点的层数等于它的双亲节点的层数+1。
树的深度：树中各节点的层数的最大值。
树的度：树中各节点的度的最大值。
路径，路径长度：如果一棵树的一串节点n1,n2,….,nk有如下关系：节点ni是ni
+1的父节点（1<=i
1.2 二叉树的基本性质
二叉树的基本性质有四个：
- 二叉树第i层上的结点数目最多为2i-1(i>=1)
- 深度为k的二叉树至多有2k-1个结点（k>=1）
- 包含n个结点的二叉树的高度为[log2（n）]+1 ([]为向上取整)
- 在任意一棵二叉树中，若终端结点的个数为n0，度为2的结点数为n2，则n0=n2+1
性质4的证明：
因为二叉树中所有结点的度数均不大于2，不妨设n0表示度为0的结点个数，n1表示度为1的结点个数，n2表示度为2的结点个数。三类结点加起来为总结点个数，于是便可得到：n=n0+n1+n2 (1)
由度之间的关系可得第二个等式：n=n0*0+n1*1+n2*2+1即n=n1+2n2+1 (2)
将（1）（2）组合在一起可得到n0=n2+1
1.3 三种常见的树
满二叉树
在一棵二叉树中，如果所有分支节点都存在左子树和右子树，并且所有的叶子节点都在同一层上，这样的一棵二叉树称为满二叉树。如下图所示。
完全二叉树
一棵二叉树中，只有最下面两层结点的度可以小于2，并且最下层的叶结点集中在靠左的若干位置上，这样的二叉树称为完全二叉树。特点：叶子结点只能出现在最下层和次下层，且最下层的叶子结点集中在树的左部。显然，一棵满二叉树必定是一棵完全二叉树，而完全二叉树未必是满二叉树。如下图所示。
1.4 二叉树的实现代码
public class Node {
public int data;
public Node left;
public Node right;
public Node(int data) {
this.data = data;
}
}2. 二叉排序树
二叉排序树又称二叉查找树、二叉搜索树。它或者是一棵空树，或者是具有下列性质的二叉树：
1). 如果左子树不空，那么左子树上所有节点的值均小于它的根节点的值；
2). 如果右子树不空，那么右子树上所有节点的值均大于它的根节点的值；
3). 左右子树也分别为二叉排序树。
二叉排序树插入数据的实现
/**
* 将数据插入到二叉排序树中
* @param data
*/
public void insert(int data){
Node newNode=new Node(data);
if (root==null)
root=newNode;
else {
Node current=root;
Node parent;
//寻找数据的插入位置
while (true){
parent=current;
//插入到左子树
if (data<parent.data){
current=current.left;
//左子树为空则将数据插入否则进入下次循环
if (current==null){
parent.left=newNode;
return;
}
}
//插入到右子树
else {
current=current.right;
//右子树为空则将数据插入，否则进入下次循环
if (current==null){
parent.right=newNode;
return;
}
}
}
}
}3. 二叉树的遍历
二叉树的遍历（traversing binary tree）是指从根结点出发，按照某种次序依次访问二叉树中所有的结点，使得每个结点被访问依次且仅被访问一次。
3.1 前序遍历
若树为空，则空操作返回。否则，先访问根节点，然后前序遍历左子树，再前序遍历右子树。W）型 （中 左 右）。
前序遍历的实现
/**
* 前序遍历
* @param root
*/
public void preOrder(Node root){
if (root!=null){
System.out.print(new StringBuffer().append(root.data).append(" "));
preOrder(root.left);
preOrder(root.right);
}
}3.2 中序遍历
若树为空，则空操作返回。否则，从根节点开始（注意并不是先访问根节点），中序遍历根节点的左子树，然后是访问根节点，最后中序遍历根节点的右子树。（M）型，（左 中 右）
中序遍历的实现
/**
* 中序遍历
* @param root
*/
public void inOrder(Node root){
if (root!=null){
inOrder(root.left);
System.out.print(new StringBuffer().append(root.data).append(" "));
inOrder(root.right);
}
}3.3 后序遍历
若树为空，则空操作返回。否则，从左到右先叶子后双亲节点的方式遍历访问左右子树，最后访问根节点。（左右中）逆时针型 （左 右 中）
后续遍历的实现
/**
* 后序遍历
* @param root
*/
public void postOrder(Node root) {
if (root!=null){
postOrder(root.left);
postOrder(root.right);
System.out.print(new StringBuffer().append(root.data).append(" "));
}
}3.4 层序遍历
若树为空，则空操作返回。否则，从树的第一层，也就是根节点开始访问，从上到下逐层遍历，在同一层中，按从左到右的顺序结点逐个访问。
层序遍历的实现
可以使用队列来实现二叉树的层次遍历。主要思路如下：先将根节点放入队列中，然后每次都从队列中取出一个节点打印出该节点的值，若这个节点有子节点，则将它的子节点放入队列尾，直到队列为空。实现代码如下：
/**
* 层次遍历
* @param root
*/
public void layTranverse(Node root){
if(root==null)
return;
Queue<Node> q=new LinkedList<Node>();
q.add(root);
while (!q.isEmpty()){
Node n=q.poll();
System.out.print(new StringBuffer().append(n.data).append(" "));
if (n.left!=null)
q.add(n.left);
if (n.right!=null)
q.add(n.right);
}
}3.5 运行
写一个生成二叉树的程序：
/**
* 构造二叉树
* @param data
*/
public void buildTree(int[] data){
for (int i=0;i<data.length;i++){
insert(data[i]);
}
}main函数：
public static void main(String[] argus){
BinaryTree binaryTree=new BinaryTree();
int[] data={2,8,7,4,9,3,1,6,7,5};
binaryTree.buildTree(data);
binaryTree.inOrder(binaryTree.root);
System.out.println();
binaryTree.preOrder(binaryTree.root);
System.out.println();
binaryTree.postOrder(binaryTree.root);
System.out.println();
binaryTree.layTranverse(binaryTree.root);
}结果如下：
中序遍历结果：
1 2 3 4 5 6 7 7 8 9
前序遍历结果：
2 1 8 7 4 3 6 5 7 9
后序遍历结果：
1 3 5 6 4 7 7 9 8 2
层序遍历结果：
2 1 8 7 9 4 7 3 6 5 4. 还原二叉树
4.1 已知先序遍历和中序遍历，还原二叉树
已知先序遍历和中序遍历，还原二叉树：
先序遍历PreOrder: GDAFEMHZ
中序遍历InOrder: ADEFGHMZ
我们如何还原这颗二叉树
我们基于一个事实：中序遍历一定是 { 左子树中的节点集合 }，root，{ 右子树中的节点集合 }，前序遍历的作用就是找到每颗子树的root位置。
方法如下：
- 寻找树的root，前序遍历的第一节点G就是root。
- 观察前序遍历GDAFEMHZ，知道了G是root，剩下的节点必然在root的左或右子树中的节点。
- 观察中序遍历ADEFGHMZ。其中root节点G左侧的ADEF必然是root的左子树中的节点，G右侧的HMZ必然是root的右子树中的节点，root不在中序遍历的末尾或开始就说明根节点的两颗子树都不为空。
- 观察左子树ADEF，按照前序遍历的顺序来排序为DAFE，因此左子树的根节点为D，并且A是左子树的左子树中的节点，EF是左子树的右子树中的节点。
- 同样的道理，观察右子树节点HMZ，前序为MHZ，因此右子树的根节点为M，左子节点H，右子节点Z。
观察发现，上面的过程是递归的。先找到当前树的根节点，然后划分为左子树，右子树，然后进入左子树重复上面的过程，然后进入右子树重复上面的过程。最后就可以还原一棵树了：
步骤：
- 确定树的根节点。树根是当前树中所有元素在先序遍历中最先出现的元素，即先序遍历的第一个节点就是二叉树的根。
- 求解树的子树。找到根在中序遍历的位置，位置左边是二叉树的左孩子，位置右边是二叉树的右孩子，如果根节点左边或右边为空，那么该方向子树为空；如果根节点左边和右边都为空，那么根节点已经为叶子节点。
- 对二叉树的左右孩子分别进行步骤1和步骤2，直到求出二叉树的结构为止。
具体的代码实现如下：
/**
* 已知先序遍历和中序遍历，还原二叉树
* @param preOrder 先序遍历序列
* @param inOrder 先序遍历序列
* @return
*/
public Node buildTree(int[] preOrder,int[] inOrder){
return initTree(preOrder,0,preOrder.length-1,inOrder,0,inOrder.length-1);
}
public Node initTree(int[] preOrder,int start1,int end1,int[] inOrder,int start2,int end2){
if (start1>end1 || start2 >end2)
return null;
else {
int rootData=preOrder[start1];
Node head=new Node(rootData);
//找到根节点所在的位置
int flag=0;
for (int i=start2;i<=end2;i++)
if (rootData==inOrder[i]){
flag=i;
break;
}
//构建左子树
//flag-start2是左子树中节点的个数，start1+flag-start2则是结束位置
Node left=initTree(preOrder,start1+1,start1+flag-start2,inOrder,start2,flag-1);
//构建右子树
Node right=initTree(preOrder,start1+flag-start2+1,end1,inOrder,flag+1,end2);
head.left=left;
head.right=right;
return head;
}
}main函数：
public static void main(String[] argus){
int[] preorder={1,2,4,8,9,5,10,3,6,7};
int[] inOrder={8,4,9,2,10,5,1,6,3,7};
//相对应的前序遍历为1,2,4,8,9,5,10,3,6,7
Node postOrderRoot=buildTree(preOrder,inOrder);
//已知先序和中序遍历，得到后序遍历：
System.out.println("先序和中序遍历，得到后序遍历：");
postOrder(postOrderRoot);
}输出为：
已知先序和中序遍历，得到后序遍历：
8 9 4 10 5 2 6 7 3 1 4.2 已知中序遍历和后序遍历，还原二叉树
方法：
中序序列和后序序列为BDCEAFHG和DECBHGFA
求其先序序列为：
解：A为根结点，BDCE、FHG为左右子树，B,F为左右子节点，接着DCE为B的右子树，HG为F的右子树。依次类推求得先序序列为ABCDEFGH.
具体的实现代码如下：
/**
* 已知中序和后序遍历，还原二叉树
* @param inOrder 中序遍历
* @param postOrder 后序遍历
* @return
*/
public Node buildTree(int[] inOrder,int[] postOrder){
return initTree(inOrder,0,inOrder.length-1,postOrder,postOrder.length-1,0);
}
public Node initTree(int[] inOrder,int start1,int end1,int[] postOrder,int end2,int start2){
if (start1>end1 || start2 >end2)
return null;
else {
int rootData=postOrder[end2];
Node head=new Node(rootData);
//找到根节点所在的位置
int flag=0;
for (int i=start1;i<=end1;i++)
if (rootData==inOrder[i]){
flag=i;
break;
}
//构建左子树
//flag-start2是左子树中节点的个数，start1+flag-start2则是结束位置
Node left=initTree(inOrder,start1,flag-1,postOrder,start2-start1+flag-1,start2);
//构建右子树
Node right=initTree(inOrder,flag+1,end1,postOrder,end2-1,start2-start1+flag);
head.left=left;
head.right=right;
return head;
}
}main函数：
public static void main(String[] argus){
int[] inOrder={8,4,9,2,10,5,1,6,3,7};
int[] postOrder={8,9,4,10,5,2,6,7,3,1};
//相对应的前序遍历为1,2,4,8,9,5,10,3,6,7
Node postOrderRoot=buildTree(inOrder,postOrder);
//已知中序和后序遍历，得到先序遍历：
System.out.println("已知中序和后序遍历，得到先序遍历：");
preOrder(postOrderRoot);
}运行结果：
已知先序和中序遍历，得到后序遍历：
1 2 4 8 9 5 10 3 6 7 如果已知先序遍历和后序遍历，是不能还原二叉树的。
5. 二叉树中节点的最大距离
节点的距离是指这两个节点之间边的个数。本节求出的是一颗二叉树中相距最远的两个节点之间的距离。
思路：对二叉树的操作通过递归方法实现比较容易。求最大距离的主要思想如下：首先，求左子树距根节点的最大距离，记为leftMaxDistance；其次，求右子树距根节点的最大距离，记为rightMaxDistance，那么二叉树中节点的最大距离maxDistance满足maxDistance=leftMaxDistance+rightMaxDistance。
具体的实现代码如下：
class Node_1 {
public int data;
public Node_1 left;
public Node_1 right;
public int leftMaxDistance;
public int rightMaxDistance;
public Node_1(int data) {
this.data = data;
this.left = null;
this.right = null;
}
}
public class GetMaxDistance {
private int maxLen = 0;
private int max(int a, int b) {
return a > b ? a : b;
}
public void findMaxDistance(Node_1 root) {
if (root==null)
return;
if (root.left==null)
root.leftMaxDistance=0;
if (root.right==null)
root.rightMaxDistance=0;
if (root.left!=null)
findMaxDistance(root.left);
if (root.right!=null)
findMaxDistance(root.right);
//计算左子树中距离根节点的最大距离
if (root.left!=null)
root.leftMaxDistance=max(root.left.leftMaxDistance,root.left.rightMaxDistance)+1;
if (root.right!=null)
root.rightMaxDistance=max(root.right.leftMaxDistance,root.right.rightMaxDistance)+1;
if (root.leftMaxDistance+root.rightMaxDistance>maxLen)
maxLen=root.leftMaxDistance+root.rightMaxDistance;
}
}下一篇： MongoDB实现备份压缩的方法教程