二叉搜索树

  • 是一颗二叉树
  • 所有左子树节点比根节点小，所有右子树节点比根节点大
  • 根节点的后继节点就是后第一个比他大的节点，特点就是后继节点一定没有左子树

  • 当删除一个节点时，将他的后继节点值补上去，然后再把后继节点右子树放在原后继节点位置

    二叉搜索树增删查基本操作

  • 删除操作是找到删除节点后继节点，将后继节点值赋值给删除节点，然后将后继节点右子树提上去 ```java package com.tuling.datastruct.suanfa; /**

    • @author lfy 二叉搜索树的增删改

    • @date 2022-05-05 */ public class BinarySearchTree {

      //树中插入元素 public void insert(TreeNode root,int data){

      1. if (null != root){
      2.     if (data > root.data){
      3.         if (null != root.right){
      4.             insert(root.right,data);
      5.         }else {
      6.             root.right = new TreeNode(data);
      7.         }
      8.     }else {
      9.         if (null != root.left){
      10.             insert(root.left,data);
      11.         }else {
      12.             root.left = new TreeNode(data);
      13.         }
      14.     }
      15. }

      } //查询元素 public TreeNode find(TreeNode root,int data){

      1. if (root.data == data){
      2.     return root;
      3. }
      4. if (data > root.data){
      5.     if (null != root.right){
      6.         TreeNode treeNode = find(root.right, data);
      7.         return treeNode;
      8.     }else {
      9.         return null;
      10.     }
      12. }else {
      13.     if (null != root.left){
      14.         TreeNode treeNode = find(root.left, data);
      15.         return treeNode;
      16.     }else {
      17.         return null;
      18.     }
      19. }

      } //删除元素,有三种情况 //删除节点是叶子节点直接删除 //删除节点有右子树，找到后继节点代替删除节点，再把后继节点删除 //删除节点有左子树，找到前驱节点代替删除节点，再把前驱节点删除 public TreeNode remove(TreeNode root,int data){

      1. if (data < root.data){
      2.     root.left = remove(root.left,data);
      3. }else if (data > root.data){
      4.     root.right = remove(root.right,data);
      5. }else {
      6.     if (root.left == null && root.right == null){
      7.         root = null;
      8.     }else if (root.right != null){
      9.         root.data = findAfterNode(root);
      10.         root.right = remove(root.right,root.data);
      11.     }else {
      12.         root.data = findBeforeNode(root.left);
      13.         root.left = remove(root.left,root.data);
      14.     }
      15. }
      16. return root;

      }

      private int findAfterNode(TreeNode root){

      1. root = root.right;
      2. while (null != root.right){
      3.     root = root.right;
      4. }
      5. return root.data;

      } private int findBeforeNode(TreeNode root){

      1. root = root.left;
      2. while (null != root){
      3.     root = root.left;
      4. }
      5. return root.data;

      }

  1. public static void main(String[] args) {
  2.     TreeNode root = new TreeNode(8);
  3.     int[] param = new int[]{5,11,3,7,9,12,4,10};
  4.     BinarySearchTree tree = new BinarySearchTree();
  5.     for (int i : param) {
  6.         tree.insert(root,i);
  7.     }
  8.     TreeNode treeNode = tree.find(root, 10);
  9.     tree.remove(root,5);
  11.     System.out.println(treeNode.data);
  12.     System.out.println(treeNode.left.data);
  13.     System.out.println(treeNode.right.data);
  14. }

}

  1. <a name="qy6N6"></a>
  2. #### 二叉树的层序遍历，广度优先算法
  3. ```java
  4. package com.alg.two;
  6. /**
  7.  * @author fuyao
  8.  * @date 2022年04月19日 5:20 下午
  9.  */
  10. public class IsSymmetric {
  12.     public boolean isSymmetric(Node tree){
  14.         return checkSymmetric(tree.left,tree.right);
  15.     }
  16.     public boolean checkSymmetric(Node left,Node right){
  17.         if (left == null && right == null) {
  18.             return true;
  19.         }
  20.         if (left == null || right == null){
  21.             return false;
  22.         }
  23.         if (left.value != right.value){
  24.             return false;
  25.         }
  26.         return checkSymmetric(left.left,right.right) && checkSymmetric(left.right,right.left);
  27.     }
  30.     public static void main(String[] args) {
  31.         Node node1 = new Node(1);
  32.         Node node3 = new Node(3);
  33.         Node node2 = new Node(2,node1,node3);
  34.         IsSymmetric tree = new IsSymmetric();
  35.         System.out.println(tree.isSymmetric(node2));
  36.     }
  39.     static class Node{
  40.         int value;
  41.         Node left;
  42.         Node right;
  44.         public Node(int value) {
  45.             this.value = value;
  46.         }
  48.         public Node(int value, Node left, Node right) {
  49.             this.value = value;
  50.             this.left = left;
  51.             this.right = right;
  52.         }
  53.     }
  54. }

二叉树深度优先遍历优先

  1. public void in(BinarySeachTree root) {        //中序遍历
  2.         if(root != null) {
  3.             in(root.left);
  4.             System.out.print(root.data + " ");
  5.             in(root.right);
  6.         }
  7.     }