1.创造二叉树
快速掌握叉树的基本操作，这里只创造一个简单的二叉树，而不是二叉树的真正创造方式；以后将解释二叉树的真正创造方法。
public class BinaryTree { public static class TreeNode { public char val; public TreeNode left; public TreeNode right; public TreeNode(char val) { this.val = val; } } //public TreeNode root; public TreeNode 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'); return A; } }在了解了二叉树的性质后，我们可以知道二叉树的定义是递归式的，所以
二、二叉树基操
2.一、二叉树遍历
二叉树的遍历分为三种：
-
NLR ：前序遍历（ 先序遍历 )—— 访问根结点 ---> 根的左子树 ---> 根的右子树。(根左右)
-
LNR ：中序遍历 —— 根的左子树 ---> 根节点 ---> 根的右子树。 （左根右）
-
LRN ：后序遍历 (Postorder Traversal)—— 根的左子树 ---> 根的右子树 ---> 根节点。(左右根)
前序遍历：
// 前序遍历 public void preOrder(TreeNode root) { if(root == null) return; System.out.println(root.val);//根 preOrder(root.left);//左 preOrder(root.right);//右 }中序遍历：
// 中序遍历 public void inOrder(TreeNode root) { if(root == null) return; inOrder(root.left);//左 System.out.println(root.val);//根 inOrder(root.right);//右 }后序遍历：
// 后序遍历 public void postOrder(TreeNode root) { if(root == null) return; postOrder(root.left);//左 postOrder(root.right);//右 System.out.println(root.val);//根 }分享两种思路(以后序列次历为例):遍历思路和子问题思路
遍历思路：
List<Character> ret = new ArrayList<>(); ///数组放在外面，为了防止每次递归都重新开放空间 public List<Character> postOrderTraversal(TreeNode root) { if(root == null) return ret; ret.add(root.val); postOrderTraversal(root.left); postOrderTraversal(root.right); return ret; }子问题思路：
public List<Character> postOrderTraversal(TreeNode root) { List<Character> ret = new ArrayList<>(); 如果把数组放在里面，需要接收回值，否则，每次都会重建新的数组 if(root == null) return ret; List<Character> leftTree = postOrderTraversal(root.left); ret.addAll(leftTree); List<Character> rightTree = postOrderTraversal(root.right); ret.addAll(rightTree); ret.add(root.val); return ret; }2.2.二叉树的基本操作
2.2.1.获得树中节点的数量-遍历思路
public static int nodeSize = 0; public int size(TreeNode root) { if(root == null) return 0; nodeSize ;///加起每棵子树的根 size(root.left); size(root.right); return nodeSize; }2.2.1.树中节点的数量-子问题思维
public int size2(TreeNode root) { if(root == null) return 0; //树的结点数 = 左树结点数 右子树结点数 根（1） return size2(root.left) + size2(root.right) + 1;
}2.2.2.获取叶子节点的个数---遍历思路
public static int leafSize = 0;
public int getLeafNodeCount(TreeNode root) {
if(root == null) return 0;
//叶子结点：左孩子和右孩子都为null
if(root.left == null && root. right == null) {
leafSize++;
}
getLeafNodeCount(root.left);
getLeafNodeCount(root.right);
return leafSize;
}2.2.2.获取叶子节点的个数---子问题思路
public int getLeafNodeCount2(TreeNode root) {
if(root == null) return 0;
if(root.left == null && root.right == null) {
return 1;
}
return getLeafNodeCount2(root.left) + getLeafNodeCount2(root.right);
}
2.2.3.获取第
K
层节点的个数
public int getKLevelNodeCount(TreeNode root, int k) {
if(root == null) return 0;
if(k == 1) return 1;
//第 k 层结点个数等于 以root的左子树为根结点的这棵树的第 k-1 层 + 以root的右子树为根结点的这棵树的第 k-1 层
// 依次类推，k == 1 的时候，这棵树只有根，左右子树都为空，那么就返回 1
return getKLevelNodeCount(root.left, k - 1) + getKLevelNodeCount(root.right, k - 1);
}2.2.4获取二叉树的高度
public int getHeight(TreeNode root) {
if(root == null) return 0;
if(root.left == null && root.right == null) {
return 1;
}
int leftH = getHeight(root.left);
int rightH = getHeight(root.right);
//二叉树的高度 = 左子树高度 和 右子树高度 中较大的一个 + 1
return leftH > rightH ? leftH + 1 : rightH + 1;
}这里的求左右子树的高度时，建议接收值，不然在三木操作符中会重复计算，导致时间浪费，在上可能就会跑不过。
2.2.5.检测值为value的元素是否存在
public TreeNode find(TreeNode root, char val) {
if(root == null) return null;
if(root.val == val) return root;
//left和right只有 root 和 null两种可能，先把左边找完，如果不为空，就返回
TreeNode left = find(root.left, val);
if(left != null) {
return left;
}
//右边和左边一样
TreeNode right = find(root.right, val);
if(right != null) {
return right;
}
return null;
}2.2.6.层序遍历---简易版
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);
}
}
}层序遍历需要用到队列，每一次出队后，就把出队元素的左右元素入队（不为空就入）
2.2.7.层序遍历---提高难度
public List<List<Character>> levelOrder(TreeNode root) {
List<List<Character>> ret = new ArrayList<>();
if(root == null) return ret;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while(!queue.isEmpty()) {
//二叉树当前层的元素集合
List<Character> list = new ArrayList<>();
int size = queue.size();
//size就是二叉树当前层的元素个数
while(size != 0) {
TreeNode cur = queue.poll();
list.add(cur.val);
size--;
if(cur.left != null) {
queue.offer(cur.left);
}
if(cur.right != null) {
queue.offer(cur.right);
}
}
ret.add(list);
}
return ret;
}当求一棵二叉树的层序遍历时，返回值改为二维数组，则每一层都可以看成是一个一维数组，这样的话，我们就可以在队列不为空这个循环里嵌套一个循环，用每一层的元素个数来控制循环；
2.2.8.判断一棵树是不是完全二叉树
public boolean isCompleteTree(TreeNode root) {
if(root == null) return false;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
TreeNode cur = queue.poll();
if(cur != null) {
queue.offer(cur.left);
queue.offer(cur.right);
}else {
break;
}
}
//第2次遍历队列 判断队列当中 是否存在非空的元素
while (!queue.isEmpty()) {
TreeNode cur = queue.peek();
if(cur == null) {
queue.poll();
}else {
return false;
}
}
return true;
}分析：判断一棵树是不是完全二叉树，也是要用到队列，类似于层序遍历，但是这里不同的是，左右子树为空也入队，null也是可以入队的；当弹出一个元素是 null 时，如果队里的元素全为 null，则说明它是一颗完全二叉树，，当然我们没有这种判断条件，所以这样做，当弹出的元素为 null 时，我们继续弹元素，如果为 null ，一直弹，直到队空；否则，就像图中右边的情况，弹出一个元素为空时，队里还有一个不为空，此时一定不是完全二叉树，，，
谢谢观看！！！