关于二叉树
前言
我们前面的栈丶队列丶链表等等都是一对一的数据结构，但是树是一对多的数据结构。树也有很多的分类，但是笔者在这里仅仅涉及二叉树，其他树会在后续涉及。
一丶树的相关定义
树是n个有限节点组成一个具有层次关系的集合。为什么叫做树呢？
这像什么呢？
是不是像倒过来的一棵树呢？
当节点为0时，我们称之为空树，当节点>1的时候，它们又可以分为m（m>0）个互不相交得到有限集。
那么在这里有些定义需要声明一下（配着图看）：
根结点
没有前驱的节点叫做根节点
结点的度
一个结点含有子树的个数
树的度
所有结点的度最大的那一个叫做树的度
叶子结点
度为0的结点
结点的层次
根为第一层，根的子节点为第二层，依次往下推
树的高度
最大的层次节点
二丶二叉树相关定义
二叉树是一个比较特殊的树，所谓二叉树是结点的一个有限集合。这个集合：
1.为空
2.由根节点再加上左子树和右子树的二叉树组成
这里的定义主要看哪里呢？就是第二个，可以看到左子树和右子树也都是二叉树。那么这意味着什么呢？没错，二叉树是递归定义的（事实上树都是递归定义的）。
那么这就意味着，所有的二叉树其实无非就有以下的几种而已：
所有的二叉树都是由上述二叉树拼接而成。
1.二叉树的度不能大于2
2.二叉树有严格的左右子树之分。子树次序不能颠倒
关于满二叉树
什么叫做满二叉树呢？
二
叉
树
每
一
个
层
次
的
结
点
数
目
都
达
到
了
最
大
值
的
叫
做
满
二
叉
树
\color{red}{二叉树每一个层次的结点数目都达到了最大值的叫做满二叉树}
二叉树每一个层次的结点数目都达到了最大值的叫做满二叉树
关于完全二叉树
那什么叫做完全二叉树呢？
完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。
怎么说呢？如下图：
二叉树性质
（1）第i层的最大结点数
这里的最大节点可以用满二叉树来进行考虑。
第一层：2^(1 - 1) = 1
第二层：2^(2 - 1) = 2
第三层：2^(3 - 1) = 4
…
所以由数学归纳法可以推出，第i层最大节点数为：2^(i - 1)
（2）深度为k的最大结点数
我们可以发现，随着层次的加深，每一层都是上一层结点数的二倍。所以如果深度为k，那么最大结点数其实就是
首项为1，每一项与后一项之比为1/2的前k项的等比数列之和。化简之后就是：
2^n - 1
（3）叶子结点总比度为2的节点多1
对任何一棵二叉树, 如果其叶结点个数为 n0, 度为2的非叶结点个数为 n2,则有n0＝n2＋1。
那么对于这个结论我们是怎么得到的呢？
首先我们要知道一个结论：
二
叉
树
中
，
结
点
数
比
边
数
多
1
\color{red}{二叉树中，结点数比边数多1}
二叉树中，结点数比边数多1
这个很好想象，因为在二叉树里每一个节点都只有一个前驱除了根节点，所以上述是成立的。
那么推导一下：
在二叉树中，结点有那几个呢？
度为1的结点，度为2的结点，度为0的结点。
那么设置度为0的结点为n0，度为1的结点为n1，度为2的结点为n2。那么
n0 + n1 + n2 = 总结点。
总结点设置为n，那么 n + 1 = 0 * n0 + 1 * n1 +2 * n2,这里全部转换成边数来进行运算。化简之后就可以得到我们的结论： n0 = n2 + 1
（4） 具有n个结点的二叉树的深度
这里这个结论怎么推导呢？
前面我们说过，深度为k的节点的最大节点数为 2^k - 1 = N（N为最大节点
数），那么我们化简成：2 ^ k = N + 1,然后以2为底，取N + 1的对数，也就是： ㏒₂(n+1) = k。
那么如果是满二叉树我们当然可以轻而易举的取到对应的深度k，但是如果是完全二叉树呢？
也很简单，向下取整就好啦。
（5）判断根、双亲、左右孩子和总结点的关系
对于具有n个结点的完全二叉树，如果按照从上至下从左至右的顺序对所有节点从0开始编号，则对于序号为i的结点有：
若i>0，双亲序号：(i-1)/2；i=0，i为根结点编号，无双亲结点
若2i+1<n，左孩子序号：2i+1，否则无左孩子
若2i+2<n，右孩子序号：2i+2，否则无右孩子
三丶遍历二叉树
构造一个二叉树
构造一个二叉树我们一般都是使用递归来进行构造，但是在这里呢，我们就自己构造了。（实际上树都是递归构造的 ）
给出代码：
public class BinaryTree<E>{
public static class BTNode{
BTNode left;
BTNode right;
int data;
public BTNode(int data){
this.data = data;
}
}
BTNode root;//构造根节点
public void creatBinaryTree(){
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;
}
public static void main(String[] args) {
BinaryTree bT = new BinaryTree();
bT.creatBinaryTree();
}
}
遍历二叉树
所谓遍历(Traversal)是指沿着某条搜索路线，依次对树中每个结点均做一次且仅做一次访问。那么肯定是要有顺序的，不然还不乱了套了。
前序遍历
所谓前序遍历，就是把根节点的访问次序放在前面。也就是：
根节点 >>> 左子树 >>> 右子树
像我们构造的二叉树
前序遍历结果就是：1 2 3 4 5 6
具体代码如下：
//前序遍历
public void preOrder(BTNode root){
if(root == null){
return;
}
System.out.print(root.data + " ");
preOrder(root.left);
preOrder(root.right);
}
public void preOrder(){
System.out.println("前序遍历:");
preOrder(root);
}
运行结果如下：
中序遍历
对于中序遍历，实际上就是把根节点的访问次序放在中间。
左子树 >>> 根节点 >>> 右子树
对于我们的这个二叉树来说，中序遍历结果就是：3 2 1 5 4 6
具体代码如下：
//中序遍历
public void inOrder(BTNode root){
if(root == null){
return;
}
inOrder(root.left);
System.out.println(root.data + " ");
inOrder(root.right);
}
public void inOrder(){
System.out.println("中序遍历:");
inOrder(root);
}
运行结果如下：
后序遍历
对于后序遍历，其实就是把根节点的访问次序放在了最后。
左子树 >>> 右子树 >>> 根节点
如图：
它的后序遍历就是：3 2 5 6 4 1
具体代码如下;
//后序遍历
public void postOrder(BTNode root){
if(root == null){
return;
}
inOrder(root.left);
inOrder(root.right);
System.out.print(root.data + " ");
}
public void postOrder(){
System.out.println("后序遍历：");
postOrder(root);
}
运行结果如下：
层序遍历
什么是层序遍历呢？
就是把每一层从左往右进行遍历。
比如我们构造的这个二叉树，遍历结果就是：1 2 4 3 5 6
方法一
在这里直接给出代码，因为这种方法其实就是结合后面关于二叉树的基本操作实现的。
//层序遍历
public void levelOrder(BTNode root){
//先知道这个二叉树有几层，这里的getHeight()方法看后面的基本操作
int a = getHeight(root);
int i = 1;
//然后遍历每一层
while(i <= a){
getKLevelNode(root,i);
i++;
}
}
public void getKLevelNode(BTNode root,int k){
if(root == null || k <= 0){
return;
}//先排除异常
if(k != 1){
getKLevelNode(root.left,k - 1);
getKLevelNode(root.right,k - 1);
}else{
System.out.print(root.data + " ");
}
}
虽然这种方法好理解，但是取巧了。
方法二
第二种方法就是用队列来进行遍历。
//层序遍历第二种，为了区分，所以不传参数
public void levelOrder(){
if(root == null){
return;
}
//遍历前的准备工作
Queue<BTNode> queue = new LinkedList();
queue.offer(root);
//队列不为空便利完成，每次只对队列头元素进行操作
while(!queue.isEmpty()){
if(queue.peek().left != null){
queue.offer(queue.peek().left);
}
if(queue.peek().right != null){
queue.offer(queue.peek().right);
}
System.out.print(queue.poll().data + " ");
}
}
四丶关于二叉树的基本操作
这一部分呢是重写部分二叉树的方法。所有代码都是在前面的基础上进行书写，所用二叉树也是前面构造的二叉树。
获取树中结点的个数
获取节点个数其实就是遍历整个二叉树。
代码如下：
public int size(BTNode root){
if(root == null){
return 0;
}
return size(root.left) + size(root.right) + 1;
}
public int size(){
return size(root);
}
最后可以得到结果是：6
获得叶子结点的个数
在遍历二叉树的基础上加了一个判断：如果左右子树为null那么就加1
//求叶子结点
public int getLeafNodeCount(BTNode root){
if(root == null){
return 0;
}
if(root.left == null && root.right == null){
return 1;
}
return getLeafNodeCount(root.left) + getLeafNodeCount(root.right);
}
public int getLeafNodeCount(){
return getLeafNodeCount(root);
}
最后得到结果：3
获取第K层节点个数
就是在遍历树中节点的同时给它加一个计数器进行控制。
//求第k层结点个数
public int getKLevelNodeCount(BTNode root,int k){
if(root == null || k <= 0){
return 0;
}//先排除异常
if(k == 1){
return 1;
}
return getKLevelNodeCount(root.left,k - 1)+getKLevelNodeCount(root.right,k - 1);
}
public int getKLevelNodeCount(int k){
return getKLevelNodeCount(root,k);
}
最后运行结果是：3
获取二叉树的高度
在遍历中对返回值加以控制，只返回高的那个子树。
代码如下：
//求树的高度
public int getHeight(BTNode root){
if(root == null){
return 0;
}
return getHeight(root.left) > getHeight(root.right) ? 1 + getHeight(root.left) : 1 + getHeight(root.right);
}
public int getHeight(){
return getHeight(root);
}
运行结果为：3
检测值为value的元素是否存在
这个没啥好说的了，就是在遍历中加入一个判断语句。
代码如下：
//判断值为value的节点是否存在
public BTNode find(BTNode root, int val) {
if(root == null){
return null;
}
if(root.data == val){
return root;
}
return find(root.right, val) != null ? find(root.right,val):find(root.left,val);
}
public BTNode find(int val) {
return find(root,val);
}
五丶总结
这两天事情太多了，所以耽搁了好多事情，赶紧补赶紧补。