devbox
笔触狂放9
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

数据结构 -- 二叉树&二叉搜索树

作者：笔触狂放9 | 2024-04-28 00:03:52

赞

踩

数据结构 -- 二叉树&二叉搜索树

二叉树

二叉树是这么一种树状结构：每个节点最多有两个孩子，左孩子和右孩子

重要的二叉树结构

  • 完全二叉树（complete binary tree）是一种二叉树结构，除最后一层以外，每一层都必须填满，填充时要遵从先左后右

  • 平衡二叉树（balance binary tree）是一种二叉树结构，其中每个节点的左右子树高度相差不超过 1

1) 存储

存储方式分为两种

  1. 定义树节点与左、右孩子引用（TreeNode）

  2. 使用数组，前面讲堆时用过，若以 0 作为树的根，索引可以通过如下方式计算

    • 父 = floor((子 - 1) / 2)

    • 左孩子 = 父 * 2 + 1

    • 右孩子 = 父 * 2 + 2

 没有孩子的节点也有一个称呼:叶子结点

我们之前学优先级队列和堆结构的时候其实都接触过,比如我们之前学的大顶堆

当然大顶堆这种二叉树属于比较特殊的二叉树,叫完全二叉树,也就是除了最后一层以外,每一层都得填满而且填充的顺序必须从左到右填充

遍历

遍历也分为两种

1.广度优先遍历(Breadth-first-order):尽可能先访问离根最近的节点,也称为层序遍历

2.深度优先遍历(Depth-first-order):对于二叉树,可以进一步分为三种

        1.pre-order前序遍历,对于一棵子树,先访问该节点,然后是左子树,最后是右子树

        2.in-order中序遍历,对于每一颗子树,先访问左子树,然后是该节点,最后是右子树

        3.post-order后序遍历,对于每一棵子树,先访问左子树,然后是右子树,最后是该节点

本轮开始时队列本轮访问节点
[1]1
[2, 3]2
[3, 4]3
[4, 5, 6]4
[5, 6]5
[6, 7, 8]6
[7, 8]7
[8]8
[]

  1. 初始化，将根节点加入队列

  2. 循环处理队列中每个节点，直至队列为空

  3. 每次循环内处理节点后，将它的孩子节点（即下一层的节点）加入队列

注意

  • 以上用队列来层序遍历是针对 TreeNode 这种方式表示的二叉树

  • 对于数组表现的二叉树，则直接遍历数组即可，自然为层序遍历的顺序

深度优先

 

 递归

  1. public class TreeTraversal {
  2.     public static void main(String[] args) {
  3.         /*
  4.                  1
  5.                 / \
  6.                2   3
  7.               /    /\
  8.              4    5  6
  9.          */
  10.         TreeNode root = new TreeNode(
  11.                 new TreeNode(new TreeNode(4),2,null),
  12.                 1,
  13.                 new TreeNode(new TreeNode(5),3,new TreeNode(6))
  14.         );
  15.         preOrder(root);//1	2	4	3	5	6
  16.         System.out.println();
  17.  
  18.         inOrder(root);//4	2	1	5	3	6
  19.         System.out.println();
  20.  
  21.         PostOrder(root);
  22.         System.out.println();
  23.     }
  24.     /**
  25.      * 前序遍历
  26.      * @Params:node-节点
  27.      */
  28.     static void preOrder(TreeNode node){
  29.         if(node==null){
  30.             return;
  31.         }
  32.         System.out.print(node.val+"\t");//当前节点值
  33.         preOrder(node.left);// 左
  34.         preOrder(node.right);// 右
  35.  
  36.     }
  37.  
  38.     /**
  39.      * 中序遍历
  40.      * @Params:node-节点
  41.      */
  42.     static void inOrder(TreeNode node){
  43.         if(node==null){
  44.             return;
  45.         }
  46.         inOrder(node.left); //左
  47.         System.out.print(node.val+"\t");//值
  48.         inOrder(node.right);//右
  49.     }
  50.  
  51.     /**
  52.      * 后序遍历
  53.      * @Params:node-节点
  54.      */
  55.     static void PostOrder(TreeNode node){
  56.         if(node==null){
  57.             return;
  58.         }
  59.         PostOrder(node.left);
  60.         PostOrder(node.right);
  61.         System.out.print(node.val+"\t");
  62.  
  63.     }
  64. }

非递归

非递归实现

前序遍历 这里的LinkedListStack是自己实现的 也可以用Java自带的LInkedList

  1. LinkedListStack<TreeNode> stack = new LinkedListStack<>();
  2. TreeNode curr = root;
  3. ​
  4. while (!stack.isEmpty() || curr != null) {
  5.     if (curr != null) {
  6.         stack.push(curr);
  7.         System.out.println(curr);
  8.         curr = curr.left;
  9.     } else {
  10.         TreeNode pop = stack.pop();
  11.         curr = pop.right;
  12.     }
  13. ​
  14. }

中序遍历

  1. LinkedListStack<TreeNode> stack = new LinkedListStack<>();
  2. TreeNode curr = root;
  3. ​
  4. while (!stack.isEmpty() || curr != null) {
  5.     if (curr != null) {
  6.         stack.push(curr);
  7.         curr = curr.left;
  8.     } else {
  9.         TreeNode pop = stack.pop();
  10.         System.out.println(pop);
  11.         curr = pop.right;
  12.     }
  13. }

后序遍历

  1. LinkedListStack<TreeNode> stack = new LinkedListStack<>();
  2. TreeNode curr = root;
  3. TreeNode pop = null;
  4. ​
  5. while (!stack.isEmpty() || curr != null) {
  6.     if (curr != null) {
  7.         stack.push(curr);
  8.         curr = curr.left;
  9.     } else {
  10.         TreeNode peek = stack.peek();
  11.         if (peek.right == null || peek.right == pop) {
  12.             pop = stack.pop();
  13.             System.out.println(pop);
  14.         } else {
  15.             curr = peek.right;
  16.         }
  17.     }
  18. }

对于后序遍历，向回走时，需要处理完右子树才能 pop 出栈。如何知道右子树处理完成呢？

  • 如果栈顶元素的 right==null 表示没啥可处理的，可以出栈

  • 如果栈顶元素的right!=null，

    • 那么使用 lastPop 记录最近出栈的节点，即表示从这个节点向回走

    • 如果栈顶元素的 right==lastPop 此时应当出栈

对于前、中两种遍历，实际以上代码从右子树向回走时，并未走完全程（stack 提前出栈了）后序遍历以上代码是走完全程了

统一写法

下面是一种统一的写法，依据后序遍历修改

  1. LinkedList<TreeNode> stack = new LinkedList<>();
  2. ​
  3. TreeNode curr = root; // 代表当前节点
  4. TreeNode pop = null; // 最近一次弹栈的元素
  5. while (curr != null || !stack.isEmpty()) {
  6.     if (curr != null) {
  7.         colorPrintln("前: " + curr.val, 31);
  8.         stack.push(curr); // 压入栈，为了记住回来的路
  9.         curr = curr.left;
  10.     } else {
  11.         TreeNode peek = stack.peek();
  12.         // 右子树可以不处理, 对中序来说, 要在右子树处理之前打印
  13.         if (peek.right == null) {
  14.             colorPrintln("中: " + peek.val, 36);
  15.             pop = stack.pop();
  16.             colorPrintln("后: " + pop.val, 34);
  17.         }
  18.         // 右子树处理完成, 对中序来说, 无需打印
  19.         else if (peek.right == pop) {
  20.             pop = stack.pop();
  21.             colorPrintln("后: " + pop.val, 34);
  22.         }
  23.         // 右子树待处理, 对中序来说, 要在右子树处理之前打印
  24.         else {
  25.             colorPrintln("中: " + peek.val, 36);
  26.             curr = peek.right;
  27.         }
  28.     }
  29. }
  30. ​
  31. public static void colorPrintln(String origin, int color) {
  32.     System.out.printf("\033[%dm%s\033[0m%n", color, origin);
  33. }

将回的代码注释掉那就是一个前序遍历代码

将去的代码注释掉那就是一个中序遍历代码

练习

101. 对称二叉树 - 力扣（LeetCode）

代码实现:

  1. public class E04Leetcode101 {
  2.     public boolean isSymmetric(TreeNode root){
  3.         return check(root.left,root.right);
  4.     }
  5.  
  6.     private boolean check(TreeNode left, TreeNode right) {
  7.         if(left==null&&right==null){
  8.             return true;
  9.         }
  10.         //执行到这里说明:left 和 right不能同时为null
  11.         if(right==null||left==null){
  12.             return false;
  13.         }
  14.         if(left.val!=right.val){
  15.             return false;
  16.         }
  17.         return check(left.left,right.right) && check(left.right,right.left);
  18.  
  19.  
  20.  
  21.     }
  22. }

