思维导图：
1.树的概念：
- 树是一种非线性的数据结构，由递归定义出来的。根节点R在上，其他节点在下；树形结构中子树不能有交集，否则不能称为树形结构。
- 树的几种重要概念，参照上图：
1.节点的度：一个节点含有子树的个数，例如：c的度就是3
2.树的度：一棵树中所有节点的度的最大值，例如：上图中树的度就是3
3.叶子节点或终端节点：一个节点没有任何子树，例如：j、k、e、f、g、m、n、i
4.双亲节点或父节点：一个节点含有子节点，例如：r是a、b、c的父节点
5.孩子节点或子节点：例如：a、b、c是r的孩子节点
6.根节点：一棵树中，没有双亲节点的节点，例如：r就是根节点
7.节点的层次：从根开始算，r为第1层，a、b、c为第2层
8.树的高度或深度：树中节点的最大层次，例如：上图中树的最大高度为4
2.二叉树：
- 二叉树是由1个根节点加上左子树和右子树组成的，每个根节点可以有2棵子树、1棵子树也可以没有子树。因此：二叉树不会存在度大于2的节点；二叉树的子树有左右之分，不可以颠倒；一颗二叉树的左子树和右子树也必须是二叉树。
- 有2种特殊的二叉树分别为满二叉树和完全二叉树。满二叉树是1棵二叉树上的每层节点数达到最大值，如果1棵二叉树的层数为n并且节点总数为 (2^n) - 1；则这棵树就是满二叉树。
- 二叉树的性质：
1.规定根节点的层数为1，则1棵非空二叉树的第i层上最多有2^(i-1)个节点
2.规定根节点的二叉树高度为1，则高度为k的二叉树最大节点数是2^k - 1
3.度为0的节点个数比度为2的个数多1个
4.有n个节点的完全二叉树的深度为log以2为底的(n+1)向上取整
- 二叉树的存储是通过一个一个的节点引用起来的，常用的表示方式有孩子表示法和孩子双亲表示法。二叉树的存储分为顺序存储和类似于链表的链式存储，注意类似于链表不是链表。
3.二叉树的遍历：
- 二叉树的遍历是二叉树最重要的基本功能。
- 前序遍历：先访问根节点—>左子树—>右子树
参照上图前序遍历：r a d e c g i
- 中序遍历：先访问左子树—>根节点—>右子树
参照上图中序遍历：d a e r g c i
- 后序遍历：先访问左子树—>右子树—>根节点
参照上图后序遍历：d e a g i c r
- 层序遍历：从左到右遍历每一层
参照上图层序遍历：r a c d e g i
- 根据前序遍历和后序遍历不能创建出一个二叉树，前序和后序只能确定根。
- 前、中、后、层+序遍历的代码实现：
public class BinaryTree { class TreeNode{ //孩子表示法 public char val; public TreeNode left; public TreeNode right; public TreeNode(char val){ this.val = val; } } public TreeNode root; //前序遍历1 public void preOrder1(TreeNode root){ if(root == null) return; System.out.print(root.val+" "); preOrder1(root.left); preOrder1(root.right); } //前序遍历2：有返回值类型，遍历思路 class Solution{ //list必须定义在外面，否则每次递归都会创建1个list List<Character> list = new ArrayList<>(); public List<Character> preOrder2(TreeNode root){ if(root == null) return list; list.add(root.val); preOrder2(root.left); preOrder2(root.right); return list; } } //前序遍历3：有返回值，子问题思路 public List<Character> preOrder3(TreeNode root){ List<Character> list = new ArrayList<>(); if(root == null) return list; list.add(root.val); List<Character> leftTree = preOrder3(root.left); list.addAll(leftTree); List<Character> rightTree = preOrder3(root.right); list.addAll(rightTree); return list; } //中序遍历1 public void inOrder(TreeNode root){ if(root == null) return; inOrder(root.left); System.out.print(root.val+" "); inOrder(root.right); } //中序遍历2：有返回值，子问题思路 public List<Character> inOrder2(TreeNode root){ List<Character> list = new ArrayList<>(); if(root == null) return list; List<Character> leftTree = inOrder2(root.left); list.addAll(leftTree); list.add(root.val); List<Character> rightTree = inOrder2(root.right); list.addAll(rightTree); return list; } //后序遍历1 public void postOrder(TreeNode root){ if(root == null) return; postOrder(root.left); postOrder(root.right); System.out.print(root.val+" "); } //后序遍历2：有返回值，子问题思路 public List<Character> postOrder2(TreeNode root){ List<Character> list = new ArrayList<>(); if(root == null) return list; List<Character> leftTree = postOrder(root.left); list.addAll(leftTree); List<Character> rightTree = postOrder2(root.right); list.addAll(rightTree); list.add(root.val); return list; } //层序遍历1:使用到了队列 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+" "); if(cur.left != null){ queue.offer(cur.left); } if(cur.right != null){ queue.offer(cur.right); } } } }
4.二叉树的模拟实现：
获取树中节点得个数
获取叶子节点的个数
获取第k层节点的个数
获取二叉树的高度
检测值value是否存在
代码实现如下：
public class BinaryTree { class TreeNode{ //孩子表示法 public char val; public TreeNode left; public TreeNode right; public TreeNode(char val){ this.val = val; } } public TreeNode root; //获取树中节点的个数1:子问题思路 public int size(TreeNode root){ if(root == null) return 0; return size(root.left)+size(root.right)+1; } //获取树中节点的个数2:遍历思路 public static int nodeSize; public void size2(TreeNode root){ if(root == null) return; nodeSize++; size2(root.left); size2(root.right); } //获取叶子节点的个数1：子问题思路 public int getLeafNodeCount(TreeNode root){ if(root == null) return 0; if(root.left == null && root.right==null){ return 1; } return getLeafNodeCount(root.left)+ getLeafNodeCount(root.right); } //获取叶子节点的个数2：遍历思路 public static int leafSize; public void getLeafNodeCount2(TreeNode root){ if(root == null) return; if(root.left == null && root.right == null){ leafSize++; } getLeafNodeCount2(root.left); getLeafNodeCount2(root.right); } //获取第k层节点的个数：子问题思路 public int getKLevelNodeCount(TreeNode root,int k){ if(root == null) return 0; if(k == 1) return 1; //对k操作不会影响右树 return getKLevelNodeCount(root.left,k-1) +getKLevelNodeCount(root.right,k-1); } //获取二叉树的高度 public int getHeight(TreeNode root){ if(root == null) return 0; int leftHeight = getHeight(root.left); int rightHeight = getHeight(root.right); return (leftHeight > rightHeight? leftHeight+1 : rightHeight+1); } //检测value是否存在 public TreeNode find(TreeNode root,int value){ if(root == null) return null; if(root.val == value){ return root; } TreeNode ret1 = find(root.left,value); if(ret1 != null) return ret1; TreeNode ret2 = find(root.right,value); if(ret2 != null) return ret2; return null; } //判断一棵树是不是完全二叉树 public boolean isCompleteTree(TreeNode root){ if(root == null) return true; Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); while(!queue.isEmpty()){ TreeNode cur = queue.poll(); System.out.println(cur+" "); if(cur != null){ queue.offer(cur.left); queue.offer(cur.right); }else{ break; } } while(!queue.isEmpty()){ TreeNode cur = queue.peek(); if(cur != null){ return false; }else{ queue.poll(); } } return true; } }
5.二叉树的OJ题：
1.检查俩颗二叉树是否完全相同，时间复杂度为O(min(m,n))
//检查俩颗树是否完全相同 public boolean isSameTree(TreeNode p,TreeNode q){ if(p == null &&q != null || q == null && p != null) return false; if(p == null && q == null) return true; if(p.val == q.val) return true; return isSameTree(p.left,q.left) && isSameTree(p.right,q.right); }
2.判断一棵树是不是另外一棵树的子树，时间复杂度为O(m*n)
//判断一棵树是不是另外一棵树的子树 public boolean isSubTree(TreeNode root,TreeNode subRoot){ if(root == null || subRoot == null) return false; if(isSameTree(root,subRoot)) return true; if(isSameTree(root.left,subRoot)) return true; if(isSameTree(root.right,subRoot)) return true; return false; }
3.二叉树的最大深度
//得到一棵树的高度 private int getHeight(TreeNode root) { if(root == null) return 0; int leftTree = getHeight(root.left); int rightTree = getHeight(root.right); return leftTree > rightTree? leftTree+1 : rightTree+1; }
4.判断一棵树是不是平衡二叉树
//得到一棵树的高度 private int getHeight(TreeNode root) { if(root == null) return 0; int leftTree = getHeight(root.left); int rightTree = getHeight(root.right); return leftTree > rightTree? leftTree+1 : rightTree+1; } //1.判断一棵树是否是平衡二叉树,时间复杂度为O(n^2) public boolean isBalanced(TreeNode root){ if(root == null){ return true; } int leftTree = getHeight(root.left); int rightTree = getHeight(root.right); return Math.abs(leftTree-rightTree)<=1 && isBalanced(root.left) && isBalanced(root.right); } //2.判断一棵树是否是平衡二叉树，时间复杂度为O(n) public boolean isBalanced2(TreeNode root){ if(root == null) return true; return maxDepth(root)>=0; } private int maxDepth(TreeNode root) { if(root == null) return 0; int leftTree = maxDepth(root.left); int rightTree = maxDepth(root.right); if(leftTree >= 0 && rightTree >= 0 && Math.abs(leftTree-rightTree) <= 1){ return Math.max(leftTree,rightTree)+1; }else{ return -1; } }
5.构建一颗二叉树
//构建一颗二叉树 public static int i; public TreeNode createTree(String s){ TreeNode root = null; if(s.charAt(i) != '#'){ root = new TreeNode(s.charAt(i)); i++; root.left = createTree(s); root.right = createTree(s); }else{ i++; } return root; }
6.二叉树的分层遍历
//二叉树的分层遍历 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()){ int size = queue.size(); List<Character> row = new ArrayList<>(); while(size > 0){ TreeNode cur = queue.poll(); size--; row.add(cur.val); if(cur.left != null){ queue.offer(cur.left); } if(cur.right != null){ queue.offer(cur.right); } } ret.add(row); } return ret; }
7.找到俩个二叉树的公共祖先
//找俩个节点的公共祖先,方法1 public TreeNode lowestAncestor(TreeNode root,TreeNode p,TreeNode q){ if(root == null) return null; if(root == p || root == q) return root; TreeNode retleft = lowestAncestor(root.left,p,q); TreeNode retright = lowestAncestor(root.right,p,q); if(retleft != null && retright != null){ return root; } else if (retleft != null) { return retleft; }else{ return retright; } } //找俩个节点的公共祖先,方法2:找到根节点到指定节点之间的所有节点，存到stack中 private boolean getPath(TreeNode root, TreeNode node, Stack<TreeNode> stack){ if(root == null || node == null) return false; stack.push(root); if(root == node) return true; boolean ret1 = getPath(root.left,node,stack); if(ret1 == true) return true; boolean ret2 = getPath(root.right,node,stack); if(ret2 == true) return true; stack.pop(); return false; } public TreeNode lowestAncestor2(TreeNode root,TreeNode p,TreeNode q){ if(root == null || p == null || q == null) return null; Stack<TreeNode> stack1 = new Stack<>(); getPath(root,p,stack1); Stack<TreeNode> stack2 = new Stack<>(); getPath(root,q,stack2); int size1 = stack1.size(); int size2 = stack2.size(); if(size1 > size2){ int tmp = size1 - size2; while(tmp != 0){ stack1.pop(); tmp--; } }else{ int tmp = size2 - size1; while(tmp != 0){ stack2.pop(); tmp--; } while(! stack1.empty() && !stack2.empty()){ if(stack1.peek() == stack2.peek()){ return stack1.peek(); }else{ stack1.pop(); stack2.pop(); } } return null; }
8.将二叉搜索树转换成排序双向链表
//二叉搜索树转换成排序双向链表 public TreeNode prev = null; private void ConvertChild(TreeNode root){ if(root == null) return ; ConvertChild(root.left); root.left = prev; if(prev != null){ prev.right = root; } prev = root; ConvertChild(root.right); } public TreeNode Convert(TreeNode pRootOfTree){ if(pRootOfTree == null) return null; ConvertChild(pRootOfTree); TreeNode head = pRootOfTree; while(head.left != null){ head = head.left; } return head; }
9.根据前序和后序遍历构造二叉树
//根据前序和中序遍历构造二叉树 public int preindex = 0; private TreeNode buildTreeChild(int[] preorder,int[] inorder,int inbegin,int inend){ //没有了左树或没有右树 if(inbegin > inend) return null; TreeNode root = new TreeNode(preorder[preindex]); //找到当前根节点在中序遍历中的位置 int rootIndex = findInorderIndex(inorder,preorder[preindex],inbegin,inend); preindex++; root.left = buildTreeChild(preorder,inorder,inbegin,rootIndex-1); root.right = buildTreeChild(preorder,inorder,rootIndex+1,inend); return root; } private int findInorderIndex(int[] inorder,int val,int inbegin,int inend){ for (int i = inbegin; i <= inend; i++) { if (inorder[i] == val){ return i; } } return -1; } public TreeNode buildTree(int[] preorder,int[] inorder){ return buildTreeChild(preorder,inorder,0,inorder.length-1); }
10.根据中序和后序遍历构造二叉树
//根据中序和后序遍历构造二叉树 public int postindex = 0; private TreeNode buildTreeChild(int[] postorder,int[] inorder,int inbegin,int inend){ //没有了左树或没有右树 if(inbegin > inend) return null; TreeNode root = new TreeNode(postorder[postindex]); //找到当前根节点在中序遍历中的位置 int rootIndex = findInorderIndex(inorder,postorder[postindex],inbegin,inend); postindex--; root.right = buildTreeChild(postorder,inorder,rootIndex+1,inend); root.left = buildTreeChild(postorder,inorder,inbegin,rootIndex-1); return root; } private int findInorderIndex(int[] inorder,int val,int inbegin,int inend){ for (int i = inbegin; i <= inend; i++) { if (inorder[i] == val){ return i; } } return -1; } public TreeNode buildTree(int[] postorder,int[] inorder){ postindex = postorder.length-1; return buildTreeChild(postorder,inorder,0,inorder.length-1); }
11.二叉树创建字符串
//二叉树创建字符串 public String tree2str(TreeNode root) { StringBuilder sb = new StringBuilder(); tree2strChild(root,sb); return sb.toString(); } private void tree2strChild(TreeNode t,StringBuilder sb) { if(t == null) return ; sb.append(t.val); if(t.left != null) { sb.append("("); tree2strChild(t.left,sb); sb.append(")"); }else { if(t.right == null) { return; }else{ sb.append("()"); } } if(t.right == null) { return; }else{ sb.append("("); tree2strChild(t.right,sb); sb.append(")"); } }
12.非递归实现前序遍历
//非递归实现前序遍历 public void preorderTraversalNor(TreeNode root) { Stack<TreeNode> stack = new Stack<>(); TreeNode cur = root; while (cur != null || !stack.empty()) { while (cur != null) { stack.push(cur); System.out.print(cur.val + " "); cur = cur.left; } TreeNode top = stack.pop(); cur = top.right; } }
13.非递归实现中序遍历
//非递归实现中序遍历 public void inorderTraversal(TreeNode root) { Stack<TreeNode> stack = new Stack<>(); TreeNode cur = root; while (cur != null || !stack.empty()) { while (cur != null) { stack.push(cur); cur = cur.left; } TreeNode top = stack.pop(); System.out.print(top.val + " "); cur = top.right; } }
14.非递归实现后序遍历
//非递归实现后序遍历 public void postorderTraversal(TreeNode root) { Stack<TreeNode> stack = new Stack<>(); TreeNode prev = null; TreeNode cur = root; while (cur != null || !stack.empty()) { while (cur != null) { stack.push(cur); cur = cur.left; } TreeNode top = stack.peek(); //top.right 如果已经被访问了 也要弹出top所指向的节点 if (top.right == null || top.right == prev) { stack.pop(); System.out.print(top.val + " "); prev = top; } else { cur = top.right; } } }
如果对您有帮助的话，
不要忘记点赞+关注哦，蟹蟹
如果对您有帮助的话，
不要忘记点赞+关注哦，蟹蟹
如果对您有帮助的话，
不要忘记点赞+关注哦，蟹蟹
