1. 树形结构

1.1 定义

树是一种非线性的数据结构，它是由n($n\ge 0$)个有限结点组成一个具有层次关系的集合。把它叫作树是因为它看起来像一棵倒挂的树，也就是说它是根朝上叶朝下的。
树具有以下特点：

• 有一个特殊的结点，称为根结点，根结点没有前驱结点。
• 除根结点外，其余结点被分成M(M>0)个互不相交的集合$T_1、T_2、......、T_m$，其中每一个集合$T_i(1\le i\le m)$又是一棵与树类似的子树。每棵子树的根结点有且只有一个前驱，可以有0个或者多个后继。
• 树是递归定义的。
  

注意：

1. 树形结构中，子树之间不能有交集，否则就不是树形结构。
2. 除了根结点之外，每个结点有且仅有一个父结点。
3. 一棵N个结点的树有N-1条边。(从下往上看)

1.2 概念

1. 结点的度：一个结点含义子树的个数称为该结点的度；例如上图中，A的度为6.
2. 树的度：一棵树中，所有结点度的最大值称为树的度；例如上图中，树的度为6.
3. 叶子结点(终端结点)：度为0的结点称为叶结点；例如上图中，B、C、H、I…等结点为叶子结点。
4. 双亲结点(父结点)：若一个结点含义子结点，则这个结点称为其子节点的父结点；例如上图中，A是B的父结点。
5. 孩子结点(子结点)：一个结点含义的子树的根结点称为该结点的子结点；例如上图中，B是A的子结点。
6. 根结点：一棵树中，没有双亲结点的结点；例如上图中，A就是根结点。
7. 结点的层次：从根开始定义起，根为第一层，根的子结点为第二层，以此类推。
8. 树的高度或深度：树中结点的最大层次；如上图：树的高度为4.
   以下概念只需了解
9. 非终端结点或分支结点：度不为0的结点；如上图；A、D、E、J、F、G，这些结点为分支结点。
10. 兄弟结点：具有相同父结点的结点互称为兄弟结点；例如上图中的B、C。
11. 堂兄弟结点：双亲在同一层的结点为堂兄弟结点；例如上图中的H、I。
12. 结点的祖先：一个点的双亲、双亲的双亲…都是该结点的祖先，注意根结点是所有子结点的祖先。双亲是一个集合概念。
13. 子孙：以某结点为根的子树中任何一个结点都称为该结点的子孙。如上图中，所有结点都是A的子孙。
14. 森林：由m($m\ge 0$)棵互不相交的树组成的集合称为森林。

1.3 树的表示形式

树结构比线性表复杂，存储起来比较麻烦。实际中树有很多表示方法，比如：双亲表示法、孩子表示法、孩子双亲表示法、孩子兄弟表示法。简单了解一下孩子兄弟表示法：

class Node{
int value;//树中存储的数据
Node firstChild;//第一个孩子引用
Node nextBrother;//下一个兄弟引用

2. 二叉树

2.1 概念

一棵二叉树是结点的有限集合，该集合：

1. 或者为空
2. 或者是由一个根结点加上两棵分别称为左子树和右子树的二叉树组成。
   

从上图中可以看出：

1. 二叉树不存在度大于2的结点。
2. 二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树。

注意：对于任意的二叉树都是由以下几种情况复合而成的。

2.2 两种特殊的二叉树

1. 满二叉树：一棵二叉树，如果每层的结点树都达到最大值，则这棵二叉树就是满二叉树。也就是说，如果一棵二叉树的层数为K，且总结点数是$2^K-1$，则它就是满二叉树。
2. 完全二叉树：完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树引出来的。对于深度为k的，有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从0至n-1的结点一一对应时称之为完全二叉树。
   