测试类:

  1. import org.junit.Test;
  2.  
  3. import static org.junit.Assert.assertTrue;
  4.  
  5. public class TestE04Leetcode101 {
  6.     @Test
  7.     public void test1(){
  8.         TreeNode root = new TreeNode(
  9.                 new TreeNode(new TreeNode(3),2,new TreeNode(4)),
  10.                 1,
  11.                 new TreeNode(new TreeNode(4),2,new TreeNode(3))
  12.         );
  13.         assertTrue(new E04Leetcode101().isSymmetric(root));
  14.     }
  15.  
  16.     @Test
  17.     public void test2(){
  18.         TreeNode root = new TreeNode(
  19.                 new TreeNode(null,2,new TreeNode(3)),
  20.                 1,
  21.                 new TreeNode(null,2,new TreeNode(3))
  22.         );
  23.         assertTrue(new E04Leetcode101().isSymmetric(root));
  24.     }
  25. }

104. 二叉树的最大深度 - 力扣（LeetCode）

分析:

  1. /**
  2.  * 二叉树最大深度-使用后序遍历求解
  3.  */
  4. public class Leetcode104_1 {
  5.     /*
  6.         思路:
  7.         1.得到左子树深度,得到右子树深度,二者最大值+1就是本节点深度
  8.         2.因为需要先得到左右子树深度,很显然是后序遍历典型应用
  9.         3.关于深度的定义:从根出发,离根最远的节点总边数
  10.             注意:力扣里的深度定义要多一
  12.             深度2         深度3          深度1
  13.             1              1               1
  14.            / \            / \
  15.           2   3          2   3
  16.                               \
  17.                                4
  18.      */
  19.  
  20.     public int maxDepth(TreeNode node){
  21.          if(node==null){
  22.              return 0;
  23.          }
  24.          if(node.left==null&&node.right==null){
  25.              return 1;
  26.          }
  27.          int d1 = maxDepth(node.left);
  28.          int d2 = maxDepth(node.right);
  29.          return Integer.max(d1,d2)+1;
  30.     }
  31. }

注:上面代码中其实可以把第二个if去掉

第二种解法:

  1. import java.util.LinkedList;
  2.  
  3. /**
  4.  * 二叉树最大深度 - 使用后序遍历(非递归)求解
  5.  */
  6. public class E05Leetcode104_2 {
  7.     /*
  8.         思路:
  9.         1.使用非递归后序遍历,栈的最大高度即为最大深度
  10.      */
  11.     public int maxDepth(TreeNode root){
  12.         TreeNode curr = root;
  13.         TreeNode pop = null;
  14.         LinkedList<TreeNode>stack = new LinkedList<>();
  15.         int max = 0;//栈的最大高度
  16.         while(curr!=null || !stack.isEmpty()){
  17.             if(curr!=null){
  18.                 stack.push(curr);
  19.                 int size = stack.size();
  20.                 if(size>max){
  21.                     max = size;
  22.                 }
  23.                 curr=curr.left;
  24.                 
  25.             }else{
  26.                 TreeNode peek = stack.peek();
  27.                 if(peek.right==null||peek.right==pop){
  28.                     pop=stack.pop();
  29.                 }else{
  30.                     curr=peek.right;
  31.                 }
  32.             }
  33.         }
  34.         return max;
  35.     }
  36. }

第三张方法:

 代码实现:

  1. public class E05Leetcode104_3 {
  2.     /*
  3.         思路:
  4.         1.使用层序遍历,层数即最大深度
  5.      */
  6.     public int maxDepth(TreeNode root){
  7.         Queue<TreeNode> queue= new LinkedList<>();
  8.         //LinkedList:可以作为双向链表,队列,栈  "身兼数职"
  9.         queue.offer(root);
  10.         int depth=0;
  11. //        int c1=1;//记录每层有几个元素
  12.         while(!queue.isEmpty()){
  13.             //queue.size()
  14. //            int c2=0;
  15.             int size = queue.size();
  16.             for(int i=0;i<size;i++){
  17.                 TreeNode poll = queue.poll();
  18. //                System.out.print(poll.val+"\t");
  19.                 if(poll.left!=null){
  20.                     queue.offer(poll.left);
  21. //                    c2++;
  22.                 }
  23.                 if(poll.right!=null){
  24.                     queue.offer(poll.right);
  25. //                    c2++;
  26.                 }
  27.             }
  28. //            c1=c2;
  29. //            System.out.println();
  30.             depth++;
  31.  
  32.         }
  33.         return depth;
  34.  
  35.     }
  36.  
  37. }
  1. if(root==null){
  2.     return 0;
  3. }
  4. //有可能传过来的是null

111. 二叉树的最小深度 - 力扣（LeetCode）

  1. class Solution {
  2.     public int minDepth(TreeNode root) {
  3.         if(root==null)return 0;
  4.         int m1 = minDepth(root.left);
  5.         int m2 = minDepth(root.right);
  6.         return root.left==null||root.right==null?m1+m2+1:Math.min(m1,m2)+1;
  7.     }
  8. }
  1. class Solution {
  2.     public int minDepth(TreeNode root){
  3.         if(root == null){
  4.             return 0;
  5.         }
  6.         Queue<TreeNode>queue = new LinkedList<>();
  7.         queue.offer(root);
  8.         int depth = 0;
  9.         while(!queue.isEmpty()){
  10.             int size = queue.size();
  11.             depth++;
  12.             for(int i=0;i<size;i++){
  13.  
  14.                 TreeNode poll = queue.poll();
  15.                 if(poll.right==null&&poll.left==null){
  16.                     return depth;
  17.                 }
  18.                 if(poll.left!=null){
  19.                     queue.offer(poll.left);
  20.                 }
  21.                 if(poll.right!=null){
  22.                     queue.offer(poll.right);
  23.                 }
  24.             }
  25.  
  26.         }
  27.         return depth;
  28.     }
  29. }

226. 翻转二叉树 - 力扣（LeetCode）

  1. class Solution {
  2.     public TreeNode invertTree(TreeNode root) {
  3.         fn(root);
  4.         return root;
  5.     }
  6.     private void fn(TreeNode node){
  7.         if(node==null){
  8.             return;
  9.         }
  10.         TreeNode t = node.left;
  11.         node.left = node.right;
  12.         node.right = t;
  13.         fn(node.left);
  14.         fn(node.right);
  15.  
  16.     }
  17. }

  1. import java.util.LinkedList;
  2.  
  3. /**
  4.  * 根据后缀表达式构造表达式树
  5.  */
  6. public class ExpressionTree {
  7.  
  8.     public static class TreeNode {
  9.         public String val;
  10.         public TreeNode left;
  11.         public TreeNode right;
  12.  
  13.         public TreeNode(String val) {
  14.             this.val = val;
  15.         }
  16.  
  17.         public TreeNode(TreeNode left, String val, TreeNode right) {
  18.             this.val = val;
  19.             this.left = left;
  20.             this.right = right;
  21.         }
  22.  
  23.         @Override
  24.         public String toString() {
  25.             return this.val;
  26.         }
  27.     }
  28.  
  29.     /*
  30.         中缀表达式  (2-1)*3
  31.         后缀(逆波兰)表达式  21-3*
  33.         1.遇到数字入栈
  34.         2.遇到运算符出栈,建立节点关系,再入栈
  36.         栈
  37.         /   /
  38.         /   /
  39.         /   /
  40.         ----
  41.         '-'.right = 1
  42.         '-'.left = 2
  44.         '*' .right = 3
  45.         '*' .left = '-'
  47.         表达式树
  48.         *
  49.        / \
  50.       -   3
  51.      / \
  52.     2   1
  53.      */
  54.     public TreeNode constructExpressionTree(String[] tokens) {
  55.         LinkedList<TreeNode> stack = new LinkedList<>();
  56.         for (String t : tokens) {
  57.             switch (t) {
  58.                 case "+", "-", "*", "/" -> {//运算符
  59.                     TreeNode right = stack.pop();
  60.                     TreeNode left = stack.pop();
  61.                     TreeNode parent = new TreeNode(t);
  62.                     parent.left = left;
  63.                     parent.right = right;
  64.                     stack.push(parent);
  65.                 }
  66.                 default -> {//数字
  67.                     stack.push(new TreeNode(t));
  68.                 }
  69.             }
  70.         }
  71.         return stack.peek();
  72.         //做个后序遍历 检测
  73.     }
  74. }
  1. import Tree.ExpressionTree;
  2. import org.junit.Test;
  3. import java.util.ArrayList;
  4. import static org.junit.Assert.assertArrayEquals;
  5.  
  6. public class TestExpressionTree {
  7.     ExpressionTree exp = new ExpressionTree();
  8.  
  9.     @Test
  10.     public void test1(){
  11.         String[] tokens = {"2","1","-","3","*"};
  12.         ExpressionTree.TreeNode root = exp.constructExpressionTree(tokens);
  13.         ArrayList<String>result = new ArrayList<>();
  14.         post(root,result);
  15.         assertArrayEquals(tokens,result.toArray(new String[0]));
  16.     }
  17.  
  18.     private void post(ExpressionTree.TreeNode node,ArrayList<String>result){
  19.         if(node==null){
  20.             return;
  21.         }
  22.         post(node.left,result);
  23.         post(node.right,result);
  24.         result.add(node.val);
  25.     }
  26. }

