一、树的相关概念
1.1 树的定义
定义：树是由n（n>=0）个结点组成的有限集合（记为T）。其中
如果n=0，它是一颗空树，这是树的特例；
如果n>0，这n个结点中存在（有且仅有）一个结点作为树的根结点，简称根（root），其余结点可分为m（m>=0）个互不相交的有限集T1，T2，…,Tm，其中每一颗子集本身又是一颗符合本定义的树，称为根的子树。
1.2 树的相关术语
1.根：指在树中没有前驱的结点称之为根节点（如A结点）。
2.叶子：即终端结点，没有后继的结点称之为叶子结点（如G、H、I、J、F）。
3.森林：是（n>=0）棵树的集合。多棵树是森林，一棵树也是森林;删去一棵非空树的根结点，树就变成森林（当然也有可能是空的森林)这个角度来说要是删除一棵树可不能前序遍历！变成森林就不好办了！
4.结点(node)：由数据元素和构造数据元素之间关系的指针组成。大白话就是有数据和联系其他结点的指针结点的度:结点所拥有的子树的个数（例如上图中结点D的度为3.）
孩子结点(child) ：该结点的子树的根结点是该结点的孩子，例如上图中B是A的孩子，同时B又有1个孩子。
5.父节点(parent) ：若该结点有孩子，则该结点为他的孩子结点的父节点（C是E和F的父亲）。
6.树的深度(depth) :树中距离根结点最远的点所处的层次数就是树的深度，空树的深度为O，只有根结点的深度为1，上图中树(c)的深度为3.
7.树的高度(height) ：深度是从上往下算，高度是从下往上算，从叶节点开始算，但是高度等于深度。
8.结点所在层次(level) ：从根结点到该结点所经路径上的分支条数，根结点为第一层，其他结点就是沿着从根结点到这个结点的这条路径上的分支结点数。
9.兄弟结点(sibling)：同一父节点的孩子互称为兄弟。
10.孩子结点(child) ：该结点的子树的根结点是该结点的孩子，例如上图中D是B的孩子，同时D又有3个孩子。
11.祖先结点 (ancester) ：从根结点到该结点所经分支的所有结点，例如上图中结点G的祖先为A，B，D.
12.子孙结点(descendant) :该结点的孩子和孩子的孩子都是该结点的子孙，例如B的子孙为D，G，H，I.
二、二叉树
2.1 二叉树的相关概念
定义：一棵二叉树是结点的一个有限集合，该集合 :由一个根节点加上两棵别称为左子树和右子树的二叉树组成（左子树或右子树都可以为空，根节点也可能为空）
特点：结点的度小于等于2
2.2 二叉树的分类
1. 满二叉树 ：大白话就是满的二叉树，没有空节点，一棵深度为k 且有2^k -1个结点的二叉树。（特点：每层都“充满”了结点），即叶子一个也不少的树。满二叉树是完全二叉树的一个特例。如下图
2. 完全二叉树：大白话就是满二叉树的最后一层的右边可以缺一块。：深度为k 的，有n个结点的二叉树，当且仅当其每一个结点都与深度为k 的满二叉树中编号从1至n的结点一一对应。简而言之，完全二叉树虽然前n-1层是满的，但最底层却允许在右边缺少连续若干个结点。同时满二叉树也是一种特殊的完全二叉树。
2.3 二叉树的性质
1. 若规定根节点的层数为 1 ，则一棵非空二叉树的 第 i 层上最多有 2^(i-1)个结点(这层排满).
2. 若规定根节点的层数为 1 ，则深度为n的二叉树的最大结点数是2^n -1(满二叉树).
3. 对任何一棵二叉 树 , 如果度为 0 其叶结点个数为n0 , 度为 2 的分支结点个数为n2 , 则有
n0 ＝n2 ＋ 1.
4. 若规定根节点的层数为 1 ，具有 n 个结点的满二叉树的深度 ，h= log2(n+1).(log2(n+1)表示log以2为底数，n+1为对数)。
5.对于具有 n 个结点的完全二叉树，如果按照从上至下从左至右的数组顺序对所有节点从 0开始编号，则对于序号为 i 的结点有：
a. 若i > 0， i 位置节点的双亲序号： (i-1)/2 ； i=0 ， i 为根节点编号，无双亲节点
b. 若 2i+1<n ，左孩子序号： 2i+1 ， 2i+1>=n 否则无左孩子
c. 若 2i+2<n ，右孩子序号： 2i+2 ， 2i+2>=n 否则无右孩子
2.4 二叉树的存储结构
2.4.1 顺序存储
顺序结构存储就是使用数组来存储，一般使用数组只适合表示完全二叉树，因为不是完全二叉树会有空间的浪费。而现实中使用中只有堆才会使用数组来存储，二叉树顺序存储在物理上是一个数组，在逻辑上是一颗二叉树。对于一般的二叉树：通过“补虚结点”，将一般的二叉树变成完全二叉树。
如果用顺序存储一般的二叉树，就会有浪费。
2.4.2 链式存储
如同二叉树定义一般，有一个数据域，有一个左的引用，有一个右的引用。
三、代码构建二叉树
3.1 创建二叉树
就是简单的创造结点，然后串上。
public void createTree(){ TreeNode A = new TreeNode('A'); TreeNode B = new TreeNode('B'); TreeNode C = new TreeNode('C'); TreeNode D = new TreeNode('D'); TreeNode E = new TreeNode('E'); TreeNode F = new TreeNode('F'); TreeNode G = new TreeNode('G'); TreeNode H = new TreeNode('H'); A.left = B; A.right = C; B.left = D; B.right = E; C.left = F; C.right = G; E.right = H; this.root = A; }
3.2 二叉树的先序遍历
遍历方式：
1：如果为空，则进行空操作
2：如果不为空，先访问根，然后左树，然后右树（根左右）
//先序遍历递归 public void preOrder(TreeNode root){ if(root == null){ return; } System.out.print(root.val+" "); preOrder(root.left); preOrder(root.right); } //非递归 public void preOrder2(TreeNode root){ if(root == null){ return; } Deque<TreeNode> stack = new ArrayDeque<>(); TreeNode cur = root; while(!stack.isEmpty() || cur != null){ while (cur != null){ stack.push(cur); System.out.print(cur.val+" "); cur = cur.left; } cur = stack.pop(); cur = cur.right; } }
如果是非递归的话，需要一个栈（是因为需要回溯，如果你看懂上面的递归版本，和递归的回溯一样子捏），如果访问根节点，根节点不为空，就继续访问根的左树，重复上述操作，直到左树为空，就需要回溯了，从栈顶弹出一个节点，然后去访问右树。
3.3 二叉树的中序遍历
遍历方式：
1：如果访问的根为空，则进行空操作
2：如果不为空，先访问左树，然后根，然后右树（左根右）
跟上面一样的，无论是递归还是非递归
//中序遍历 public void inOrder(TreeNode root){ if(root == null){ return; } inOrder(root.left); System.out.print(root.val+" "); inOrder(root.right); } //非递归 public void inOrder2(TreeNode root){ if(root == null){ return; } TreeNode cur = root; Deque<TreeNode> stack = new ArrayDeque<>(); while (cur != null || !stack.isEmpty()){ while(cur != null){ stack.push(cur); cur = cur.left; } cur = stack.pop(); System.out.print(cur.val+" "); cur = cur.right; } }
3.4 二叉树的后序遍历
遍历方式：
1：如果访问的根为空，则进行空操作
2：如果不为空，先访问左树，然后右树，然后根（左右根）
后序遍历的递归和上面的思路一样，但是非递归的话要注意一个地方，如果一直访问左树然后开始回溯，然后从栈顶弹出一个结点（这个是peek，这个结点还是存在在栈中的，因为不知道还存不存在右树），如果不存在右树，则遍历然后弹出。如果存在右树，访问右树（不弹出），注意如果弹出要标记一下，如果不标记回退到根结点又要判断右树情况就存在死循环！！
//后序遍历 public void postOrder(TreeNode root){ if(root == null){ return; } postOrder(root.left); postOrder(root.right); System.out.print(root.val+" "); } //非递归 public void postOrder2(TreeNode root){ if(root == null){ return; } TreeNode cur = root; TreeNode pre = null; Deque<TreeNode> stack = new ArrayDeque<>(); while(cur != null || !stack.isEmpty()){ while (cur != null){ stack.push(cur); cur = cur.left; } TreeNode top = stack.peek(); if(top.right == null || top.right == pre){ System.out.print(top.val+" "); stack.pop(); pre = top; }else { cur = top.right; } } }
3.5 计算二叉树节点个数
大致分为两个思路：
1：遍历整棵树，遇到一个结点i就++
2：分别计算左树的节点个数和右树的节点个数
注：第一个思路只能调用一次，调用两次的话就相当于计算了两次结点个数
第二个思路大概就是下图的递归
//思路二 public int size2(TreeNode root){ if(root == null){ return 0; } int countLeft = size2(root.left); int countRight = size2(root.right); return countLeft + countRight + 1; } public static int nodeSize;//只能调用一次size方法 /** * 获取树中节点的个数：遍历思路 思路1 */ public void size(TreeNode root) { if(root == null){ return; } nodeSize++; size(root.left); size(root.right); }
3.6 计算二叉树叶子节点个数
判断是叶子的方法就是没有左右孩子。
方法一：遇见一个叶子节点leafsize就加一（也只能调用一次）。
方法二：计算左树的叶子个数和右树的叶子个数然后加起来返回。
public static int leafSize = 0; public void getLeafNodeCount1(TreeNode root) { if(root == null){ return; } if(root.left == null && root.right == null){ leafSize++; } getLeafNodeCount1(root.left); getLeafNodeCount1(root.right); }
public int getLeafNodeCount2(TreeNode root) { if(root == null){ return 0; } if(root.right == null && root.left == null){ return 1; } int countLeft = getLeafNodeCount2(root.left); int countRight = getLeafNodeCount2(root.right); return countLeft + countRight; }
3.7 获取第K层节点的个数
也是子问题，分别计算k层左树节点个数与右树节点个数，往下递归一层k就减1，等k为1就是第k层的一个节点返回1即可。
public int getKLevelNodeCount(TreeNode root, int k) { if (root == null){ return 0; } if(k == 1){ return 1; } int countLeft = getKLevelNodeCount(root.left,k-1); int countRight = getKLevelNodeCount(root.right,k-1); return countLeft+countRight; }
3.8 获取二叉树的高度
分别计算左树高度和右树高度，然后取最高值。
public int getHeight(TreeNode root) { if(root == null){ return 0; } int countLeft = getHeight(root.left); int countRight = getHeight(root.right); return (countLeft > countRight) ? (countLeft+1) : (countRight+1); }
3.9 检测值为value的元素是否存在
就是遍历树，然后对比val
public TreeNode find(TreeNode root, char val) { if (root == null){ return null; } if(root.val == val){ return root; } TreeNode leftNode = find(root.left,val); if(leftNode != null){ return leftNode; } TreeNode rightNode = find(root.right,val); if (rightNode != null){ return rightNode; } return null; }
3.10 判断是否是相同的树
public boolean isSameTree(TreeNode p, TreeNode q) { if(p == null && q == null){ return true; } if((p == null && q != null) || (p != null && q == null)){ return false; } if(p.val != q.val){ return false; } return isSameTree(p.right,q.right) && isSameTree(q.left,p.left); }
3.11 判断是否是平衡树
定义：一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。
注：是每个节点都要判断
public boolean isBalanced(TreeNode root) { return getDepth(root) >= 0; } public int getDepth(TreeNode root) { if(root == null){ return 0; } int countLeft = getDepth(root.left);//计算左树节点深度 if(countLeft < 0) return -1;//如果为负说明不需要接着判断了，一直返回负一，节约时间复杂度 int countRight = getDepth(root.right);//同理 if(countRight < 0) return -1; if(Math.abs(countLeft - countRight) <= 1){ return Math.max(countLeft,countRight) + 1; }else{ return -1; } }
3.12 层序遍历
实现层序遍历，我们需要使用队列，思路是先把根节点如队，然后出队打印，然后再将根节点的如下图A的左孩子B入队，右孩子C入队。然后B出队打印B然后将D和E分别入队，直到队列为空。
public void levelOrder(TreeNode root) { if(root == null){ return; } 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); } } }
3.13 判断一棵树是不是完全二叉树
这个是借用了层次遍历的思想，如果层次遍历遇见了空那说明，如果这个树为满二叉树那说明这个结点是最后一个，那说明这个队列后面无元素也就是队列为空
public boolean isCompleteTree(TreeNode root) { if(root == null){ return true; } Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); while(!queue.isEmpty()){ TreeNode node = queue.poll(); if(node != null){ queue.offer(node.left); queue.offer(node.right); } else { break; } } while(!queue.isEmpty()){ TreeNode node = queue.poll(); if(node != null){ return false; } } return true; }