   注：完全二叉树的k-1层是满的，第k层是都连续靠左的。

2.3 二叉树的性质

1. 若规定根结点的层数为1，则一棵非空二叉树的第i层上最多有$2^{i-1}(i>0)$个结点。
2. 若规定只有根结点的二叉树的深度为1，则深度为k的二叉树的最大结点数是$2^k-1(k\ge 0)$.
3. 对任何一棵树，如果其叶结点的个数为$n_0$，度为2的非叶结点个数为$n_2$，则有$n_0=n_2+1$。

公式推导：假设二叉树中总的结点个数为N，度为0的结点个数为n0个，度为1的结点个数为$n_1$个，度为2的结点个数为$n_2$个。则可得
$N=n_0+n_1+n_2$-------式子1
二叉树总的结点个数为N，在二叉树中总共有N-1条边------从下往上看，
$n_0$的结点-----叶子结点：往下不可能产生边
$n_1$的结点------只有一个孩子的结点：往下只能产生一条边
$n_2$的结点------两个孩子的结点：往下可以产生两条边
利用总的边数建立等式：
$N-1=n_1+2\ast n_2$-------式子2
将式1和式2联立即可得$n_0=n_2+1$。

4. 具有n个结点的完全二叉树的深度k为$lo{g}_2(n+1)$向上取整。
5. 对于具有n个结点的完全二叉树，如果按照从上至下、从左至右的顺序对所有结点从0开始编号，则对于序号为i的结点有;

• 若i>0，双亲序号：(i-1)/2；i=0，i为根结点编号，无双亲结点；
• 若2i+1<n，左孩子序号：2i+1，否则无左孩子；
• 若2i+2<n，右孩子序号：2i+2，否则右有孩子；

2.4二叉树的存储

二叉树的存储结构分为：顺序存储和类似于链表的链式存储。
顺序存储：适合存储完全二叉树；
链式结构：任意二叉树的存储；
问题：为什么完全二叉树比较适合使用顺序结构存储？
二叉树的链式存储是通过一个一个的结点引用起来的，常见的表示方式有二叉和三叉表示方式，具体如下：

//孩子表示法
class Node{
int val;//数据域
Node left;//左孩子的引用，常常代表左孩子为根的整棵左子树
Node right;//右孩子的引用，常常代表右孩子为根的整棵右子树
}

//孩子双亲表示法
class Node{
int val;//数据域
Node left;//左孩子的引用，常常代表左孩子为根的整棵左子树
Node right;//右孩子的引用，常常代表右孩子为根的整棵右子树
Node parent;//当前结点的根结点

注：本文采用孩子表示法来构建二叉树。

2.5 二叉树的基本操作

2.5.1 前置说明

  在学习二叉树的基本操作前，需要先创建一棵二叉树，然后才能学习其相关的基本操作。为了效率更高，我们先手动快速创建一棵二叉树，快速进入二叉树操作学习，等二叉树了解得差不多的时候，再回来研究二叉树真正的创建方式。

public class BinaryTree {public static class BTNode {BTNode left;//引用当前结点的左孩子BTNode right;//引用当前结点的右孩子int value;public BTNode(int value) {this.value = value;}}BTNode root;//指向二叉树的根结点//自己手动创建一棵二叉树public void createBinaryTree(){BTNode node1=new BTNode(1);BTNode node2=new BTNode(2);BTNode node3=new BTNode(3);BTNode node4=new BTNode(4);BTNode node5=new BTNode(5);BTNode node6=new BTNode(6);node1.left=node2;node2.left=node3;node1.right=node4;node4.left=node5;node4.right=node6;root =node1;}public static void main(String[] args) {BinaryTree bt=new BinaryTree();bt.createBinaryTree();}
}

注意：上述代码并不是创建二叉树的方式，真正创建二叉树的方式后续详细介绍。
二叉树：

1. 空树；
2. 非空：根结点，根结点的左子树、根结点的右子树组成。
3. 二叉树定义是递归式的，后续基本操作基本都是按照该概念实现的。
   

2.5.2 二叉树的遍历

1. 前中后序遍历
     学习二叉树结构，最简单的方式就是遍历。遍历就是沿着某条搜索路线，依次对树中每个结点均做一次且仅做一次访问。访问结点所做的操作依赖于具体的应用问题(比如：打印结点内容、结点内容加1)。遍历是二叉树上最重要的操作之一，是二叉树上进行其他运算的基础。
     在遍历二叉树时，如果没有进行某种约定，每个人都按照自己的方式遍历，得出的结果就比较混乱，如果按照某种规则进行约定，则每个人对于同一棵树的遍历结果肯定是相同的。如果N表示根结点，L表示根结点的左子树，R表示根结点的右子树，则根据遍历根结点的先后次序有以下遍历方式：

• NLR：前序遍历—访问根结点—根的左子树-----根的右子树。
• LNR：中序遍历—根的左子树—访问根结点-----根的右子树。
• LRN：后序遍历—根的左子树-----根的右子树—访问根结点。

