二分搜索树(玩转数据结构)
程序员文章站
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
上一篇: Java开发学习.Day8
下一篇: python中main函数的用法