105. 从前序与中序遍历序列构造二叉树 - 力扣（LeetCode）

  1. import java.util.Arrays;
  2.  
  3. /**
  4.  * 根据前中序遍历结果构造二叉树
  5.  */
  6. public class Leetocde105 {
  7.     /*
  8.         preOrder = {1,2,4,3,6,7};
  9.         inOrder = {4,2,1,6,3,7};
  11.         根1
  12.             pre     in
  13.         左 2 4     4,2
  14.         右 3,6,7   6,3,7
  16.         根 2
  17.         左 4
  19.         根 3
  20.         左 6
  21.         右 7
  23.      */
  24.  
  25.     public TreeNode buildTree(int[] preOrder,int[] inOrder){
  26.         if(preOrder.length==0||inOrder.length==0){
  27.             return null;
  28.         }
  29.         //创建根节点
  30.         int rootValue = preOrder[0];
  31.         TreeNode root = new TreeNode(rootValue);
  32.         //区分左右子树
  33.         for (int i = 0; i < inOrder.length; i++) {
  34.             if(inOrder[i]==rootValue){
  35.                 //0 ~ i-1  左子树
  36.                 //i+1 ~ inOrder.length-1 右子树
  37.                 int[] inLeft = Arrays.copyOfRange(inOrder, 0, i);//i是不包含的 [4,2]
  38.                 int[] inRight= Arrays.copyOfRange(inOrder, i, inOrder.length);//[6,3,7]
  39.  
  40.                 int[] preLeft = Arrays.copyOfRange(preOrder, 1, i + 1);//[2,4]
  41.                 int[] preRight = Arrays.copyOfRange(preOrder, i+1, inOrder.length);//[3,6,7]
  42.  
  43.                 root.left = buildTree(preLeft,inLeft); //2
  44.                 root.right = buildTree(preRight,inRight);//3
  45.                 break;
  46.  
  47.             }
  48.             
  49.         }
  50.         return root;
  51.     }
  52. }

参考力扣题解:

  1. 可以将中序遍历的值和索引存在一个哈希表中，这样就可以一下子找到根结点在中序遍历数组中的索引。
  2.  
  3. Java
  4. import java.util.HashMap;
  5. import java.util.Map;
  6.  
  7. class TreeNode {
  8.     int val;
  9.     TreeNode left;
  10.     TreeNode right;
  11.  
  12.     TreeNode(int x) {
  13.         val = x;
  14.     }
  15. }
  16.  
  17. public class Solution {
  18.  
  19.     private int[] preorder;
  20.     private Map<Integer, Integer> hash;
  21.  
  22.     public TreeNode buildTree(int[] preorder, int[] inorder) {
  23.         int preLen = preorder.length;
  24.         int inLen = inorder.length;
  25.         if (preLen != inLen) {
  26.             throw new RuntimeException("Incorrect input data.");
  27.         }
  28.         this.preorder = preorder;
  29.         this.hash = new HashMap<>();
  30.         for (int i = 0; i < inLen; i++) {
  31.             hash.put(inorder[i], i);
  32.         }
  33.  
  34.         return buildTree(0, preLen - 1, 0, inLen - 1);
  35.     }
  36.  
  37.  
  38.     private TreeNode buildTree(int preLeft, int preRight, int inLeft, int inRight) {
  39.         // 因为是递归调用的方法，按照国际惯例，先写递归终止条件
  40.         if (preLeft > preRight || inLeft > inRight) {
  41.             return null;
  42.         }
  43.         // 先序遍历的起点元素很重要
  44.         int pivot = preorder[preLeft];
  45.         TreeNode root = new TreeNode(pivot);
  46.         int pivotIndex = hash.get(pivot);
  47.         root.left = buildTree(preLeft + 1, pivotIndex - inLeft + preLeft,
  48.                 inLeft, pivotIndex - 1);
  49.         root.right = buildTree(pivotIndex - inLeft + preLeft + 1, preRight,
  50.                 pivotIndex + 1, inRight);
  51.         return root;
  52.     }
  53. }
  54. 复杂度分析：
  55.  
  56. 时间复杂度：O(N)O(N)O(N)，这里 NNN 是二叉树的结点个数，每调用一次递归方法创建一个结点，一共创建 NNN 个结点，这里不计算递归方法占用的时间。
  57. 空间复杂度：O(N)O(N)O(N)，这里忽略递归方法占用的空间，因为是对数级别的，比 NNN 小。
  58.  
  59. 作者：liweiwei1419
  60. 链接：https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/solutions/8946/qian-xu-bian-li-python-dai-ma-java-dai-ma-by-liwei/
  61. 来源：力扣（LeetCode）
  62. 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

106. 从中序与后序遍历序列构造二叉树 - 力扣（LeetCode）

  1. class Solution {
  2.     public TreeNode buildTree(int[] inorder, int[] postorder) {
  3.         if(inorder.length==0||postorder.length==0){
  4.             return null;
  5.         }
  6.         int rootValue = postorder[postorder.length-1];
  7.         TreeNode root = new TreeNode(rootValue);
  8.         for(int i=0;i<inorder.length;i++){
  9.             if(inorder[i] == rootValue){
  10.                 int[] inLeft = Arrays.copyOfRange(inorder,0,i);
  11.                 int[] inRight =Arrays.copyOfRange(inorder,i+1,inorder.length);
  12.  
  13.                 int[] postLeft = Arrays.copyOfRange(postorder,0,i);
  14.                 int[] postRight = Arrays.copyOfRange(postorder,i,postorder.length-1);
  15.  
  16.                 root.left = buildTree(inLeft,postLeft);
  17.                 root.right = buildTree(inRight,postRight);
  18.             }
  19.         }
  20.         return root;
  21.     }
  22. }

在我们之前所学的数据结构中我们要查找一个元素,时间复杂度都是O(n) 如果我们想提高查找效率就要引入新的数据结构和算法了

之前学过二分查找

O(logN) 但是这个算法它必须是排好序的 但排序消耗的时间复杂度也是比较高的可能会得不偿失

那么我引入这个新的数据结构叫:

二叉搜索树

平均复杂度是对数时间,但是最糟糕情况是O(n)

