目录
树的定义
树是一种非线性的数据结构，它是由n（n>=0）个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。
树的特点
- 有一个特殊的结点，称为根结点，根结点没有前驱结点(通常叫它root节点)
- 除根结点外，其余结点被分成M(M > 0)个互不相交的集合T1、T2、......、Tm，其中每一个集合 Ti (1 <= i<= m) 又是一棵与树类似的子树。每棵子树的根结点有且只有一个前驱，可以有0个或多个后继。(根节点：唯一，有且仅有一个根节点，中间结点：一个双亲可以有多个孩子节点，叶子结点:叶子结点度为0，无孩子可以有多个)。
- 由于一棵树又可以划分为多个子树，所以二叉树的操作大部分都是由递归来实现的
- 对于节点数为n，n>0时根节点是唯一的，有且仅有一个
- 一棵树可以有多个节点，但是节点之间是不能相交的
树的结点分类
结点的度：一个结点含有子树的个数称为该结点的度；对于1节点它的度就是2,1节点共有两个子树
树的度：一棵树中，所有结点度的最大值称为树的度； 这颗树，一个结点最多子树为2个，所以树的度为2
叶子结点或终端结点：度为0的结点称为叶结点； 叶子结点在树的最后没有子树的节点，例如6,7,8,9,10节点.
双亲结点或父结点：若一个结点含有子结点这个结点称为其子结点的父结点;比如2的父亲就是1
孩子结点或子结点：一个结点含有的子树的根结点称为该结点的子结点； 对于2节点来说它的父亲是1，对于1节点来说它的孩子是2和3节点
根结点：一棵树中，没有双亲结点的结点；一般来说除了空树外，其他树有且仅有一个根节点root
结点的层次：从根开始定义起，根为第1层，根的子结点为第2层，以此类推
树的深度：相对于节点来说的，比如1节点深度为1。?2,3节点深度为2。4,5,6,7节点深度为3
树的高度：树中结点的最大层次；树的最大深度就是这一颗树的高度
树的祖先：从根到该结点所经分支上的所有结点，对于8节点来说，1,2,4节点都是8的公共祖先。
二叉树
二叉树的特点
- 对于二叉树的每一个节点来说，它的度也就是子树的个数都是小于等于2的
- 二叉树有左右子树区分。一定要区分它的左树和右树。
二叉树的五种形态
- 空树（没有结点的树）
- 只有左树没有右树
- 只有右树没有左树
- 既有左树又有右树
- 只有一个根节点
三种特殊的二叉树
- 斜树：所有树只有左子树的树或者只有右子树的树叫做斜树，只有左子树的树叫做左斜树，只有右子树的树叫做右斜树
- 满二叉树：?一棵二叉树，如果每层的结点数都达到最大值，则这棵二叉树就是满二叉树。也就是说，如果一棵二叉树的层数为K，且结点总数是 ，则它就是满二叉树
- ?完全二叉树：完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从0至n-1的结点一一对应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。完全二叉树从左往右开始编号，如果不为空是一颗完全二叉树，完全二叉树可以有度为1的情况，如果从左往右开始编号为空，那就证明不是一颗完全二叉树
?二叉树的性质(非常重要)
- 若规定根结点的层数为1，则一棵非空二叉树的第i层上最多有 2^i-1(i>0)个结点
- ?若规定只有根结点的二叉树的深度为1，则深度为K的二叉树的最大结点数是2^k-1 (k>=0)
- ?对任何一棵二叉树, 如果其叶结点个数为 n0, 度为2的非叶结点个数为 n2,则有n0＝n2＋1
- ?具有n个结点的完全二叉树的深度k为 log2(n+1)上取整
- ?. 对于具有n个结点的完全二叉树，如果按照从上至下从左至右的顺序对所有节点从0开始编号，则对于序号为i的结点有：
若i>0，双亲序号：(i-1)/2；i=0，i为根结点编号，无双亲结点
若2i+1<n，左孩子序号：2i+1，否则无左孩子
若2i+2<n，右孩子序号：2i+2，否则无右孩子
给定子节点下标求父节点下标：(i-1)/2
给定父节点下标求子节点下标：左孩子2i+1 右孩子：2i+2
这个结论在堆的学习经常会用到所以务必要记住
一些习题：
?
?二叉树的存储
我们在平时刷题时和平常学的一些二叉树基础都是利用链式存储，也就是说一个节点有节点值和它的左孩子和右孩子。
public class TreeNode {
int val; // 数据域
TreeNode left; // 左孩子的引用，常常代表左孩子为根的整棵左子树
TreeNode right; // 右孩子的引用，常常代表右孩子为根的整棵右子树
}二叉树的基本操作
首先我们创建一颗二叉树
static class TreeNode{
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int val){
this.val = val;
}
}
//根节点
public TreeNode root;
public TreeNode createTree(){
TreeNode node1 = new TreeNode(1);
TreeNode node2 = new TreeNode(2);
TreeNode node3 = new TreeNode(3);
TreeNode node4 = new TreeNode(4);
TreeNode node5 = new TreeNode(5);
TreeNode node6 = new TreeNode(6);
TreeNode node7 = new TreeNode(7);
node1.left = node2;
node1.right = node4;
node2.left = node3;
node2.right = node7;
node4.left = node5;
node4.right= node6;
root =node1;
return root;
}二叉树的遍历
二叉树的前序遍历
二叉树的前序遍历：先访问根在访问左子树在访问右子树? 根-左子树-右子树
?对于这样一颗二叉树它的先序遍历时 A - B - D - E -H - C - F - G
?我们仔细分析一下这个前序遍历：
对于A这棵树来说要先访问根也就是A,然后去访问A的左子树，而A的左子树又是一棵树,先访问根B,在访问B这棵树的左子树D,对于D这棵树而言又是一棵树，所以先访问根D,再去访问它的左子树，发现D的左子树为null,再去访问D的右子树为null,所以D这棵树访问完了，也证明B的左树访问完了，然后接着访问B的右树E，而E又是一棵树，先访问根节点E,在去访问它的左子树，发现它的左子树为null,再去访问它的右子树H,所以E这棵树访问完了，也说明B的右树访问完了，也说明A的左树访问完了，然后再去访问A的右树C，而C又是一棵树，先访问根C,在去访问她的左树F,而F又是一棵树，访问它的左树为空，右树为空，F这棵树访问完了，所以C的左树访问完，同理再去访问G,好最后返回到A证明A这棵树走完了，这才是真正的结束一个二叉树的前序遍历。
根据我上面的分析，每一个树的逻辑都是一样的，都是先访问根节点，在访问左子树，在访问右子树，在访问左子树或者右子树，又是同样的道理，所以每一棵树可以用相同的操作，在使用递归操作重复调用，最终这棵树就遍历完成。
代码实现：
- 前序遍历-->递归版本无list
// 前序遍历-->递归版本无list
void preOrder(TreeNode root){
if(root==null) return;
System.out.print(root.val+" ");
preOrder(root.left);
preOrder(root.right);
}- 使用list遍历思路去存储-->前序遍历
//使用list遍历思路去存储-->前序遍历
List<Integer> list = new ArrayList<>();
public List<Integer> preorderTraversal(TreeNode root) {
if(root==null) return list;
list.add(root.val);
preorderTraversal(root.left);
preorderTraversal(root.right);
return list;
}-
使用list子问题思路进行前序遍历
//使用list子问题思路进行前序遍历
public List<Integer> preorderTraversal1(TreeNode root) {
List<Integer> list = new ArrayList<>();
if(root==null) return list;
list.add(root.val);
List<Integer> leftTree = preorderTraversal(root.left);
if(leftTree!=null){
list.addAll(leftTree);
}
List<Integer> rightTree = preorderTraversal(root.right);
if(rightTree!=null){
list.addAll(rightTree);
}
return list;
}-
前序遍历-->非递归版本
//前序遍历-->非递归版本
public List<Integer> preorderTraversal2(TreeNode root) {
List<Integer> ret = new ArrayList<>();
if(root==null) return ret;
Stack<TreeNode> stack = new Stack<>();
TreeNode cur = root;
while(cur!=null||(!stack.isEmpty())){
while(cur!=null){
stack.push(cur);
ret.add(cur.val);
cur = cur.left;
}
TreeNode top = stack.pop();
if(top.right!=null){
cur = top.right;
}
}
return ret;
}二叉树的中序遍历
根据二叉树的前序遍历，中序遍历也是一样的道理，中序遍历是先访问左子树在访问根节点在访问右子树。
对于上面那棵树而言中序遍历为：D - B - E - H - A - F - C - G
代码实现：
// 中序遍历
void inOrder(TreeNode root){
if(root==null) return;
inOrder(root.left);
System.out.print(root.val+" ");
inOrder(root.right);
}- 使用list-->子问题进行中序遍历
//使用list-->子问题进行中序遍历
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> ret = new ArrayList<>();
if(root==null) return ret;
List<Integer> leftTree = inorderTraversal(root.left);
if(leftTree!=null){
ret.addAll(leftTree);
}
ret.add(root.val);
List<Integer> rightTree = inorderTraversal(root.right);
if(rightTree!=null){
ret.addAll(rightTree);
}
return ret;
}- 使用list进行非递归实现--->中序遍历
//使用list进行非递归实现--->中序遍历
public List<Integer> inorderTraversalNor(TreeNode root) {
List<Integer> ret = new ArrayList<>();
if(root==null) return ret;
Stack<TreeNode> stack = new Stack<>();
TreeNode cur = root;
while(cur!=null||!stack.isEmpty()){
while (cur != null) {
stack.push(cur);
cur = cur.left;
}
TreeNode top = stack.pop();
ret.add(top.val);
if (top.right != null) {
cur = top.right;
}
}
return ret;
}二叉树的后序遍历
根据二叉树的前序遍历，中序遍历，后序遍历也是一样的道理，后序遍历是先访问左子树在访问右子树在访问根节点。
对于上面那棵树而言后序遍历为：D - H - E - B - F - G - C - A
代码实现：
// 后序遍历
void postOrder(TreeNode root){
if(root==null) return;
postOrder(root.left);
postOrder(root.right);
System.out.print(root.val+" ");
}- 使用非递归来实现二叉树的后序遍历
//使用非递归来实现二叉树的后序遍历
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> ret = new ArrayList<>();
if(root==null) return ret;
Stack<TreeNode> stack = new Stack<>();
TreeNode cur = root;
TreeNode prev = null;
while(cur!=null||(!stack.isEmpty())){
while(cur!=null){
stack.push(cur);
cur = cur.left;
}
TreeNode top = stack.peek();
if(top.right==null||top.right==prev){
stack.pop();
ret.add(top.val);
prev = top;
}else {
cur = top.right;
}
}
return ret;
}- 最终我们还可以得出一个结论要想有想构建一颗二叉树，要么给出二叉树的递归序(也就是包括null节点也给出)，否则要想得到一颗二叉树，必须知道中序遍历，要么前序遍历和中序遍历，要么后序遍历和中序遍历，如果没有中序遍历，就只能根据前序或者后序确定根节点，不能确定左子树和右子树。
获取树中节点的个数
对于获取节点个数：普通遍历思路，就是遍历二叉树中的每一个节点然后计数器++，可以使用前序中序后序都可以。
这里的代码实现给出的是子问题的思路，我们可以思考一下，对于一颗二叉树来说，就是根节点，左子树和右子树，那一颗二叉树节点的个数是不是等于左子树节点的个数+右子树节点的个数+根节点本身(也就是+1)。
int size(TreeNode root){
if(root==null) return 0;
int left = size(root.left);//算出左子树的节点个数
int right = size(root.right);//算出右子树的节点个数
return left+right+1;
}获取叶子节点的个数
遍历思路：叶子结点前面我也讲过就是度为0的节点，也就是当我们遍历树的左子树为空并且它的右子树为空，那他就是我们的叶子结点使用计数器++就可以。
子问题思路：这里我给出的也是子问题思路，一颗二叉树我们只要求出它的左子树叶子结点个数+右子树叶子结点个数就是我们这棵二叉树的叶子结点个数了。
int getLeafNodeCount(TreeNode root){
if(root==null) return 0;
if(root.left==null&&root.right==null){
return 1;
}
int left = getLeafNodeCount(root.left);
int right = getLeafNodeCount(root.right);
return left+right;
}获取第K层节点的个数
对于一颗二叉树，我们要求第3层结点个数，那相对于根节点我们是不是求它的第二层结点。而相对于第二层结点来说我们是不是在求它的第一层结点，对于第三层，我们是求它的第0层。
号也就是说，如果我们求第k层结点的个数我们就求相对于每一层的k-1层结点，当k=1时候也就是求它本身结点个数1.
int getKLevelNodeCount(TreeNode root,int k){
if(root==null) return 0;
if(k==1) return 1;
int left = getKLevelNodeCount(root.left,k-1);
int right = getKLevelNodeCount(root.right,k-1);
return left + right;
}获取二叉树的高度
对于一颗二叉树来说，树的高度就是这颗二叉树最大深度，我们只要求出左子树和右子树高度的最大值在+1就是这棵二叉树的高度。
int getHeight(TreeNode root){
if(root==null) return 0;
int left = getHeight(root.left);
int right = getHeight(root.right);
return left>right?left+1:right+1;
}检测值为value的元素是否存在
还是一样的，对于一颗二叉树我们要判断value是否在这颗二叉树中存在，我们首先会先去根节点看一看是不是这个value,如果不是value，再去左子树看一看有没有，再去看一看右子树有没有，如果在一棵树中找到value立马把这个值返回来。
TreeNode find(TreeNode root, int val){
if(root==null) return null;
if(root.val==val) return root;
TreeNode leftTree = find(root.left,val);
if(leftTree!=null){
return leftTree;
}
TreeNode rightTree = find(root.right,val);
if(rightTree!=null){
return rightTree;
}
return null;
}层序遍历
层序遍历我们利用一个辅助栈来实现。
- 先将根节点压入栈中
- 每一次将栈顶元素弹出并打印，在弹出元素时要将弹出元素利用一个临时遍历存起来，然后同时将它的左子树和右子树一并压入栈中，如果为null我们就不压入栈中，反复进行最终就是层序遍历
void levelOrder(TreeNode root){
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while(!queue.isEmpty()){
TreeNode cur = queue.poll();
System.out.print(cur.val+" ");
if(cur.left!=null){
queue.offer(cur.left);
}
if(cur.right!=null){
queue.offer(cur.right);
}
}
}判断一棵树是不是完全二叉树
根据层序遍历思想
- 先将根节点压入栈中
- 每一次将栈顶元素弹出并打印，在弹出元素时要将弹出元素利用一个临时遍历存起来，然后同时将它的左子树和右子树一并压入栈中，此时与层序遍历不同的是如果树为null，我们依然要压入栈中
- 最后我们将这棵树遍历完之后，栈中还有元素，如果栈中元素全为null,就说明这是一颗完全二叉树，否则不是。
- 这也依据完全二叉树的定义，如果从左往右开始编号，有一个子树漏掉了并且它的右边还有子树那就不是一颗完全二叉树
boolean isCompleteTree(TreeNode root){
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while(!queue.isEmpty()){
TreeNode cur = queue.poll();
if(cur==null){
break;
}
queue.offer(cur.left);
queue.offer(cur.right);
}
while(!queue.isEmpty()){
TreeNode tmp =queue.peek();
if(tmp!=null){
return false;
}
queue.poll();
}
return true;
}