欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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

程序员文章站 2022-12-20 16:51:24
二分搜索树...

前言

二分搜索树


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

一、为什么要研究树结构

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

二、二分搜索树基础

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

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