get方法的实现

  1. /**
  2.  * Binary Search Tree 二叉搜索树
  3.  */
  4. public class BSTTree1 {
  5.     BSTNode root;//根节点
  6.    static class BSTNode {
  7.         int key;
  8.         Object value;
  9.         BSTNode left;
  10.         BSTNode right;
  11.  
  12.         public BSTNode(int key){
  13.             this.key = key;
  14.  
  15.         }
  16.  
  17.        public BSTNode(int key, Object value) {
  18.            this.key = key;
  19.            this.value = value;
  20.        }
  21.  
  22.        public BSTNode(int key, Object value, BSTNode left, BSTNode right){
  23.             this.key = key;
  24.             this.value = value;
  25.             this.left = left;
  26.             this.right = right;
  27.         }
  28.    }
  29.  
  30.     /**
  31.      * <h3>查找关键字对应的值</h3>
  32.      * @param:key-关键字
  33.      * @return:关键字对应的值
  34.      */
  35.    public Object get(int key){
  36.  
  37.        return doGet(root,key);
  38.    }
  39.   //递归版本
  40.  
  41.   //尾递归 最后一步调用自身的时候(不含任何其他数) 转换成非递归实现性能更好 因为java不会对尾递归进行优化
  42.  
  43.    private Object doGet(BSTNode node,int key){
  44.        if(node == null){
  45.            return null;//没有找到
  46.        }
  47.        if(key<node.key){
  48.            return doGet(node.left,key);//向左找
  49.        }else if(node.key < key){
  50.            return doGet(node.right,key);//向右找
  51.        }else{
  52.            return node.value;//找到了
  53.        }
  54.    }
  55.  
  56.  
  57.     //非递归版本
  58.    public Object get(int key){
  59.         BSTNode node =root;
  60.         while(node!=null){
  61.             if(key<node.key){
  62.                 node = node.left;
  63.             }else if(key>node.key){
  64.                 node = node.right;
  65.             }else{
  66.                 return node.value;
  67.             }
  68.         }
  69.         return null;
  70.    }

也可以用泛型实现更一般的方法:

  1. /*
  2. //泛型有没有比较大小的能力呢? 泛型中也有一个语法叫做泛型上限
  3. 将来我的泛型必须是Comparable的子类型
  4.  */
  5. public class BSTNode2<T extends Comparable<T>,V> {
  6.     static class BSTNode<T,V> {
  7.         T key;
  8.         V value;
  9.         BSTNode<T,V> left;
  10.         BSTNode<T,V> right;
  11.  
  12.         public BSTNode(T key){
  13.             this.key = key;
  14.         }
  15.  
  16.         public BSTNode(T key, V value) {
  17.             this.key = key;
  18.             this.value = value;
  19.         }
  20.  
  21.         public BSTNode(T key, V value, BSTNode<T,V> left, BSTNode<T,V> right){
  22.             this.key = key;
  23.             this.value = value;
  24.             this.left = left;
  25.             this.right = right;
  26.         }
  27.     }
  28.  
  29.     BSTNode<T,V> root;
  30.  
  31.  
  32.     /**
  33.      * <h3>查找关键字对应的值</h3>
  34.      * @param:key-关键字
  35.      * @return:关键字对应的值
  36.      */
  37.     public V get(T key){
  38.         BSTNode<T,V> p =root;
  39.         while(p!=null){
  40.             //key p.key
  41.             /*
  42.             -1 : key<p.key
  43.             0  : key=p.key
  44.             1  : key>p.key
  45.              */
  46.             int result = key.compareTo(p.key);
  47.             if(result<0){
  48.                 p = p.left;
  49.             }else if (result>0){
  50.                 p = p.right;
  51.             }else{
  52.                 return p.value;
  53.             }
  54.         }
  55.         return null;
  56.     }

min-max的实现

  1.     /**
  2.      * <h3>查找最小关键字对应值</h3>
  3.      * @Returns:关键字对应的值
  4.      */
  5. //    public Object min(){
  6. //        return  doMin(root);
  7. //    }
  8.  
  9.     public Object min(){
  10.         if(root==null){
  11.             return null;
  12.         }
  13.         BSTNode P = root;
  14.         while(P.left!=null){
  15.             P = P.left;
  16.         }
  17.         return P.value;
  18.     }
  19.  
  20.     public Object doMin(BSTNode node){
  21.         if(node==null){
  22.             return null;
  23.         }
  24.         if(node.left == null){//找到了最小的节点
  25.             return node.value;
  26.         }
  27.         return doMin(node.left);//尾递归
  28.     }
  29.  
  30.     /**
  31.      * <h3>查找最大关键字对应值</h3>
  32.      * @return:关键字对应值
  33.      */
  34.     public Object max(){
  35.         if(root==null){
  36.             return null;
  37.         }
  38.         BSTNode p = root;
  39.         while(p.right!=null){
  40.             p = p.right;
  41.         }
  42.         return p.value;
  43.     }

put的实现 --和java map集合非常相似

  1. /**
  2.      * <h3>存储关键字和对应值</h3>
  3.      * @param:key 关键字
  4.      * @param:value 值
  5.      */
  6.     public void put(int key,Object value){
  7.         //1.key 有  更新
  8.         //2.key 没有 更新
  9.         BSTNode node = root;
  10.         BSTNode parent =null;
  11.         while(node!=null){
  12.             parent = node;
  13.             if(key <node.key){
  14.                 node = node.left;
  15.             }else if(node.key<key){
  16.                 node=node.right;
  17.             }else{
  18.                 //1
  19.                 node.value = value;
  20.                 return;
  21.             }
  22.         }
  23.         if(parent == null){//树为空
  24.             root = new BSTNode(key,value);
  25.             return;
  26.         }
  27.         //2
  28. //        new BSTNode(key,value);
  29.         if(key< parent.key){
  30.             parent.left = new BSTNode(key,value);
  31.         }else if(key> parent.key){//也可以直接改为else即可
  32.             parent.right = new BSTNode(key,value);
  33.         }
  34.     }

前驱&后继

  1. /**
  2.      * <h3>查找关键字的前驱值</h3>
  3.      * @param:key-关键字
  4.      * @return:前驱值
  5.      */
  6.     //中序遍历结果就是升序的结果
  7.     //但是我们实际去实现的时候并不会采用中序遍历 因为性能不高 最坏的情况两个指针要把整个树走一次
  8.     /*
  9.     前人的经验:
  10.         分为有左子树时,此时前驱节点就是左子树的最大值,图中属于这种情况的有
  11.           没有左子树时,若离它最近的祖先从左而来,此时祖先为前驱
  12.      */
  13.     public Object successor(int key) {
  14.         BSTNode p = root;
  15.         BSTNode ancestorFromLeft = null;
  16.         while(p!=null){
  17.             if(p.key < key){
  18.                 ancestorFromLeft = p;
  19.                 p = p.right;
  20.             }else if(p.key > key){
  21.                 p = p.left;
  22.             }else{
  23.                 break;
  24.             }
  25.         }
  26.         //没找到节点的情况
  27.         if(p==null){
  28.             return null;
  29.         }
  30.         //找到节点
  31.         if(p.left!=null){
  32.             return max(p.left);
  33.         }
  34.         //情况二:节点没有左子树(自左而来)
  35.         return ancestorFromLeft!=null?ancestorFromLeft.value:null;
  36.     }

在这里也修改了一下max的代码

  1.     /**
  2.      * <h3>查找最大关键字对应值</h3>
  3.      * @return:关键字对应值
  4.      */
  5.     public Object max(){
  6.         return max(root);
  7.     }
  8.     //写的更通用 方便找前驱等使用
  9.     private Object max(BSTNode node){
  10.         if(node==null){
  11.             return null;
  12.         }
  13.         BSTNode p = node;
  14.         while(p.right!=null){
  15.             p = p.right;
  16.         }
  17.         return p.value;
  18.     }

后继

  1.    /**
  2.      * <h3>查找关键字的后继值</h3>
  3.      * @param:key-关键字
  4.      * @return:后继值
  5.      */
  6.     public Object predecessor(int key){
  7.         BSTNode p = root;
  8.         BSTNode ancestorFromRight = null;
  9.         while(p!=null){
  10.             if(p.key < key){
  11.                 p = p.right;
  12.             }else if(p.key > key){
  13.                 ancestorFromRight = p;
  14.                 p = p.left;
  15.             }else{
  16.                 break;
  17.             }
  18.         }
  19.         //没找到节点的情况
  20.         if(p==null){
  21.             return null;
  22.         }
  23.         //找到节点
  24.         if(p.right!=null){
  25.             return min(p.right);
  26.         }
  27.         //情况二:节点没有右子树(自右而来)
  28.         return ancestorFromRight!=null?ancestorFromRight.value:null;
  29.  
  30.     }
  1. public Object min(){
  2.  
  3.         return min(root);
  4.     }
  5.     private Object min(BSTNode node){
  6.         if(node==null){
  7.             return null;
  8.         }
  9.         BSTNode P = node;
  10.         while(P.left!=null){
  11.             P = P.left;
  12.         }
  13.         return P.value;
  14.     }

删除delete

第一种情况:没有左孩子

 情况二:没有右孩子

  1.     /**
  2.      * <h3>根据关键字删除</h3>
  3.      * @param:key-关键字
  4.      * @return:被删除关键字对应值
  5.      */
  6.     public Object delete(int key){
  7.         //先找到节点
  8.         BSTNode parent =null;//记录待删除节点的父亲
  9.         BSTNode p = root;
  10.         while(p!=null){
  11.             if(key<p.key){
  12.                 parent = p;
  13.                 p = p.left;
  14.             }else if(p.key < key){
  15.                 parent = p;
  16.                 p = p.right;
  17.             }else{
  18.                 break;
  19.             }
  20.         }
  21.         if(p==null){
  22.             return null;
  23.         }
  24.         //找到了进行删除操作
  25.         if(p.left==null && p.right!=null){
  26.             //情况一:
  27.             shift(parent,p,p.right);
  28.         }else if(p.right==null&&p.left!=null){
  29.             //情况二:
  30.             shift(parent,p,p.left);
  31.         }
  32.         return p.value;
  33.     }
  34.  
  35.     /**
  36.      * 托孤方法
  37.      * @param parent-被删除节点的父亲
  38.      * @param deleted-被删除节点
  39.      * @param child-被顶上去的节点
  40.      */
  41.     private void shift(BSTNode parent,BSTNode deleted,BSTNode child){
  42.         if(parent==null){
  43.             root = child;
  44.         }else if(deleted==parent.left){
  45.             parent.left = child;
  46.         }else{
  47.             parent.right =child;
  48.         }
  49.     }

情况三:直接走情况一或者情况二的逻辑即可 直接将if 和 else if && 后面那部分删了即可 

情况四: 后继相邻 & 后继不相邻(后继要先处理自己的后事)

  1. public Object delete(int key){
  2.         //先找到节点
  3.         BSTNode parent =null;//记录待删除节点的父亲
  4.         BSTNode p = root;
  5.         while(p!=null){
  6.             if(key<p.key){
  7.                 parent = p;
  8.                 p = p.left;
  9.             }else if(p.key < key){
  10.                 parent = p;
  11.                 p = p.right;
  12.             }else{
  13.                 break;
  14.             }
  15.         }
  16.         if(p==null){
  17.             return null;
  18.         }
  19.         //找到了进行删除操作
  20.         if(p.left==null){
  21.             //情况一:
  22.             shift(parent,p,p.right);
  23.         }else if(p.right==null){
  24.             //情况二:
  25.             shift(parent,p,p.left);
  26.         }else{//情况四
  27.             //4.1被删除节点的后继节点
  28.             BSTNode s = p.right;
  29.             BSTNode sParent=p;//后继父亲
  30.             while(s.left!=null){
  31.                 sParent = s;
  32.                 s= s.left;
  33.             }
  34.             //后继节点即为s
  35.             if(sParent!=p){
  36.                 //说明不相邻
  37.                 4.2删除节点和后继节点不相邻,要处理后继的后事
  38.                 shift(sParent,s,s.right);//不可能有左孩子 因为是后继
  39.                 s.right = p.right;
  40.             }
  41.             //4.3后继取代被删除节点
  42.             shift(parent,p,s);
  43.             s.left = p.left;
  44.  
  45.         }
  46.         return p.value;
  47.     }

整体代码:

  1. /**
  2.  * Binary Search Tree 二叉搜索树
  3.  */
  4. public class BSTTree1 {
  5.     BSTNode root;//根节点
  6.    static class BSTNode {
  7.         int key;
  8.         Object value;
  9.         BSTNode left;
  10.         BSTNode right;
  11.  
  12.         public BSTNode(int key){
  13.             this.key = key;
  14.  
  15.         }
  16.  
  17.        public BSTNode(int key, Object value) {
  18.            this.key = key;
  19.            this.value = value;
  20.        }
  21.  
  22.        public BSTNode(int key, Object value, BSTNode left, BSTNode right){
  23.             this.key = key;
  24.             this.value = value;
  25.             this.left = left;
  26.             this.right = right;
  27.         }
  28.    }
  29.  
  30.     /**
  31.      * <h3>查找关键字对应的值</h3>
  32.      * @param:key-关键字
  33.      * @return:关键字对应的值
  34.      */
  35.  
  36.     //非递归版本
  37.    public Object get(int key){
  38.         BSTNode node =root;
  39.         while(node!=null){
  40.             if(key<node.key){
  41.                 node = node.left;
  42.             }else if(key>node.key){
  43.                 node = node.right;
  44.             }else{
  45.                 return node.value;
  46.             }
  47.         }
  48.         return null;
  49.    }
  50.     /**
  51.      * <h3>查找最小关键字对应值</h3>
  52.      * @Returns:关键字对应的值
  53.      */
  54. //    public Object min(){
  55. //        return  doMin(root);
  56. //    }
  57.  
  58.     public Object min(){
  59.  
  60.         return min(root);
  61.     }
  62.     private Object min(BSTNode node){
  63.         if(node==null){
  64.             return null;
  65.         }
  66.         BSTNode P = node;
  67.         while(P.left!=null){
  68.             P = P.left;
  69.         }
  70.         return P.value;
  71.     }
  72.  
  73.     public Object doMin(BSTNode node){
  74.         if(node==null){
  75.             return null;
  76.         }
  77.         if(node.left == null){//找到了最小的节点
  78.             return node.value;
  79.         }
  80.         return doMin(node.left);//尾递归
  81.     }
  82.  
  83.     /**
  84.      * <h3>查找最大关键字对应值</h3>
  85.      * @return:关键字对应值
  86.      */
  87.     public Object max(){
  88.         return max(root);
  89.     }
  90.     //写的更通用 方便找前驱等使用
  91.     private Object max(BSTNode node){
  92.         if(node==null){
  93.             return null;
  94.         }
  95.         BSTNode p = node;
  96.         while(p.right!=null){
  97.             p = p.right;
  98.         }
  99.         return p.value;
  100.     }
  101.  
  102.     /**
  103.      * <h3>存储关键字和对应值</h3>
  104.      * @param:key 关键字
  105.      * @param:value 值
  106.      */
  107.     public void put(int key,Object value){
  108.         //1.key 有  更新
  109.         //2.key 没有 更新
  110.         BSTNode node = root;
  111.         BSTNode parent =null;
  112.         while(node!=null){
  113.             parent = node;
  114.             if(key <node.key){
  115.                 node = node.left;
  116.             }else if(node.key<key){
  117.                 node=node.right;
  118.             }else{
  119.                 //1
  120.                 node.value = value;
  121.                 return;
  122.             }
  123.         }
  124.         if(parent == null){//树为空
  125.             root = new BSTNode(key,value);
  126.             return;
  127.         }
  128.         //2
  129. //        new BSTNode(key,value);
  130.         if(key< parent.key){
  131.             parent.left = new BSTNode(key,value);
  132.         }else if(key> parent.key){//也可以直接改为else即可
  133.             parent.right = new BSTNode(key,value);
  134.         }
  135.     }
  136.  
  137.     /**
  138.      * <h3>查找关键字的前驱值</h3>
  139.      * @param:key-关键字
  140.      * @return:前驱值
  141.      */
  142.     //中序遍历结果就是升序的结果
  143.     //但是我们实际去实现的时候并不会采用中序遍历 因为性能不高 最坏的情况两个指针要把整个树走一次
  144.     /*
  145.     前人的经验:
  146.         分为有左子树时,此时前驱节点就是左子树的最大值,图中属于这种情况的有
  147.           没有左子树时,若离它最近的祖先从左而来,此时祖先为前驱
  148.      */
  149.     public Object successor(int key) {
  150.         BSTNode p = root;
  151.         BSTNode ancestorFromLeft = null;
  152.         while(p!=null){
  153.             if(p.key < key){
  154.                 ancestorFromLeft = p;
  155.                 p = p.right;
  156.             }else if(p.key > key){
  157.                 p = p.left;
  158.             }else{
  159.                 break;
  160.             }
  161.         }
  162.         //没找到节点的情况
  163.         if(p==null){
  164.             return null;
  165.         }
  166.         //找到节点
  167.         if(p.left!=null){
  168.             return max(p.left);
  169.         }
  170.         //情况二:节点没有左子树(自左而来)
  171.         return ancestorFromLeft!=null?ancestorFromLeft.value:null;
  172.     }
  173.  
  174.     /**
  175.      * <h3>查找关键字的后继值</h3>
  176.      * @param:key-关键字
  177.      * @return:后继值
  178.      */
  179.     public Object predecessor(int key){
  180.         BSTNode p = root;
  181.         BSTNode ancestorFromRight = null;
  182.         while(p!=null){
  183.             if(p.key < key){
  184.                 p = p.right;
  185.             }else if(p.key > key){
  186.                 ancestorFromRight = p;
  187.                 p = p.left;
  188.             }else{
  189.                 break;
  190.             }
  191.         }
  192.         //没找到节点的情况
  193.         if(p==null){
  194.             return null;
  195.         }
  196.         //找到节点
  197.         if(p.right!=null){
  198.             return min(p.right);
  199.         }
  200.         //情况二:节点没有右子树(自右而来)
  201.         return ancestorFromRight!=null?ancestorFromRight.value:null;
  202.  
  203.     }
  204.  
  205.     /**
  206.      * <h3>根据关键字删除</h3>
  207.      * @param:key-关键字
  208.      * @return:被删除关键字对应值
  209.      */
  210.     public Object delete(int key){
  211.         //先找到节点
  212.         BSTNode parent =null;//记录待删除节点的父亲
  213.         BSTNode p = root;
  214.         while(p!=null){
  215.             if(key<p.key){
  216.                 parent = p;
  217.                 p = p.left;
  218.             }else if(p.key < key){
  219.                 parent = p;
  220.                 p = p.right;
  221.             }else{
  222.                 break;
  223.             }
  224.         }
  225.         if(p==null){
  226.             return null;
  227.         }
  228.         //找到了进行删除操作
  229.         if(p.left==null){
  230.             //情况一:
  231.             shift(parent,p,p.right);
  232.         }else if(p.right==null){
  233.             //情况二:
  234.             shift(parent,p,p.left);
  235.         }else{//情况四
  236.             //4.1被删除节点的后继节点
  237.             BSTNode s = p.right;
  238.             BSTNode sParent=p;//后继父亲
  239.             while(s.left!=null){
  240.                 sParent = s;
  241.                 s= s.left;
  242.             }
  243.             //后继节点即为s
  244.             if(sParent!=p){
  245.                 //说明不相邻
  246.                 4.2删除节点和后继节点不相邻,要处理后继的后事
  247.                 shift(sParent,s,s.right);//不可能有左孩子 因为是后继
  248.                 s.right = p.right;
  249.             }
  250.             //4.3后继取代被删除节点
  251.             shift(parent,p,s);
  252.             s.left = p.left;
  253.  
  254.         }
  255.         return p.value;
  256.     }
  257.  
  258.     /**
  259.      * 托孤方法
  260.      * @param parent-被删除节点的父亲
  261.      * @param deleted-被删除节点
  262.      * @param child-被顶上去的节点
  263.      */
  264.     private void shift(BSTNode parent,BSTNode deleted,BSTNode child){
  265.         if(parent==null){
  266.             root = child;
  267.         }else if(deleted==parent.left){
  268.             parent.left = child;
  269.         }else{
  270.             parent.right =child;
  271.         }
  272.     }
  273. }

递归实现delete

    

  1.  /**
  2.      * <h3>根据关键字删除</h3>
  3.      *
  4.      * @param:key-关键字
  5.      * @return:被删除关键字对应值
  6.      */
  7.     public Object delete(int key) {
  8.         ArrayList<Object>result = new ArrayList<>();//保存被删除节点的值
  9.         root = doDelete(root,key,result);
  10.         return result.isEmpty()?null:result.get(0);
  11.     }
  12.  
  13.     /*
  14.     递归版
  15.     1.删除节点没有左孩子,将右孩子托孤给Parent
  16.     2.删除节点没有右孩子,将左孩子托孤给Parent
  17.     3.删除节点左右孩子都没有,已经被涵盖在情况一,情况二当中,把null托孤给Parent
  18.     4.删除左右节点孩子都有,可以把它的后继节点(称之为S)托孤给parent
  19.             4
  20.            / \
  21.           2   6
  22.          /     \
  23.         1       7
  24.         node : 起点
  25.         返回值: 删剩下的孩子节点 或 null
  26.      */
  27.     private BSTNode doDelete(BSTNode node, int key,ArrayList<Object>result) {
  28.         if (node == null) {
  29.             return null;
  30.         }
  31.         if (key < node.key) {
  32.             node.left = doDelete(node.left, key,result);//假如要删除2 那么返回1
  33.             return node;
  34.         }
  35.         if (node.key < key) {
  36.             node.right = doDelete(node.right, key,result);
  37.             return node;
  38.         }
  39.         //找到了
  40.         result.add(node.value);
  41.         //情况1: 只有右孩子
  42.         if (node.left == null) {
  43.             return node.right;//返回的就是删剩下的东西
  44.         }
  45.         //情况2: 只有左孩子
  46.         if (node.right == null) {
  47.             return node.left;//返回的就是删剩下的东西
  48.         }
  49.         //情况3: 两个孩子都有
  50.         BSTNode s = node.right;///后继节点
  51.         while (s.left != null) {
  52.             s = s.left;
  53.         }
  54.         s.right = doDelete(node.right, s.key,new ArrayList<>());//反正这个new的用不上 因为是删除后继节点的
  55.         s.left = node.left;
  56.         return s;
  57.     }

范围查询

  1. /*
  2.     范围查询
  3.      */
  4.  
  5.     //中序遍历-->升序
  6.     /*
  7.             4
  8.            / \
  9.           2   6
  10.          / \  /\
  11.         1  3  5 7
  13.      */
  14.  
  15.     //找 < key 的所有value
  16.     public List<Object>less(int key){ //key = 6
  17.         ArrayList<Object>result = new ArrayList<>();
  18.         BSTNode p = root;
  19.         LinkedList<BSTNode> stack = new LinkedList<>();
  20.         while(p!=null||!stack.isEmpty()){
  21.             if(p!=null){
  22.                 stack.push(p);
  23.                 p=p.left;
  24.             }else{
  25.                 BSTNode pop = stack.pop();
  26.                 //处理值
  27.                 if(pop.key<key){
  28.                     result.add(pop.value);
  29.                 }else{
  30.                     break;
  31.                 }
  32.                 p = pop.right;
  33.             }
  34.         }
  35.         return result;
  36.     }
  37.  
  38.  
  39.  
  40.     //找>key的所有value
  41.     /*
  42.     Pre-order,NLR
  43.     In-order,LNR
  44.     Post-order,LRN
  45.     Reverse Pre-order,NRL
  46.     Reverse In-order,RNL
  47.     Reverse post-order,RLN
  48.      */
  49.     public List<Object>greater(int key){ //优化 从后开始 反向中序遍历
  50. //        ArrayList<Object>result = new ArrayList<>();
  51. //        BSTNode p = root;
  52. //        LinkedList<BSTNode> stack = new LinkedList<>();
  53. //        while(p!=null||!stack.isEmpty()){
  54. //            if(p!=null){
  55. //                stack.push(p);
  56. //                p=p.left;
  57. //            }else{
  58. //                BSTNode pop = stack.pop();
  59. //                //处理值
  60. //                if (key<pop.key){
  61. //                    result.add(pop.value);
  62. //                }
  63. //                //不能提前结束 因为ta要把全部走一次
  64. //                p = pop.right;
  65. //
  66. //
  67. //            }
  68. //        }
  69. //        return result;
  70.  
  71.  
  72.         ArrayList<Object>result = new ArrayList<>();
  73.         BSTNode p = root;
  74.         LinkedList<BSTNode> stack = new LinkedList<>();
  75.         while(p!=null||!stack.isEmpty()){
  76.             if(p!=null){
  77.                 stack.push(p);
  78.                 p=p.right;
  79.             }else{
  80.                 BSTNode pop = stack.pop();
  81.                 //处理值
  82.                 if (key<pop.key){
  83.                     result.add(pop.value);
  84.                 }
  85.                 else{
  86.                     break;
  87.                 }
  88. //                System.out.println(pop.value);//逆序
  89.  
  90.                 p = pop.left;
  91.  
  92.  
  93.             }
  94.         }
  95.         return result;
  96.     }
  97.  
  98.     //找>=key1||<=key2的所有值
  99.     public List<Object>between(int key1,int key2){
  100.         ArrayList<Object>result = new ArrayList<>();
  101.         BSTNode p = root;
  102.         LinkedList<BSTNode> stack = new LinkedList<>();
  103.         while(p!=null||!stack.isEmpty()){
  104.             if(p!=null){
  105.                 stack.push(p);
  106.                 p=p.left;
  107.             }else{
  108.                 BSTNode pop = stack.pop();
  109.                 //处理值
  110.                 if(pop.key>=key1 && pop.key<=key2){
  111.                     result.add(pop.value);
  112.                 }else if(pop.key>key2){
  113.                     break;
  114.                 }
  115.                 p = pop.right;
  116.             }
  117.         }
  118.         return result;
  119.     }

二叉搜索树练习

上面实现写过的就不做实现了.

删除节点-力扣450题

450. 删除二叉搜索树中的节点 - 力扣（LeetCode）

  • 当然要注意的是:题目中的树节点TreeNode相当于例题中的BSTNode
  • val,left,right(val即作为键又作为值)
  • key,value,left,right
  • Ta的TreeNode没有key,比较用的是TreeNode.val属性与待删除key进行比较
  1. /**
  2.  * Definition for a binary tree node.
  3.  * public class TreeNode {
  4.  *     int val;
  5.  *     TreeNode left;
  6.  *     TreeNode right;
  7.  *     TreeNode() {}
  8.  *     TreeNode(int val) { this.val = val; }
  9.  *     TreeNode(int val, TreeNode left, TreeNode right) {
  10.  *         this.val = val;
  11.  *         this.left = left;
  12.  *         this.right = right;
  13.  *     }
  14.  * }
  15.  */
  16. class Solution {
  17.     public TreeNode deleteNode(TreeNode node, int key) {
  18.         if(node==null){
  19.             return null;
  20.         }
  21.         if(key<node.val){
  22.             node.left = deleteNode(node.left,key);
  23.             return node;
  24.         }
  25.         if(node.val<key){
  26.             node.right = deleteNode(node.right,key);
  27.             return node;
  28.         }
  29.         if(node.left==null){//情况一:只有右孩子
  30.             return node.right;
  31.         }
  32.         if(node.right == null){//情况二:只有左孩子
  33.             return node.left;
  34.         }
  35.         TreeNode s = node.right;//情况三:有两个孩子
  36.         while(s.left != null){
  37.             s= s.left;
  38.         }
  39.         s.right = deleteNode(node.right,s.val);
  40.         s.left = node.left;
  41.         return s;
  42.     }
  43. }

也可以这么写:

  1. /**
  2.  * Definition for a binary tree node.
  3.  * public class TreeNode {
  4.  *     int val;
  5.  *     TreeNode left;
  6.  *     TreeNode right;
  7.  *     TreeNode() {}
  8.  *     TreeNode(int val) { this.val = val; }
  9.  *     TreeNode(int val, TreeNode left, TreeNode right) {
  10.  *         this.val = val;
  11.  *         this.left = left;
  12.  *         this.right = right;
  13.  *     }
  14.  * }
  15.  */
  16. class Solution {
  17.     public TreeNode deleteNode(TreeNode root, int key) {
  18.         if(root == null){
  19.             return null;
  20.         }
  21.         if(key > root.val){
  22.             root.right = deleteNode(root.right,key);//去右子树删除
  23.  
  24.         }
  25.         else if(key<root.val){
  26.             root.left = deleteNode(root.left,key);//去左子树删除
  27.  
  28.         }
  29.         else{//当前节点就是要删除的节点
  30.             if(root.left==null){
  31.                 return root.right;//情况一
  32.             }
  33.             if(root.right==null){
  34.                 return root.left;//情况二
  35.             }
  36.             TreeNode node = root.right;//情况三
  37.             while(node.left!=null){//寻找要删除节点右子树的最左节点
  38.                 node = node.left;
  39.             }
  40.             node.left = root.left;
  41.             //将要删除节点的左子树成为其右子树的最左节点的左子树
  42.             root = root.right;//将要删除节点的右子顶替它的位置,节点被删除
  43.  
  44.         }
  45.         return root;
  46.     }
  47. }

新增节点-力扣701

701. 二叉搜索树中的插入操作 - 力扣（LeetCode）

  1. /**
  2.  * 新增节点(题目前提:val一定与树中节点不同)
  3.  */
  4. public class Leetcode701 {
  5.  
  6.     /*
  7.         put(key,value)
  8.             - key 存在 更新
  9.             - key 不存在 新增
  10.      */
  11.  
  12.     /*
  13.             val=7
  15.             5
  16.            / \
  17.           2   6
  18.          / \   \
  19.         1   3   7
  20.      */
  21.     public TreeNode insertIntoBST(TreeNode node,int val){
  22.         if(node==null){//找到空位
  23.             return new TreeNode(val);
  24.         }
  25.         if(val<node.val){
  26.             //2.left = 2 多余的赋值动作
  27.             node.left = insertIntoBST(node.left,val);//val=1 建立父子关系
  28.         }else if(node.val<val){
  29.             node.right = insertIntoBST(node.right,val);
  30.         }
  31.         return node;
  32.     }
  33. }

查询节点-力扣700

700. 二叉搜索树中的搜索 - 力扣（LeetCode）

  1. /**
  2.  * Definition for a binary tree node.
  3.  * public class TreeNode {
  4.  *     int val;
  5.  *     TreeNode left;
  6.  *     TreeNode right;
  7.  *     TreeNode() {}
  8.  *     TreeNode(int val) { this.val = val; }
  9.  *     TreeNode(int val, TreeNode left, TreeNode right) {
  10.  *         this.val = val;
  11.  *         this.left = left;
  12.  *         this.right = right;
  13.  *     }
  14.  * }
  15.  */
  16. class Solution {
  17.     public TreeNode searchBST(TreeNode root, int val) {
  18.         if(root==null){
  19.             return null;
  20.         }
  21.         if(val<root.val){
  22.             return searchBST(root.left,val);
  23.         }else if(root.val<val){
  24.             return searchBST(root.right,val);
  25.         }else{
  26.             return root;
  27.         }
  28.     }
  29. }

验证二叉搜索树-力扣98

98. 验证二叉搜索树 - 力扣（LeetCode）

  1. // 解法1:中序遍历非递归实现
  2.     public boolean isValidBST(TreeNode node){
  3.         TreeNode p = node;
  4.         LinkedList<TreeNode> stack = new LinkedList<>();
  5.         long prev=Long.MIN_VALUE;//代表上一个值
  6.         while(p!=null || !stack.isEmpty()){
  7.             if(p!=null){
  8.                 stack.push(p);
  9.                 p= p.left;
  10.             }else{
  11.                 TreeNode pop = stack.pop();
  12.                 //处理值
  13.                 if(prev >= pop.val){
  14.                     return false;
  15.                 }
  16.                 prev = pop.val;
  17.                 p = pop.right;
  18.             }
  19.         }
  20.         return true;
  21.     }
  1. long pre = Long.MIN_VALUE;
  2.     // 解法2:中序遍历递归实现
  3.     public boolean isValidBST(TreeNode node){
  4.         if(node==null){
  5.             return true;
  6.         }
  7.         boolean a = isValidBST(node.left);
  8.         //值
  9.         if(pre >= node.val){
  10.             return false;
  11.         }
  12.         pre = node.val;
  13.         boolean b = isValidBST(node.right);
  14.         return a&&b;
  15.     }

虽然在leetcode上这段代码运行的效率比非递归的高 但是仍然不是最优效率的,下面来看一下:

上面这段代码到这里仍然没有结束

 

 

  1. long pre = Long.MIN_VALUE;
  2.     // 解法2:中序遍历递归实现
  3.     public boolean isValidBST(TreeNode node){
  4.         if(node==null){
  5.             return true;
  6.         }
  7.         boolean a = isValidBST(node.left);
  8.         if(!a){
  9.             return false;//做一个提前的返回
  10.         }
  11.         //值
  12.         if(pre >= node.val){
  13.             return false;
  14.         }
  15.         pre = node.val;
  16.         return isValidBST(node.right);;
  17.     }

剪枝操作.

还有一个问题就是pre 变量的一个小坑:

  1.   public boolean isValidBST(TreeNode node){
  2.         return doValid(node,Long.MIN_VALUE);
  3.     }
  4.  
  5.     private boolean doValid(TreeNode node,long prev){
  6.         if(node==null){
  7.             return true;
  8.         }
  9.         boolean a = doValid(node.left,prev);
  10.         if(!a){
  11.             return false;
  12.         }
  13.         if(prev>=node.val){
  14.             return false;
  15.         }
  16.         prev = node.val;
  17.         return doValid(node.right,prev);
  18.         
  19.         /*
  20.                 3
  21.                  \ 
  22.                   4
  23.                  /
  24.                 5
  25.         
  26.          */
  27.     }

这样写看似没有问题 但在运行像上面345这个实例的时候会发生问题 实际上当3往下走的时候4会先走doValid(node.left,prev); 这样看似prev = node.val 也就是 prev = 5,但因为你的prev是作为一个参数,是对整个方法中生效的,也就是4这个点有doValid(node.left,prev) 和 doValid(node.right,prev)这两个prev都是4这个点传入的prev并不会说因为在doValid(node.prev)中prev=5导致这个方法的所有prev都变为了5,本质也就是这个参数只是这个方法的局部变量,局部变量的修改不会影响到其他的方法

解决方法:1.prev作为全局变量(上面实现过)  2.AtomicLong prev也就是作为是一个对象

  1.   public boolean isValidBST(TreeNode node){
  2.         return doValid(node,new AtomicLong(Long.MIN_VALUE));
  3.         //始终传递的都是同一个对象 所以修改可以改变其他方法中prev
  4.         //那能不能用Long 这个长整型作为对象呢?不行,Long和其他java
  5.         //里的包装类型都属于不可变数据类型,里面的值是不能修改的
  6.         //AtomicLong是可变数据类型,里面的数据是可以用set修改
  7.     }
  8.  
  9.     private boolean doValid(TreeNode node, AtomicLong prev){
  10.         if(node==null){
  11.             return true;
  12.         }
  13.         boolean a = doValid(node.left,prev);
  14.         if(!a){
  15.             return false;
  16.         }
  17.         if(prev.get()>=node.val){
  18.             return false;
  19.         }
  20.         prev.set(node.val);
  21.         return doValid(node.right,prev);
  22.     }

上面的所有方法都是利用中序遍历判断,

能否只判断父亲比左孩子大比右孩子小?no 考虑少了

  1.     /*
  2.            能否只判断父亲比左孩子大,比右孩子小?
  3.                 4
  4.               /    \
  5.              2      6
  6.            /  \
  7.           1    3
  9.     反例:
  10.            4
  11.          /   \
  12.         2     6
  13.              /  \
  14.             3    7
  16. 只考虑了父子之间没有考虑祖先跟后代的大小关系,判断上就出现了疏漏
  17.      */

可以用上下限的方法来解决:

  1. /*
  3.         -∞ 4  +∞
  4.          /   \
  5.       -∞ 2 4 4 6 +∞
  6.              /  \
  7.           4 3 6 6 7 +∞
  8.      */
  9.     //解法4:上下限递归实现 0ms
  10.     public boolean isValidBST4(TreeNode node){
  11.         return doValid4(node,Long.MIN_VALUE,Long.MAX_VALUE);
  12.     }
  13.     private boolean doValid4(TreeNode node,long min,long max){
  14.         if(node==null){
  15.             return true;
  16.         }
  17.         if(node.val<=min || node.val>=max){
  18.             return false;
  19.         }
  20.         return doValid4(node.left,min,node.val) && doValid4(node.right,node.val,max);
  21.  
  22.     }

搜索二叉树范围和-力扣938

938. 二叉搜索树的范围和 - 力扣（LeetCode）

  1. // 解法1: 中序非递归实现 4ms
  2.     public int rangeSumBST(TreeNode node,int low,int high){
  3.         TreeNode p  = node;
  4.         LinkedList<TreeNode>stack = new LinkedList<>();
  5.         int sum = 0;
  6.         while(p!=null||!stack.isEmpty()){
  7.             if(p!=null){
  8.                 stack.push(p);
  9.                 p=p.left;
  10.             }else{
  11.                 TreeNode pop = stack.pop();
  12.                 //处理值
  13.                 if(pop.val>high){
  14.                     break;
  15.                 }//剪枝
  16.  
  17.                 if(pop.val >= low){
  18.                     sum+=pop.val;
  19.                 }
  20.                 p = pop.right;
  21.             }
  22.         }
  23.         return sum;
  24.     }

解题思路
标签：深度优先遍历
题意：这个题字面含义很难理解，本意就是求出所有 X >= L 且 X <= R 的值的和
递归终止条件：
当前节点为 null 时返回 0
当前节点 X < L 时则返回右子树之和
当前节点 X > R 时则返回左子树之和
当前节点 X >= L 且 X <= R 时则返回：当前节点值 + 左子树之和 + 右子树之和

  1.  //中序遍历性能不高的原因在于不能够有效的筛选 对high可以剪枝 但是对low没有办法有效的剪枝
  2.     // 解法2:上下限递归
  3.     /*
  4.             10
  5.            /  \
  6.           5    15
  7.          / \    \
  8.         3   7    18     low=7   high=15
  10.      */
  11.     public int rangeSumBST(TreeNode node,int low,int high){
  12.         if(node==null){
  13.             return 0;
  14.         }
  15.         if(node.val<low){
  16.             return rangeSumBST(node.right,low,high);
  17.         }
  18.         if(node.val>high){
  19.             return rangeSumBST(node.left,low,high);
  20.         }
  21.  
  22.         // 在范围内
  23.         return node.val + rangeSumBST(node.left, low, high) + rangeSumBST(node.right, low, high);
  24.  
  25.     }

 

前序遍历构造二叉搜索树-力扣1008

  1. /**
  2.  * 根据前序遍历构造二叉搜索树 题目说明 preorder 长度>=1
  3.  */
  4. public class Leetcode1008 {
  5.     /*
  6.     1.preorder长度>=1
  7.     2.preorder没有重复值
  9.         8, 5, 1, 7, 10, 12
  11.                 8
  12.                / \
  13.               5  10
  14.              / \   \
  15.             1   7  12
  16.      */
  17.     public TreeNode bstFromPreorder(int[] preorder){
  18.         TreeNode root = new TreeNode(preorder[0]);
  19.         for (int i = 1; i < preorder.length; i++) {
  20.             int val = preorder[i];
  21.             insert(root,val);//n * log(n)
  22.         }
  23.         return root;
  24.     }
  25.     private TreeNode insert(TreeNode node,int val){
  26.         if(node==null){
  27.             return new TreeNode(val);
  28.         }
  29.         if(val<node.val){
  30.             node.left = insert(node.left,val);
  31.         }else if(node.val<val){
  32.             node.right = insert(node.right,val);
  33.         }//没有重复值 直接不写else
  34.         return node;
  35.     }
  36. }

方法二: 

  1.  // 上限法 8 5 1 7 10 12
  2.     /*
  3.     1.遍历数组中的每一个值,根据值创建节点
  4.         - 每个人节点若成功创建:做孩子上限,右孩子上限
  5.     2.处理下一个值时,如果超过此上限,那么
  6.         - 将null作为上个节点的孩子
  7.         - 不能创建节点对象
  8.         - 直到不超过上限为止
  9.     3.重复1,2步骤
  11.      */
  12.     public TreeNode bstFromPreorder(int[] preorder){
  13.         return insert(preorder,Integer.MAX_VALUE);
  14.     }
  15.     /*
  16.         依次处理 preorder 中每个值,返回创建好的节点或null
  17.         1.如果超过上限,返回null,作为孩子返回
  18.         2.如果没超过上限,创建节点,并设置其左右孩子
  19.             左右孩子完整后返回
  20.      */
  21.  
  22.     int i = 0;//索引从0开始
  23.     private TreeNode insert(int[] preorder,int max){
  24.         if(i==preorder.length){
  25.             return null;
  26.         }
  27.         int val = preorder[i];
  28.         if(val>max){
  29.             return null;
  30.         }
  31.         //没有超过上限
  32.         TreeNode node = new TreeNode(val);
  33.         i++;//找到下一个值看看下一个值能不能作为左孩子或者右孩子
  34.         node.left = insert(preorder,val);//左孩子上限就是自身的值
  35.         node.right= insert(preorder,max);//
  36.         return node;
  37.  
  38.     }

上下限:时间复杂度为O(n)

分治法:O(n*logn)

  1.    //分治法
  2.     /*
  3.         8 5 1 7 10 12
  4.        根 8
  5.        左 5 1 7
  6.        右 10 12
  8.        根 5  左 1 右 7
  9.        根 10 左 null 右 12
  11.     */
  12.  
  13.     public TreeNode bstFromPreorder1(int[] preorder){
  14.         return partition(preorder,0,preorder.length);
  15.     }
  16.     private TreeNode partition(int[] preorder,int start,int end){
  17.         if(start>end){
  18.             return null;
  19.         }
  20.         TreeNode root = new TreeNode(preorder[start]);
  21.         int index = start+1;
  22.         while(index<=end){
  23.             if(preorder[index]>preorder[start]){
  24.                 break;
  25.             }
  26.             index++;
  27.         }
  28.         //index是右子树的起点
  29.         root.left = partition(preorder,start+1,index-1);
  30.         root.right = partition(preorder,index,end);
  31.         return root;
  32.     }

求二叉搜索树最近公共祖先(祖先也包括自己) - 力扣235

  1. /**
  2.  * 求二叉搜索树最近公共祖先(祖先也包括自己)
  3.  * 前提:
  4.  * <ul>
  5.  *     <li>节点值唯一</li>
  6.  *     <li>p和q都存在</li>
  7.  * </ul>
  8.  */
  9. public class Leetcode235 {
  10.     /*
  11.            _ _ 6_ _
  12.           /         \
  13.          2           8
  14.         / \         / \
  15.        0   4       7   9
  16.           / \
  17.          3   5
  19.          待查找节点p q 在某一节点的两侧,那么此节点就是最近的公共祖先
  20.      */
  21.     public TreeNode lowestCommonAncestor(TreeNode root,TreeNode p,TreeNode q){
  22.         TreeNode a = root;
  23.         while(p.val<a.val&&q.val<a.val || a.val<p.val && a.val<q.val){ //在同一侧
  24.             if(p.val<a.val){
  25.                 a = a.left;
  26.             }else{
  27.                 a= a.right;
  28.             }
  29.         }
  30.         return a;
  31.     }
  32.  
  33. }

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/笔触狂放9/article/detail/499404
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号