算法

二叉树----遍历、查找、删除

1、为什么需要树？

数组的查找效率高，但是插入效率低。
链表的插入效率高，查找效率低。

2、二叉树

二叉树的基本概念：每个节点最多只能由两个子节点的一种树叫做二叉树
满二叉树：如果该二叉树的所有叶子节点都在最后一层，并且结点总数= 2n -1 , n为层数，则我们称为满二叉树。
完全二叉树：如果该二叉树的所有叶子节点都在最后一层或者倒数第二层，而且最后一层的叶子节点在左边连续，倒数第二层的叶子节点在右边连续，我们称为完全二叉树

3、二叉树的遍历

前序遍历
先遍历父节点，再遍历左子节点，最后遍历右子节点
中序遍历
先遍历左子节点，再遍历父节点，最后遍历右子节点
后序遍历
先遍历左子节点，再遍历右子节点，最后遍历父节点

区别：看父节点什么时候遍历，在最前面就是前序，在中间就是中序，在最后就是后续

4、二叉树的遍历代码实现

class BinaryTree {
   /**
    * 根节点
    */
   private StuNode root;

   public void setRoot(StuNode root) {
      this.root = root;
   }

   public void preTraverse() {
      if(root != null) {
         System.out.println("前序遍历");
         root.preTraverse();
         System.out.println();
      }else {
         System.out.println("二叉树为空！");
      }
   }

   public void midTraverse() {
      if(root != null) {
         System.out.println("中序遍历");
         root.midTraverse();
         System.out.println();
      }else {
         System.out.println("二叉树为空！");
      }  }

   public void lastTraverse() {
      if(root != null) {
         System.out.println("后序遍历");
         root.lastTraverse();
         System.out.println();
      }else {
         System.out.println("二叉树为空！");
      }  }
}

/**
 * 二叉树中的一个节点
 * 保存了学生信息和左右孩子信息
 */
@Data
class StuNode {
   int id;
   String name;
   StuNode left;
   StuNode right;

   public StuNode(int id, String name) {
      this.id = id;
      this.name = name;
   }

   @Override
   public String toString() {
      return "StuNode{" +
            "id=" + id +
            ", name='" + name + '\'' +
            '}';
   }

   /**
    * 前序遍历
    */
   public void preTraverse() {
      //父节点最开始就输出
      System.out.println(this);
      if(left != null) {
         left.preTraverse();
      }
      if(right != null) {
         right.preTraverse();
      }
   }

   /**
    * 中序遍历
    */
   public void midTraverse() {
      if(left != null) {
         left.midTraverse();
      }
      //父节点在中间输出
      System.out.println(this);
      if(right != null) {
         right.midTraverse();
      }
   }

   public void lastTraverse() {
      if(left != null) {
         left.lastTraverse();
      }
      if(right != null) {
         right.lastTraverse();
      }
      //父节点在最后输出
      System.out.println(this);
   }
}

5、二叉树的查找

与3是类似的，在遍历的过程中加一个判断，找到对应的元素直接返回即可！

6、二叉树的查找代码实现

class BinarySearchTree {
   private Student root;

   public void setRoot(Student root) {
      this.root = root;
   }

   public void preSearch(int id) {
      System.out.println("前序查找");
      if(root == null) {
         System.out.println("树为空！");
         return;
      }
      Student result = root.preSearch(id);
      if(result == null) {
         System.out.println("未找到该元素");
         System.out.println();
         return;
      }
      System.out.println(result);
      System.out.println();
   }

   public void midSearch(int id) {
      System.out.println("中序查找");
      if(root == null) {
         System.out.println("树为空！");
         return;
      }
      Student result = root.midSearch(id);
      if(result == null) {
         System.out.println("未找到该元素");
         System.out.println();
         return;
      }
      System.out.println(result);
      System.out.println();
   }

   public void lastSearch(int id) {
      System.out.println("后序查找");
      if(root == null) {
         System.out.println("树为空！");
         return;
      }
      Student result = root.lastSearch(id);
      if(result == null) {
         System.out.println("未找到该元素");
         System.out.println();
         return;
      }
      System.out.println(result);
      System.out.println();
   }
}

@Data
class Student {
   int id;
   String name;
   Student left;
   Student right;

