1. 为什么需要树这种数据结构？

1. 数组存储方式的优缺点：
   
   • 优点：可以直接通过下标访问元素，速度快。当是有序数组的时候，还可以使用二分查找提高查询的速度。即读取效率较高。
     
   • 缺点：如果需要检索某个具体的值，或插入值的时候，数组会整体移动，这时候效率就较低。即存储效率较低
     
2. 链式存储方式的优缺点：
   
   • 优点：存储效率较高。例如在插入一个数值节点，只需要将插入节点链接到链表中就可以了，删除效率也较高。
     
   • 缺点：检索效率较低，例如当需要检索某个值的时候，需要从头节点开始遍历。即读取效率较低
     
3. 树存储方式
   能够同时提高数据的存储和读取效率。例如二叉排序树，既可以保证数据的检索速度，同时可以保证数据的插入、删除、修改的速度。
   

2. 树的示意图和常用术语 2.1 树的示意图如下：

文章图片

2.2 常用术语

• 节点。就是图中的ABCDEFGH对象
  
• 根节点
  
• 父节点
  
• 子节点
  
• 叶子节点(没有子节点的节点)
  
• 节点的权(节点的值)
  
• 路径(从root节点找到该节点的路线)
  
• 层(就是图中标注的1、2、3、4层)
  
• 树的高度(最大层数)
  
• 森林(多颗子树构成一个森林)
  

3. 二叉树

1. 树的每个节点最多只能有两个子节点的树叫作二叉树。二叉树的子节点分为左节点和右节点。
   
2. 如果二叉树的所有叶子节点都在最后一层，并且节点总数等于2^n - 1，其中n为层数，那么就称该树为满二叉树
   

文章图片

3. 如果二叉树的所有叶子节点都在最后一层或者倒数第二层，而且最后一层的叶子节点在左边连续，倒数第二层的叶子节点在右边连续，那么就称该树为完全二叉树。

文章图片

4. 二叉树的遍历

1. 前序遍历： 先输出父节点，再遍历左子树，最后遍历右子树
   
2. 中序遍历： 先遍历左子树，再输出父节点，最后遍历右子树
   
3. 后续遍历： 先遍历左子树，再遍历右子树，最后输出父节点
   

总结：看输出父节点的顺序，就确定是前序、中序还是后序。
5. 二叉树前序、中序、后序遍历的步骤

1. 创建一颗二叉树
   
2. 前序遍历
   
   • 先输出当前节点(初始的时候是root节点)
     
   • 如果左子节点不为空，则递归继续前序遍历
     
   • 如果右子节点不为空，则递归继续前序遍历
     
3. 中序遍历
   
   • 如果当前节点的左子节点不为空，则递归中序遍历
     
   • 输出当前节点
     
   • 【数据结构——树】如果当前节点的右子节点不为空，则递归中序遍历
     
4. 后序遍历
   
   • 如果当前节点的左子节点不为空，则递归后序遍历
     
   • 如果当前节点的右子节点不为空，则递归后序遍历
     
   • 输出当前节点
     

6. 二叉树前序、中序、后序遍历的代码实现

1. 创建一个节点，并在节点中实现前序、中序、后序遍历
   

   //创建一个HeroNode节点 class HeroNode { private int no; private String name; private HeroNode left; private HeroNode right; public HeroNode(int no, String name) { this.no = no; this.name = name; } public int getNo() { return no; } public String getName() { return name; } public HeroNode getLeft() { return left; } public HeroNode getRight() { return right; } public void setNo(int no) { this.no = no; } public void setName(String name) { this.name = name; } public void setLeft(HeroNode left) { this.left = left; } public void setRight(HeroNode right) { this.right = right; } @Override public String toString() { return "HeroNode{" + "no=" + no + ", name='" + name + '\'' + '}'; } /** * 前序遍历的方法 */ public void preOrder() { System.out.println(this); //用递归，向左子树前序遍历 if (this.left != null) { this.left.preOrder(); } //用递归，向右子树前序遍历 if (this.right != null) { this.right.preOrder(); } } /** * 中序遍历的方法 */ public void infixOrder() { //用递归，向左子树中序遍历 if (this.left != null) { this.left.infixOrder(); } System.out.println(this); //用递归，向右子树中序遍历 if (this.right != null) { this.right.infixOrder(); } } /** * 后序遍历 */ public void postOrder() { //用递归，向左子树后序遍历 if (this.left != null) { this.left.postOrder(); } //用递归，向右子树后序遍历 if (this.right != null) { this.right.postOrder(); } System.out.println(this); } }

   
   
