二分搜索树(玩转数据结构)

前言

二分搜索树

---

一、为什么要研究树结构

二、二分搜索树基础

package com.zcw.data.bst; /**
 * @ClassName : BST
 * @Description :二分搜索树
 * @Author : Zhaocunwei
 * @Date: 2020-07-28 18:37
 */ public class BST<E extends Comparable<E>> { private class Node{ public E e; public Node left,right; public Node(E e){ this.e = e; left = null; right =null; } } private Node root; private int size; public BST(){ root =null; size =0; } public int size(){ return size; } public boolean isEmpty(){ return size==0; } } 

三、向二分搜索树中添加元素

/**
     * 向二分搜索树中添加新的元素e
     */ public void add(E e){ if(root == null){ root = new Node(e); size ++; }else{ add(root,e); } } /**
     *向以node为根的二分搜索树中插入元素E，递归算法
     */ private void add(Node node ,E e){ if(e.equals(node.e)){ return; }else if(e.compareTo(node.e) <0 && node.left ==null){ node.left = new Node(e); size++; return; }else if(e.compareTo(node.e) >0 && node.right ==null){ node.right = new Node(e); size++; return; } if(e.compareTo(node.e)<0){ add(node.left,e); }else{ add(node.right,e); } } 

四、改进添加操作： 深入理解递归终止条件

/**
     * 改进添加操作： 深入理解递归终止条件
     * 返回出入新节点后二分搜索树的根
     * @param node
     * @param e
     * @return
     */ private Node add(Node node ,E e){ if(node == null){ size++; return new Node(e); } if(e.compareTo(node.e)<0){ node.left = add(node.left,e); }else if(e.compareTo(node.e) >0){ node.right = add(node.right,e); } return node; } 

五、二分搜索树的查询操作

/**
     * 看二分搜索树中是否包含元素e
     */ public boolean contains(E e){ return contains(root,e); } /**
     * 看以node为根的二分搜索树中是否包含元素e,递归算法
     * @param node
     * @param e
     * @return
     */ private boolean contains(Node node ,E e){ if(node == null){ return false; } if(e.compareTo(node.e) == 0){ return true; }else if(e.compareTo(node.e) < 0){ return contains(node.left,e); }else{ return contains(node.right,e); } } 

六、二分搜索树的前序遍历

1.什么是遍历

2.二分搜索树的递归操作

 @Override public String toString(){ StringBuilder res = new StringBuilder(); generateBSTString(root,0,res); return res.toString(); } //生成以node为根节点，深度为depth的描述二叉树的字符串 private void generateBSTString(Node node,int depth,StringBuilder res){ if(node == null){ res.append(generateDepthString(depth) +"null\n"); return; } res.append(generateDepthString(depth)+node.e+"\n"); generateBSTString(node.left,depth+1,res); generateBSTString(node.right,depth+1,res); } private String generateDepthString(int depth){ StringBuilder res = new StringBuilder(); for(int i=0; i<depth;i++){ res.append("--"); } return res.toString(); } public static void main(String[] args) { BST<Integer> bst = new BST<>(); int[] nums ={5,3,6,8,4,2}; for(int num : nums){ bst.add(num); } ////////////////////////////// //             5            // //            / \           // //           3   6          // //          / \   \         // //         2  4    8        // ////////////////////////////// bst.preOrder(); System.out.println(); System.out.println(bst); } 

5 3 2 4 6 8 5 --3 ----2 ------null ------null ----4 ------null ------null --6 ----null ----8 ------null ------null 

七、二分搜索树的中序遍历和后序遍历

1.前序遍历

2.中序遍历

/**
     *二分搜索树的中序遍历
     */ public void inOrder(){ inOrder(root); } /**
     *中序遍历以node为根的二分搜索树，递归算法
     */ private void inOrder(Node node){ if(node == null){ return; } inOrder(node.left); System.out.println(node.e); inOrder(node.right); } 

3. 后序遍历