   public Student(int id, String name) {
      this.id = id;
      this.name = name;
   }

   @Override
   public String toString() {
      return "Student{" +
            "id=" + id +
            ", name='" + name + '\'' +
            '}';
   }

   /**
    * 前序查找
    * @param id 要查找的学生id
    * @return 查找到的学生
    */
   public Student preSearch(int id) {
      //如果找到了，就返回
      if(this.id == id) {
         return this;
      }

      //在左子树中查找，如果找到了就返回
      Student student = null;
      if(left != null) {
         student = left.preSearch(id);
      }
      if(student != null) {
         return student;
      }

      //在右子树中查找，无论是否找到，都需要返回
      if(right != null) {
         student = right.preSearch(id);
      }
      return student;
   }

   /**
    * 中序查找
    * @param id 要查找的学生id
    * @return 查找到的学生
    */
   public Student midSearch(int id) {
      Student student = null;
      if(left != null) {
         student = left.midSearch(id);
      }
      if(student != null) {
         return student;
      }

      //找到了就返回
      if(this.id == id) {
         return this;
      }

      if(right != null) {
         student = right.midSearch(id);
      }
      return student;
   }

   /**
    * 后序查找
    * @param id 要查找的学生id
    * @return 查找到的学生
    */
   public Student lastSearch(int id) {
      Student student = null;
      if(left != null) {
         student = left.lastSearch(id);
      }
      if(student !=null) {
         return student;
      }

      if(right != null) {
         student = right.lastSearch(id);
      }

      if(this.id == id) {
         return this;
      }
      return student;
   }
}

7、二叉树节点的删除

如果删除的节点是叶子节点，则删除该节点
如果删除的节点是非叶子节点，则删除该子树.

7.1、删除节点的思路：

先考虑是否是个空树，即root节点是否为null
因为我们的二叉树是单向的，所以我们是判断当前结点的子结点是否需要删除结点，而不能去判断当前这个结点是不是需要删除结点(假如找到了当前节点，就无法找到当前节点的父节点，也就意味着无法删除当前节点了)
如果当前结点的左子结点不为空，并且左子结点就是要删除结点，就将 this.left = null; 并且就返回 (结束递归删除)
如果当前结点的右子结点不为空，并且右子结点就是要删除结点，就将 this.right= null ;并且就返回 (结束递归删除)
如果第2和第3步没有删除结点，那么我们就需要向左子树进行递归删除
如果 4步也没有删除结点，则应当向右子树进行递归删除

7.2、删除节点的代码实现

class BinaryDeleteTree {
   StudentNode root;

   public void setRoot(StudentNode root) {
      this.root = root;
   }

   /**
    * 删除节点
    * @param id 删除节点的id
    */
   public void deleteNode(int id) {
      System.out.println("删除节点");
      if(root.id == id) {
         root = null;
         System.out.println("根节点被删除");
         return;
      }
      //调用删除方法
      root.deleteNode(id);
   }
}

@Data
class StudentNode {
   int id;
   String name;
   StudentNode left;
   StudentNode right;

   public StudentNode(int id, String name) {
      this.id = id;
      this.name = name;
   }

   @Override
   public String toString() {
      return "StudentNode{" +
            "id=" + id +
            ", name='" + name + '\'' +
            '}';
   }

   /**
    * 删除节点
    * @param id 删除节点的id
    */
   public void deleteNode(int id) {
      //如果左子树不为空且是要查找的节点，就删除
      if(left != null && left.id == id) {
         left = null;
         System.out.println("删除成功");
         return;
      }

      //如果右子树不为空且是要查找的节点，就删除
      if(right != null && right.id == id) {
         right = null;
         System.out.println("删除成功");
         return;
      }

      //左递归，继续查找
      if(left != null) {
         left.deleteNode(id);
      }

      //右递归，继续查找
      if(right != null) {
         right.deleteNode(id);
      }
   }
}

如果觉得文章对你有用，请随意赞赏

算法

二叉树----遍历、查找、删除

http://192.168.0.251:2081/archives/er-cha-shu----bian-li-cha-zhao-shan-chu

作者

Administrator

发布于

2023-11-13

更新于

2024-10-13

许可协议

CC BY 4.0