1. 树形结构
1.1 树的概念
树是一种非线性的数据结构，它是由n个(n>=0)个有限节点组成一个具有层次关系的集合。它的形状像一颗倒挂的树，根在上，叶在下。
特点：
· 有一个特殊的结点称为根节点，根节点没有前驱结点
· 除根节点外，其余结点被分成M(M>0)个互不相交的集合T1,T2,.....,Tm，其中每一个集合又是一颗与树类似的字树。每棵子树的根节点有且只有一个前驱，可以没有或者多个后继
· 树是递归定义的
注意：在树形结构中，子树不能有交集，否则就不是树形结构
重要概念：
结点的度：一个结点含有子树的个数
树的度：所有结点的度的最大值称为树的度
叶子结点或终端结点：度为0的结点
双亲结点或父亲结点：若一个结点含有子节点，则这个结点为其子结点的双亲结点
孩子结点或子结点：一个结点含有的子树的根结点称为该结点的子结点
根结点：树中没有双亲结点的结点
结点的层次：从根开始定义，根为第一层，根的子结点为第二层，以此类推
树的高度或深度：树中结点层次的最大值
森林：由m(m>0)棵互不相交的树组成的集合称为森林
1.2 树的表示形式（简单了解）
树的结构相对于线性表比较复杂，要存储起来也比较麻烦，这里有几种表示方法：双亲表示法，孩子表示法，孩子双亲表示法，孩子兄弟表示法等，这里只简单了解最常用的孩子兄弟表示法。
class Node{ int val; //存储的数据 Node firstChild; // 第一个孩子引用,一般称之为左结点，Node left Node nextBrother; //下一个兄弟引用,一般称之为右结点，Node right }
2. 二叉树（重点）
2.1 概念
一颗二叉树是结点的一个有限集合，该集合：
1. 为空
2. 由一个结点加上两颗别称为左子树和右子树的二叉树组成
从图中可以看出：
1. 二叉树不存在度大于2的结点
2. 二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树
注意：对于任意的二叉树都是由以下几种情况复合而成的：
这里展示一张照片---大自然的奇观：现实中的二叉树
2.2 两种特殊的二叉树
1. 满二叉树：一颗二叉树，如果每层的节点数都达到最大值，则这棵二叉树就是满二叉树
2.完全二叉树：它是一种效率很高的数据结构，完全二叉树是由满二叉树引出来的。对于深度为k，有n个结点的二叉树，当且仅当每一个结点都与深度为k的满二叉树中编号从0至n-1的结点一一对应时称之为完全二叉树，满二叉树是一种特殊的完全二叉树
2.3 二叉树的性质（重点，选择题常考）
1. 规定根结点的层数是1，则一颗非空二叉树的第i层上最多2^(i-1)个结点
2. 规定只有根结点的二叉树深度为1，则深度为k的二叉树的最大结点数是2^k - 1
3. 对于任何一颗二叉树，如果其叶结点个数为n0，度为2的结点个数为n2，则n0=n2+1
4. 具有n个结点的二叉树的深度为log2(n+1)向上 取整 ，
5. 对于有n个结点的完全二叉树，如果按照从左至右，从上往下的顺序对所有结点从0开始编号，则对于序号为i的结点有：
· 若i>0，双亲序号：2i+1；i=0，i为根节点编号，无双亲结点
· 若2i+1
· 若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 MyTreeBlog { public class BTNode{ int val; BTNode left; BTNode right; public BTNode(int val){ this.val = val; } } private 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); root = node1; node1.left = node2; node1.right = node4; node2.left = node3; node4.left = node5; node4.right = node6; } }
注意：上述代码不是创建二叉树的方式，创建二叉树后面会介绍
2.5.2 二叉树的遍历
1. 前中后序遍历
遍历就是指沿着某条搜索路线，依次对树中每个结点均做一次且仅做一次访问，访问结点所做的操作依赖于具体的应用问题（比如：打印结点内容），遍历是二叉树最重要的操作之一，是二叉树上进行其他运算的基础。
N代表根结点，L代表根结点的左子树，R代表根节点的右子树，则根据遍历根节点的先后次序有以下几种遍历方式：
NLR：前序遍历：根节点---根的左子树---根的右子树
LNR：中序遍历：根的左子树---根结点---根的右子树
LRN：后序遍历：根的左子树---根的右子树---根结点
前序遍历结果：1 2 3 4 5 6
中序遍历结果：3 2 1 5 4 6
后序遍历结果：3 2 5 6 4 1
2. 层序遍历
除了上述三种遍历，还可以对二叉树进行层序遍历。根节点所在的层数为第一层，自上到下，自左到右，逐层访问树的结点的过程就是层序遍历
2.5.3 二叉树基本操作的实现（重点）
1. 二叉树的前中后序遍历：采用递归的方式遍历
public void preOrder(BTNode root){ if(root!=null){ System.out.print(root.val+" ");//遍历根 preOrder(root.left); //递归遍历左子树 preOrder(root.right); //递归遍历右子树 } } public void inOrder(BTNode root){ if(root!=null){ inOrder(root.left); //递归遍历左子树 System.out.print(root.val+" ");//遍历根 inOrder(root.right); //递归遍历右子树 } } public void postOrder(BTNode root){ if(root!=null){ postOrder(root.left); //递归遍历左子树 postOrder(root.right); //递归遍历右子树 System.out.print(root.val+" ");//遍历根 } } 2. 二叉树的层序遍历：这里需要借助队列完成 public void levelOrder(BTNode root){ if(root==null){ return; //根为空直接返回 } Queue<BTNode> q = new LinkedList<>(); q.offer(root); //先将根入队列 while(!q.isEmpty()){ //队列不为空时，循环 BTNode cur = q.poll(); //根出队列 System.out.print(cur.val+" "); if(cur.left!=null){ //根有左子树，将左子树的根入队列 q.offer(cur.left); } if(cur.right!=null){ //根有右子树，将右子树的根入队列 q.offer(cur.right); } } System.out.println(); }
图解：图比较丑，但是能说明情况
3. 获取二叉树中结点的个数
二叉树结点的个数=根的左子树结点的个数+根的右子树结点的个数+1（这个1就是根），所以直接一个递归就解决问题了
public int size(BTNode root){ if(root==null){ return 0; } return 1+size(root.left)+size(root.right); }
4. 获取二叉树中叶子结点的个数
叶子结点就是该结点的左子树为空，右子树为空，所以当遇到此节点时返回1，递归返回所有该结点的总数
public int getLeafNode(BTNode root){ if(root==null){ return 0; } if(root.left == null && root.right == null){ return 1; } return getLeafNode(root.left)+getLeafNode(root.right); }
5. 获取二叉树中第k层结点的个数
public int getLevelNode(BTNode root,int k){ if(root==null||k<0){ //判断参数 return 0; } if(k==1){ //如果k==1，则只有根返回1 return 1; } //递归 return getLevelNode(root.left,k-1) + getLevelNode(root.right,k-1); }
6. 获取二叉树的高度
将此二叉树的左子树的高度与右子树的高度进行比较，较大的高度+1就是此二叉树的高度
public int height(BTNode root){ if(root==null){ return 0; } int leftHeight = height(root.left); int rightHeight = height(root.right); return (Math.max(leftHeight,rightHeight)+1); }
7. 查找值为val的结点并返回
先递归在左子树中找，再递归在右子树中找
public BTNode find(BTNode root,int val){ if(root==null){ return null; } if(root.val == val){ return root; } BTNode ret = find(root.left,val); //递归在左子树中找 if(ret!=null){ return ret; //找到了返回 } return find(root.right,val); //递归在右子树中找 }
8. 判断一棵树是否为完全二叉树（重点，常考）
当某个结点是叶子结点时，此结点必须没有左右子树，如果有则返回false；当某个结点是其父类左子树的根且该结点只有左子树时，该结点同一层的另一个结点必须没有子树，否则返回为false
第一种情况好理解，这里将第二种情况进行画图说明：
注意：当遇到上述两种情况时，必须得进行特殊检测
检测的方法：当满足上面两种情况时，待检测的结点有左子树或者右子树其中的一个子树则返回false（结合上图更容易理解）
public boolean isCompleteTree(BTNode root){ if(root==null){ return true; //空树也是完全二叉树 } Queue<BTNode> q = new LinkedList<>(); boolean flag = false; //给的标记，检测上述两种情况 q.offer(root); while(!q.isEmpty()){ BTNode cur = q.poll(); if(flag){ //如果遇到上述两种情况，则进行左右子树的检测 if(cur.left!=null||cur.right!=null){ return false; } }else{ if(cur.left!=null&&cur.right!=null){ q.offer(cur.left); q.offer(cur.right); } if(cur.left!=null){ q.offer(cur.left); flag = true; //对应上述的第二种情况 } if(cur.right!=null){ return false; } else{ flag = true; //对应上述的第一种情况 } } } return true; }