/**
     * 二分搜索树的后序遍历
     */ public void postOrder(){ preOrder(root); } /**
     * 后序遍历以node为根的二分搜索树，递归算法
     */ private void postOrder(Node node){ if(node == null){ return; } postOrder(node.left); postOrder(node.right); System.out.println(node.e); } 

八、深入理解二分搜索树的前中后序遍历

1.二分搜索树的遍历

2.二分搜索树的前序遍历

3.二分搜索树中序遍历

4.二分搜索树的后序遍历

九、二分搜索树前序遍历的非递归实现

 /**
     *二分搜索树的非递归前序遍历
     */ public void preOrderNR(){ Stack<Node> stack = new Stack<>(); stack.push(root); while(!stack.isEmpty()){ Node cur = stack.pop(); System.out.println(cur.e); if(cur.right !=null){ stack.push(cur.right); } if(cur.left !=null){ stack.push(cur.left); } } } 

十、二分搜索树的层序遍历

 /**
     * 二分搜索树的层序遍历
     */ public void levelOrder(){ Queue<Node> q = new LinkedList<>(); q.add(root); while(!q.isEmpty()){ Node cur = q.remove(); System.out.println(cur.e); if(cur.left !=null){ q.add(cur.left); } if(cur.right !=null){ q.add(cur.right); } } } 

十一、 删除二分搜索树的最大元素和最小元素

/**
     * 寻找二分搜索树的最小元素
     * @return
     */ public E minimum(){ if(size == 0){ throw new IllegalArgumentException("BST is empty"); } return minimum(root).e; } /**
     * 返回以node 为根的二分搜索树的最小键值所在节点
     * @param node
     * @return
     */ private Node minimum(Node node){ if(node.left ==null){ return node; } return minimum(node.left); } 

 /**
     * 寻找二分搜索树的最大元素
     * @return
     */ public E maximum(){ if(size ==0){ throw new IllegalArgumentException("BST is empty"); } return maximum(root).e; } /**
     * 返回以node为根的二分搜索树的最大值所在的节点
     * @param node
     * @return
     */ private Node maximum(Node node){ if(node.right == null){ return node; } return maximum(node.right); } 

/**
     * 从二分搜索树中删除最小值所在节点，返回最小值
     * @return
     */ public E removeMin(){ E ret = minimum(); root = removeMin(root); return ret; } /**
     * 删除掉以node为根的二分搜索树中的最小节点
     * 返回删除节点后新的二分搜索树的根
     * @param node
     * @return
     */ private Node removeMin(Node node){ if(node.left == null){ Node rightNode = node.right; node.right = null; size --; return rightNode; } node.left = removeMin(node.left); return node; } 

/**
     * 从二分搜索树中删除最大值所在节点
     * @return
     */ public E removeMax(){ E ret = maximum(); root = removeMax(root); return ret; } /**
     * 删除掉以node为根的二分搜索树中的最大节点
     * 返回删除节点后新的二分搜索树的根
     * @param node
     * @return
     */ private Node removeMax(Node node){ if(node.right == null){ Node leftNode = node.left; node.left =null; size --; return leftNode; } node.right = removeMax(node.right); return node; } 