 //将递归方式再包装一层public void preOrder(){System.out.println("前序遍历：");preOrder(root);System.out.println();}public void inOrder(){System.out.println("中序遍历：");inOrder(root);System.out.println();}public void postOrder(){System.out.println("后序遍历：");postOrder(root);System.out.println();}public int size(){return size(root);}//二叉树不为空----需要借助队列完成二叉树的层序遍历//Queue<>//前序遍历----根结点---左子树---右子树//操作：对结点中的值域进行打印public void preOrder(BTNode treeRoot){/* if(null==root){return;}//非空//1.先遍历根结点System.out.print(root.value+" ");//2.再遍历根结点的左子树----注意：根结点的左子树也是二叉树，遍历根结点的左子树与遍历原树的规则一样preOrder(root.left);//3.最后遍历根结点的右子树preOrder(root.right);*///简化代码if(treeRoot!=null){System.out.print(treeRoot.value+" ");preOrder(treeRoot.left);preOrder(treeRoot.right);}}//中序遍历private void inOrder(BTNode treeRoot){if(treeRoot!=null){inOrder(treeRoot.left);System.out.print(treeRoot.value+" ");inOrder(treeRoot.right);}}//后序遍历private void postOrder(BTNode treeRoot){if(treeRoot!=null){postOrder(treeRoot.left);postOrder(treeRoot.right);System.out.print(treeRoot.value+" ");}}

2. 层序遍历
   除了前序遍历、中序遍历、后序遍历外，还可以对二叉树进行层序遍历。假设二叉树的根结点所在的层数为1，层序遍历就是从所在的二叉树的根结点出发，首先访问第一层的根结点，然后从左往右访问第二层上的结点，接着就是第三层的结点。以此类推，自上而下，自左往右，逐层访问树的结点的过程就是层序遍历。
   

2.5.3 二叉树的基本操作

//获取二叉树中结点的个数private int size(BTNode treeRoot){if(treeRoot==null){return 0;}return 1+size(treeRoot.right)+size(treeRoot.left);}

//获取叶子结点的个数
//当程序往下递归时，遇到叶子结点，无需继续往下递归----本次递归直接退出
//获取二叉树中叶子结点的个数：private int getLeafNode(BTNode treeRoot){if(treeRoot==null){return 0;}if(treeRoot.right==null&&treeRoot.left==null){return 1;}return getLeafNode(treeRoot.left)+getLeafNode(treeRoot.right);}

 //获取二叉树中第k层结点的个数-----认为根在第1层private int getKLevelNode(BTNode treeRoot,int k){if(treeRoot==null||k<=0){return 0;}//k==1，说明：获取第一层的结点数，第一层只有根结点if(k==1){return 1;}return getKLevelNode(treeRoot.left,k-1)+getKLevelNode(treeRoot.right,k-1);}

//获取树的高度private int height(BTNode treeRoot){if(treeRoot==null){return 0;}int leftHeight=height(treeRoot.left);int rightHeight=height(treeRoot.right);return leftHeight>rightHeight?leftHeight+1:rightHeight+1;}

 //查找值为value的结点，并返回private BTNode find(BTNode treeRoot,int value){if(treeRoot==null){return null;}if(treeRoot.value==value){return treeRoot;}BTNode ret=find(treeRoot.left,value);if(ret!=null){return ret;}return find(treeRoot.right,value);//左子树没找到，再到右子树中来找}