帮你从算法的角度来认识二叉树---（一）

一、基础概念1.定义二叉树是每个节点最多有两个子节点的树形结构两个子节点分别叫左子节点、右子节点2. 核心术语根节点树最顶端的节点叶子节点没有子节点的节点父节点 / 子节点上下级关系节点深度从根到当前节点的层数高度从当前节点到最远叶子的层数3. 特殊二叉树满二叉树所有层都填满节点完全二叉树除最后一层外都填满最后一层靠左排列二叉搜索树 (BST)左 根 右中序遍历是升序平衡二叉树左右子树高度差 ≤1二、定义二叉树节点这里用java来实现// 二叉树节点定义 public class TreeNode { int val; // 节点值 TreeNode left; // 左子节点 TreeNode right; // 右子节点 // 构造方法 TreeNode(int val) { this.val val; this.left null; this.right null; } }三、遍历二叉树1.前序遍历根--左--右//先序遍历 public void preOrder(TreeNode root){ if(rootnull) return; System.out.print(root.val );//根 preOrder(root.left);//左 preOrder(root.right);//右 }2.中序遍历左--根--右在上面提到的二叉搜索树是左子树值 根节点值 右子树值因此二叉搜索树中序遍历的结果是升序的// 中序遍历 public void inOrder(TreeNode root) { if (root null) return; inOrder(root.left); // 左 System.out.print(root.val ); // 根 inOrder(root.right); // 右 }3.后序遍历左--右--根// 后序遍历 public void postOrder(TreeNode root) { if (root null) return; postOrder(root.left); // 左 postOrder(root.right); // 右 System.out.print(root.val ); // 根 }4.层序遍历按层遍历BFS用队列实现这样可以一层一层来访问// 层序遍历队列实现 public void levelOrder(TreeNode root) { if (root null) return; // 1. 空树直接返回 QueueTreeNode queue new LinkedList(); queue.offer(root); // 2. 根节点入队 while (!queue.isEmpty()) { // 3. 队列不为空就继续 TreeNode node queue.poll();// 4. 出队一个节点 System.out.print(node.val ); // 5. 访问它 // 6. 左孩子、右孩子依次入队 if (node.left ! null) queue.offer(node.left); if (node.right ! null) queue.offer(node.right); } }四、构建二叉树public class BinaryTreeTest { public static void main(String[] args) { // 构建如下二叉树 // 1 // / \ // 2 3 // / \ // 4 5 TreeNode root new TreeNode(1); root.left new TreeNode(2); root.right new TreeNode(3); root.left.left new TreeNode(4); root.left.right new TreeNode(5); } }五、求二叉树的高度这里用递归来实现不断地求左子树的高度和右子树的高度然后返回两者最大值加11是根节点public int getHeight(TreeNode root) { if (root null) return 0; int leftH getHeight(root.left); int rightH getHeight(root.right); return Math.max(leftH, rightH) 1; }六、综合测试代码import java.util.LinkedList; import java.util.Queue; // 节点类 class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int val) { this.val val; this.left null; this.right null; } } // 二叉树操作类 public class BinaryTree { // 前序 public void preOrder(TreeNode root) { if(rootnull)return; System.out.print(root.val ); preOrder(root.left); preOrder(root.right); } // 中序 public void inOrder(TreeNode root) { if(rootnull)return; inOrder(root.left); System.out.print(root.val ); inOrder(root.right); } // 后序 public void postOrder(TreeNode root) { if(rootnull)return; postOrder(root.left); postOrder(root.right); System.out.print(root.val ); } // 层序 public void levelOrder(TreeNode root) { if(rootnull)return; QueueTreeNode qnew LinkedList(); q.offer(root); while(!q.isEmpty()){ TreeNode nq.poll(); System.out.print(n.val ); if(n.left!null)q.offer(n.left); if(n.right!null)q.offer(n.right); } } // 树高 public int getHeight(TreeNode root) { if(rootnull)return 0; return Math.max(getHeight(root.left),getHeight(root.right))1; } public static void main(String[] args) { BinaryTree treenew BinaryTree(); TreeNode rootnew TreeNode(1); root.leftnew TreeNode(2); root.rightnew TreeNode(3); root.left.leftnew TreeNode(4); root.left.rightnew TreeNode(5); System.out.println(前序);tree.preOrder(root); System.out.println(\n中序);tree.inOrder(root); System.out.println(\n后序);tree.postOrder(root); System.out.println(\n层序);tree.levelOrder(root); System.out.println(\n树高tree.getHeight(root)); } }七、小舟有话说这里仅介绍了一些概念和基本算法下一篇会着重讲一些常见的算法题哦~如果喜欢的话可以点点关注下次找我不迷路~