十二、删除二分搜索树的任意元素

 /**
     * 从二分搜索树中删除元素为e的节点
     * @param e
     */ public void remove(E e){ root = remove(root,e); } private Node remove(Node node,E e){ if(node == null){ return null; } if(e.compareTo(node.e) <0){ node.left = remove(node.left,e); return node; }else if(e.compareTo(node.e) >0){ node.right = remove(node.right,e); return node; }else { //待删除节点左子树为空的情况 if(node.left == null){ Node rightNode = node.right; node.right =null; size--; return rightNode; } //待删除节点右子树为空的情况 if(node.right == null){ Node leftNode = node.left; node.left = null; size--; return leftNode; } /**
             * 待删除节点左右子树均不为空的情况
             * 找到比待删除节点大的最小节点，即待删除节点右子树的最小节点
             * 用这个节点顶替待删除节点的位置
             */ Node successor = minimum(node.right); successor.right = removeMin(node.right); successor.left = node.left; node.left = node.right = null; return successor; } } 

 package com.zcw.data.bst; import java.util.LinkedList; import java.util.Queue; import java.util.Stack; /**
 * @ClassName : BST
 * @Description :二分搜索树
 * @Author : Zhaocunwei
 * @Date: 2020-07-28 18:37
 */ public class BST<E extends Comparable<E>> { private class Node{ public E e; public Node left,right; public Node(E e){ this.e = e; left = null; right =null; } } private Node root; private int size; public BST(){ root =null; size =0; } public int size(){ return size; } public boolean isEmpty(){ return size==0; } /**
     * 向二分搜索树中添加新的元素e
     */ public void add(E e){ //        if(root == null){ //            root = new Node(e); //            size ++; //        }else{ //            add(root,e); //        } root = add(root,e); } /**
     *向以node为根的二分搜索树中插入元素E，递归算法
     */ //    private void add(Node node ,E e){ //        if(e.equals(node.e)){ //            return; //        }else if(e.compareTo(node.e) <0  && node.left ==null){ //            node.left = new Node(e); //            size++; //            return; //        }else if(e.compareTo(node.e) >0 && node.right ==null){ //            node.right = new Node(e); //            size++; //            return; //        } // //        if(e.compareTo(node.e)<0){ //            add(node.left,e); //        }else{ //            add(node.right,e); //        } //    } /**
     * 改进添加操作： 深入理解递归终止条件
     * 返回出入新节点后二分搜索树的根
     * @param node
     * @param e
     * @return
     */ private Node add(Node node ,E e){ if(node == null){ size++; return new Node(e); } if(e.compareTo(node.e)<0){ node.left = add(node.left,e); }else if(e.compareTo(node.e) >0){ node.right = add(node.right,e); } return node; } /**
     * 看二分搜索树中是否包含元素e
     */ public boolean contains(E e){ return contains(root,e); } /**
     * 看以node为根的二分搜索树中是否包含元素e,递归算法
     * @param node
     * @param e
     * @return
     */ private boolean contains(Node node ,E e){ if(node == null){ return false; } if(e.compareTo(node.e) == 0){ return true; }else if(e.compareTo(node.e) < 0){ return contains(node.left,e); }else{ return contains(node.right,e); } } /**
     * 二分搜索树的前序遍历
     */ public void preOrder(){ preOrder(root); } /**
     * 前序遍历以node为根的二分搜索树，递归算法
     * @param node
     */ private void preOrder(Node node){ //递归终止条件 if(node == null){ return; } System.out.println(node.e); preOrder(node.left); preOrder(node.right); } /**
     *二分搜索树的非递归前序遍历
     */ public void preOrderNR(){ Stack<Node> stack = new Stack<>(); stack.push(root); while(!stack.isEmpty()){ Node cur = stack.pop(); System.out.println(cur.e); if(cur.right !=null){ stack.push(cur.right); } if(cur.left !=null){ stack.push(cur.left); } } } @Override public String toString(){ StringBuilder res = new StringBuilder(); generateBSTString(root,0,res); return res.toString(); } //生成以node为根节点，深度为depth的描述二叉树的字符串 private void generateBSTString(Node node,int depth,StringBuilder res){ if(node == null){ res.append(generateDepthString(depth) +"null\n"); return; } res.append(generateDepthString(depth)+node.e+"\n"); generateBSTString(node.left,depth+1,res); generateBSTString(node.right,depth+1,res); } private String generateDepthString(int depth){ StringBuilder res = new StringBuilder(); for(int i=0; i<depth;i++){ res.append("--"); } return res.toString(); } /**
     *二分搜索树的中序遍历
     */ public void inOrder(){ inOrder(root); } /**
     *中序遍历以node为根的二分搜索树，递归算法
     */ private void inOrder(Node node){ if(node == null){ return; } inOrder(node.left); System.out.println(node.e); inOrder(node.right); } /**
     * 二分搜索树的后序遍历
     */ public void postOrder(){ preOrder(root); } /**
     * 后序遍历以node为根的二分搜索树，递归算法
     */ private void postOrder(Node node){ if(node == null){ return; } postOrder(node.left); postOrder(node.right); System.out.println(node.e); } /**
     * 二分搜索树的层序遍历
     */ public void levelOrder(){ Queue<Node> q = new LinkedList<>(); q.add(root); while(!q.isEmpty()){ Node cur = q.remove(); System.out.println(cur.e); if(cur.left !=null){ q.add(cur.left); } if(cur.right !=null){ q.add(cur.right); } } } /**
     * 寻找二分搜索树的最小元素
     * @return
     */ public E minimum(){ if(size == 0){ throw new IllegalArgumentException("BST is empty"); } return minimum(root).e; } /**
     * 返回以node 为根的二分搜索树的最小键值所在节点
     * @param node
     * @return
     */ private Node minimum(Node node){ if(node.left ==null){ return node; } return minimum(node.left); } /**
     * 寻找二分搜索树的最大元素
     * @return
     */ public E maximum(){ if(size ==0){ throw new IllegalArgumentException("BST is empty"); } return maximum(root).e; } /**
     * 返回以node为根的二分搜索树的最大值所在的节点
     * @param node
     * @return
     */ private Node maximum(Node node){ if(node.right == null){ return node; } return maximum(node.right); } /**
     * 从二分搜索树中删除最小值所在节点，返回最小值
     * @return
     */ public E removeMin(){ E ret = minimum(); root = removeMin(root); return ret; } /**
     * 删除掉以node为根的二分搜索树中的最小节点
     * 返回删除节点后新的二分搜索树的根
     * @param node
     * @return
     */ private Node removeMin(Node node){ if(node.left == null){ Node rightNode = node.right; node.right = null; size --; return rightNode; } node.left = removeMin(node.left); return node; } /**
     * 从二分搜索树中删除最大值所在节点
     * @return
     */ public E removeMax(){ E ret = maximum(); root = removeMax(root); return ret; } /**
     * 删除掉以node为根的二分搜索树中的最大节点
     * 返回删除节点后新的二分搜索树的根
     * @param node
     * @return
     */ private Node removeMax(Node node){ if(node.right == null){ Node leftNode = node.left; node.left =null; size --; return leftNode; } node.right = removeMax(node.right); return node; } /**
     * 从二分搜索树中删除元素为e的节点
     * @param e
     */ public void remove(E e){ root = remove(root,e); } private Node remove(Node node,E e){ if(node == null){ return null; } if(e.compareTo(node.e) <0){ node.left = remove(node.left,e); return node; }else if(e.compareTo(node.e) >0){ node.right = remove(node.right,e); return node; }else { //待删除节点左子树为空的情况 if(node.left == null){ Node rightNode = node.right; node.right =null; size--; return rightNode; } //待删除节点右子树为空的情况 if(node.right == null){ Node leftNode = node.left; node.left = null; size--; return leftNode; } /**
             * 待删除节点左右子树均不为空的情况
             * 找到比待删除节点大的最小节点，即待删除节点右子树的最小节点
             * 用这个节点顶替待删除节点的位置
             */ Node successor = minimum(node.right); successor.right = removeMin(node.right); successor.left = node.left; node.left = node.right = null; return successor; } } public static void main(String[] args) { BST<Integer> bst = new BST<>(); int[] nums ={5,3,6,8,4,2}; for(int num : nums){ bst.add(num); } ////////////////////////////// //             5            // //            / \           // //           3   6          // //          / \   \         // //         2  4    8        // ////////////////////////////// bst.preOrder(); System.out.println(); //        System.out.println(bst); bst.inOrder(); System.out.println(); bst.preOrder(); System.out.println(); } } 

本文地址：https://blog.csdn.net/qq_32370913/article/details/107641932