2. 定义一个二叉树，并添加前序、中序、后序遍历的实现逻辑
   

   //定义一个BinaryTree 二叉树 class BinaryTree { private HeroNode root; public void setRoot(HeroNode root) { this.root = root; } /** * 前序遍历 */ public void preOrder() { if (this.root != null) { this.root.preOrder(); } else { System.out.println("二叉树为空，无法遍历"); } } /** * 中序遍历 */ public void infixOrder() { if (this.root != null) { this.root.infixOrder(); } else { System.out.println("二叉树为空，无法遍历"); } } /** * 后序遍历 */ public void postOrder() { if (this.root != null) { this.root.postOrder(); } else { System.out.println("二叉树为空，无法遍历"); } } }

   
   
3. 代码测试
   

   public class BinaryTreeDemo { public static void main(String[] args) { //创建一颗二叉树 BinaryTree binaryTree = new BinaryTree(); //创建需要的节点 HeroNode root = new HeroNode(1, "宋江"); HeroNode node2 = new HeroNode(2, "吴用"); HeroNode node3 = new HeroNode(3, "卢俊义"); HeroNode node4 = new HeroNode(4, "林冲"); HeroNode node5 = new HeroNode(5, "关胜"); //手动将节点放到二叉树中 root.setLeft(node2); root.setRight(node3); node3.setRight(node4); node3.setLeft(node5); binaryTree.setRoot(root); System.out.println("前序遍历"); binaryTree.preOrder(); System.out.println("中序遍历"); binaryTree.infixOrder(); System.out.println("后序遍历"); binaryTree.postOrder(); } }

   
   
4. 运行结果
   

文章图片

7. 二叉树的前序查找、中序查找和后序查找 1. 前序遍历查找的思路

1. 判断当前节点的no是否等于要查找的，如果相等，则直接返回当前节点2. 如果不相等，判断当前节点的左子节点是否为空，如果不为空，则递归前序查找3. 如果左子递归前序查找，找到了节点，则返回，如果没有找到，则继续判断当前节点的右子节点是否为空，如果不为空，则继续右递归查找

2. 中序遍历查找的思路

1. 判断当前节点的左子节点是否为空，如果不为空，则递归中序查找2. 如果找到，就返回，如果没有找到，就和当前节点比较，如果相等，就返回当前节点，否则就继续右递归中序查找3. 如果右递归中序查找，找到就返回，否则返回null

3. 后序遍历查找的思路

1. 判断当前节点的左子节点是否为空，如果不为空，则递归后序查找2. 如果找到，就返回，如果没有找到，就判断当前节点的右子节点是否为空，如果不为空，则右递归后序查找，如果找到就返回 3. 如果没有找打，就和当前节点比较，如果相等就返回，否则返回null

4. 代码实现：

1. 在节点中实现查找逻辑
   

   class HeroNode { private int no; private String name; private HeroNode left; private HeroNode right; public HeroNode(int no, String name) { this.no = no; this.name = name; } public int getNo() { return no; } public String getName() { return name; } public HeroNode getLeft() { return left; } public HeroNode getRight() { return right; } public void setNo(int no) { this.no = no; } public void setName(String name) { this.name = name; } public void setLeft(HeroNode left) { this.left = left; } public void setRight(HeroNode right) { this.right = right; } @Override public String toString() { return "HeroNode{" + "no=" + no + ", name='" + name + '\'' + '}'; } /** * @param no 查找的编号 * @return 找到就返回Node，没有找到就返回null */ /** * 前序遍历查找思路分析 * 1. 判断当前节点的no是否等于要查找的，如果相等，则直接返回当前节点 * 2. 如果不相等，判断当前节点的左子节点是否为空，如果不为空，则递归前序查找 * 3. 如果左子递归前序查找，找到了节点，则返回，如果没有找到，则继续判断当前节点的右子节点是否为空，如果不为空，则继续右递归查找 */ public HeroNode preOrderSearch(int no) { System.out.println("进入前序查找"); if (this.no == no) { //当前节点找到 return this; } HeroNode resultNode = null; if (this.left != null) { //递归左子树 resultNode = this.left.preOrderSearch(no); } if (resultNode != null) { //如果在左子树上找到了 return resultNode; } if (this.right != null) { //递归右子树 resultNode = this.right.preOrderSearch(no); } return resultNode; } /** * 中序遍历查找思路分析 * 1. 判断当前节点的左子节点是否为空，如果不为空，则递归中序查找 * 2. 如果找到，就返回，如果没有找到，就和当前节点比较，如果相等，就返回当前节点，否则就继续右递归中序查找 * 3. 如果右递归中序查找，找到就返回，否则返回null */ /** * @param no 查找的编号 * @return 找到就返回Node，没有找到就返回null */ public HeroNode infixOrderSearch(int no) { HeroNode resultNode = null; if (this.left != null) { //递归左子树 resultNode = this.left.infixOrderSearch(no); } if (resultNode != null) { //左子树上找到 return resultNode; } System.out.println("进入中序查找"); if (this.no == no) { //当前节点找到 return this; } if (this.right != null) { //递归右子树 resultNode = this.right.infixOrderSearch(no); } return resultNode; } /** * 后序遍历查找思路分析 * 1. 判断当前节点的左子节点是否为空，如果不为空，则递归后序查找 * 2. 如果找到，就返回，如果没有找到，就判断当前节点的右子节点是否为空，如果不为空，则右递归后序查找，如果找到就返回 * 3. 如果没有找打，就和当前节点比较，如果相等就返回，否则返回null */ /** * @param no 查找的编号 * @return 找到就返回Node，没有找到就返回null */ public HeroNode postOrderSearch(int no) { HeroNode resultNode = null; if (this.left != null) { //递归左子树 resultNode = this.left.postOrderSearch(no); } if (resultNode != null) { //左子树上找到 return resultNode; } if (this.right != null) { //递归右子树 resultNode = this.right.postOrderSearch(no); } if (resultNode != null) { //右子树上找到 return resultNode; } System.out.println("进入后序查找"); if (this.no == no) { //当前节点找到 return this; } return resultNode; } }

   
   
2. 在二叉树中添加查找实现逻辑
   

   class BinaryTree { private HeroNode root; public void setRoot(HeroNode root) { this.root = root; } /** * 前序查找 * @param no * @return */ public HeroNode preOrderSearch(int no) { if (root != null) { return root.preOrderSearch(no); } else { return null; } } /** * 中序查找 * @param no * @return */ public HeroNode infixOrderSearch(int no) { if (root != null) { return root.infixOrderSearch(no); } else { return null; } } /** * 后序查找 * @param no * @return */ public HeroNode postOrderSearch(int no) { if (root != null) { return root.postOrderSearch(no); } else { return null; } } }

   
   
3. 测试代码
   

   public class BinaryTreeDemo { public static void main(String[] args) { //创建一颗二叉树 BinaryTree binaryTree = new BinaryTree(); //创建需要的节点 HeroNode root = new HeroNode(1, "宋江"); HeroNode node2 = new HeroNode(2, "吴用"); HeroNode node3 = new HeroNode(3, "卢俊义"); HeroNode node4 = new HeroNode(4, "林冲"); HeroNode node5 = new HeroNode(5, "关胜"); //手动将节点放到二叉树中 root.setLeft(node2); root.setRight(node3); node3.setRight(node4); node3.setLeft(node5); binaryTree.setRoot(root); System.out.println("前序查找") HeroNode resultNode = binaryTree.preOrderSearch(5); if (resultNode != null) { System.out.printf("找到了，信息为 no=%d , name = %s", resultNode.getNo(), resultNode.getName()); } else { System.out.printf("没有找到no = %d的英雄",5); } System.out.println("中序查找"); HeroNode resultNode = binaryTree.infixOrderSearch(5); if (resultNode != null) { System.out.printf("找到了，信息为 no=%d , name = %s", resultNode.getNo(), resultNode.getName()); } else { System.out.printf("没有找到no = %d的英雄",5); } System.out.println("后序查找"); HeroNode resultNode = binaryTree.postOrderSearch(5); if (resultNode != null) { System.out.printf("找到了，信息为 no=%d , name = %s", resultNode.getNo(), resultNode.getName()); } else { System.out.printf("没有找到no = %d的英雄",5); } } }

   
   
4. 运行结果
   

文章图片

8. 二叉树删除节点 1. 思路分析

/** * 递归删除节点 * 删除的规则说明： * 1. 如果删除的是叶子节点，则删除该节点 * 2. 如果删除的是非叶子节点，则直接删除该子树 * 思路分析： * 1. 因为我们的二叉树是单向的，所以是判断当前节点的子节点是否需要删除的节点，而不是去判断当前这个节点是不是需要删除的节点 * 2. 如果当前节点的左子树节点不为空，并且左子节点就是要删除的节点，就将this.left = null，并且结束递归删除 * 3. 如果当前节点的右子树节点不为空，并且右子节点就是要删除的节点，将将this.right = null，并且结束递归删除 * 4. 如果第2步和第3步都没有删除，就需要向左子树进行递归删除 * 5. 如果第4步也没有删除节点，就需要向右子树进行递归删除 */

2. 代码实现

1. 在节点中实现删除逻辑
   

   class HeroNode { private int no; private String name; private HeroNode left; private HeroNode right; public HeroNode(int no, String name) { this.no = no; this.name = name; } public int getNo() { return no; } public String getName() { return name; } public HeroNode getLeft() { return left; } public HeroNode getRight() { return right; } public void setNo(int no) { this.no = no; } public void setName(String name) { this.name = name; } public void setLeft(HeroNode left) { this.left = left; } public void setRight(HeroNode right) { this.right = right; } @Override public String toString() { return "HeroNode{" + "no=" + no + ", name='" + name + '\'' + '}'; } /** * 递归删除节点 * 删除的规则说明： * 1. 如果删除的是叶子节点，则删除该节点 * 2. 如果删除的是非叶子节点，则直接删除该子树 * 思路分析： * 1. 因为我们的二叉树是单向的，所以是判断当前节点的子节点是否需要删除的节点，而不是去判断当前这个节点是不是需要删除的节点 * 2. 如果当前节点的左子树节点不为空，并且左子节点就是要删除的节点，就将this.left = null，并且结束递归删除 * 3. 如果当前节点的右子树节点不为空，并且右子节点就是要删除的节点，将将this.right = null，并且结束递归删除 * 4. 如果第2步和第3步都没有删除，就需要向左子树进行递归删除 * 5. 如果第4步也没有删除节点，就需要向右子树进行递归删除 */ public void deleteNode(int no) { // 如果当前节点的左子树节点不为空，并且左子节点就是要删除的节点，就将this.left = null，并且结束递归删除 if (this.left != null && this.left.no == no) { this.left = null; return; } // 如果当前节点的右子树节点不为空，并且右子节点就是要删除的节点，将将this.right = null，并且结束递归删除 if (this.right != null && this.right.no == no) { this.right = null; return; } // 如果第2步和第3步都没有删除，就需要向左子树进行递归删除 if (this.left != null) { this.left.deleteNode(no); } // 如果第4步也没有删除节点，就需要向右子树进行递归删除 if (this.right != null) { this.right.deleteNode(no); } } }

   
   
2. 在二叉树中添加删除逻辑
   

   class BinaryTree { private HeroNode root; public void setRoot(HeroNode root) { this.root = root; } /** * 删除节点 * @param no */ public void deleteNode(int no) { if (root != null) { // 如果只有一个root节点，需要理解判root是不是就是要删除的节点 if (root.getNo() == no) { //删除树 root = null; } else { // 递归删除 root.deleteNode(no); } } else { System.out.println("空树，不能删除。。。"); } } }

   
   
3. 测试代码
   

   public class BinaryTreeDemo { public static void main(String[] args) { //创建一颗二叉树 BinaryTree binaryTree = new BinaryTree(); //创建需要的节点 HeroNode root = new HeroNode(1, "宋江"); HeroNode node2 = new HeroNode(2, "吴用"); HeroNode node3 = new HeroNode(3, "卢俊义"); HeroNode node4 = new HeroNode(4, "林冲"); HeroNode node5 = new HeroNode(5, "关胜"); //手动将节点放到二叉树中 root.setLeft(node2); root.setRight(node3); node3.setRight(node4); node3.setLeft(node5); binaryTree.setRoot(root); System.out.println("删除前，前序遍历"); binaryTree.preOrder(); binaryTree.deleteNode(5); binaryTree.deleteNode(3); System.out.println("删除后，前序遍历"); binaryTree.preOrder(); } }

   
   
4. 运行结果
   

文章图片

非常感谢您的耐心阅读，希望我的文章对您有帮助。欢迎点评、转发或分享给您的朋友或技术群。

推荐阅读

• 

  头孢和酒一起喝有什么后果会死吗
• 

  痒组词和拼音 痒是什么意思
• 

  500G 320G 200G 硬盘现在报价是多少钱，256MB七彩虹显卡多少钱？帮忙写个两千块的电脑，不算显示器两千左右，写的好多给分，要符合现在的价钱，复制绝对不采纳！,200万MB是多少G流量
• 

  森马服装店 森马加盟费
• 

  计日程功的意思是什么 计日程功是什么意思
• 

  寒食节的由来 寒食节是几月几号
• 

  奶茶糖分等级怎么分
• 

  菲斯曼锅炉重启方法原因，热水器不工作常见3种解决方法？
• 

  吴青峰在歌手唱起风了是第几期
• 

  风池穴有7大作用 风池穴位位置图
• 

  非法放贷是什么
• 

  csgo技术不稳定怎么办？
• 

  浪食
• 

  惠州退休养老金计算器怎么算？惠州退休后养老金一个月能拿到多少钱？
• 

  E680成功移植通讯录from 索爱T618
• 

  樱花粉配什么颜色好看
• 

  阳台种辣椒怎么授粉，室内种辣椒需要授粉吗
• 

  华为适合打游戏的平板，想买个平板用来玩游戏的需要待机时间长需要支持很多游戏
• 

  蟑螂爬到床上怎么处理
• 

  大麦若叶青汁什么味道

• 急于表达——往往欲速则不达
• 慢慢的美丽
• 《真与假的困惑》???|《真与假的困惑》??? ——致良知是一种伟大的力量
• 2019-02-13——今天谈梦想（）
• 考研英语阅读终极解决方案——阅读理解如何巧拿高分
• Ⅴ爱阅读，亲子互动——打卡第178天
• 低头思故乡——只是因为睡不着
• 取名——兰
• 每日一话（49）——一位清华教授在朋友圈给大学生的9条建议
• 【生信技能树】R语言练习题|【生信技能树】R语言练习题 - 中级