当前位置：网站首页>详谈二叉搜索树
详谈二叉搜索树
2022-08-10 23:55:00 【牛牛最爱喝兽奶】
详谈二分搜索树
二分搜索树的概念
在了解二分搜索树之前，我们得弄清楚什么是二叉树。
什么是二叉树？
二分搜索树
二分搜索树的创建以及实现其方法
1.内部结构
内部有一个结点类，作为二分搜索树的成员变量使用
private class Node{
public E e;//结点元素
public Node left,right;//左右结点
public Node (E e){
//初始化
this.e = e;
left = null;
right = null;
}
public String toString(){
return e.toString();
}
}
2.构造方法与成员变量
初始化成员变量
private Node root;//根节点
private int size;//有效结点个数
public BinarySearchTree(){
//构造方法
size =0;
root = null;
}
3.增添元素
根据元素值大小决定去向，小于父亲节点在左边，大于在右边
public int size(){
//获取有效长度
return size;
}
public boolean isEmpty(){
//判断是否为空
return size==0&&root==null;
}
public void clear(){
size =0;
root = null;
}
public void add(E e){
增添元素
root = add(root,e);//在根节点的基础上去添加
}
private Node add(Node node,E e){
if(node==null){
size++;
return new Node(e);
}
if(e.compareTo(node.e)>0){
//e大于父节点的值
node.right = add(node.right,e);
}else if(e.compareTo(node.e)<0){
node.left = add(node.left,e);
}else {
node.e = e;
}
return node;
}
4.遍历元素
遍历元素总共有四种种先序、后序、中序和层次遍历。
private void preOrderNR(){
//先序非递归遍历
Stack<Node> stack = new Stack<>();
stack.push(root);
while(!stack.isEmpty()){
Node node = stack.pop();
System.out.print(node.e+" ");
if (node.right!=null){
//利用栈先入右节点，在入左节点 先进后出 后进先出
stack.push(node.right);
} if(node.left!=null){
stack.push(node.left);
}
}
}
private void preOrder(Node node){
//先序递归遍历
if(node == null){
return;
}
System.out.print(node.e+" ");
preOrder(node.left);
preOrder(node.right);
}
public void inOrder(){
inOrder(root);
System.out.println("=========");
inOrderNR();
}
public void inOrder(Node node){
//中序递归遍历
if(node==null){
return;
}
inOrder(node.left);
System.out.print(node.e+" ");
inOrder(node.right);
}
public void inOrderNR(){
//中序非递归遍历
Stack<Node> stack = new Stack();
Node p =root;
while(p!=null){
stack.push(p);
p = p.left;
}
while(!stack.isEmpty()){
Node ret = stack.pop();
System.out.print(ret.e+" ");
if(ret.right!=null){
p = ret.right;
while(p!=null){
stack.push(p);
p = p.left;
}
}
}
}
public void postOrder(){
postOrder(root);
System.out.println();
postOrderNR();
}
private void postOrder(Node node){
//后序递归遍历
if(node == null){
return ;
}
postOrder(node.left);
postOrder(node.right);
System.out.print(node.e+" ");
}
private void postOrderNR() {
//后序非递归遍历
Stack<Node> stack = new Stack<>();
Node node = root;
Node pre = null;
while(!stack.isEmpty()||node!=null){
while (node!=null){
stack.push(node);
node = node.left;
}
if (!stack.isEmpty()){
node = stack.pop();
if(node.right==null||pre==node.right){
System.out.print(node.e+" ");
pre = node;
node =null;
}else{
stack.push(node);
node = node.right;
}
}
}
}
public void levelOrder(){
//层序遍历
Queue<Node> que = new LinkedList<>();
que.add(root);
while(!que.isEmpty()){
Node e = que.poll();
System.out.print(e.e);
if(e.left!=null){
que.add(e.left);
}
if(e.right!=null){
que.add(e.right);
}
}
}
5.判断元素是否存在
目的是为了判断一个元素是否在二分查找树中
public boolean contains(E e){
return contains(root,e);
}
private boolean contains(Node node,E e){
if(node == null){
return false;
}
if(e.compareTo(node.e)==0){
return true;
}
return e.compareTo(node.e)>0 ? contains(node.right,e):contains(node.left,e);
}
6.remove移除一个结点
删除一个结点及元素值
public void remove(E e){
root = remove(root,e);
}
public Node remove(Node node,E e){
if(node==null){
return null;
}
if(e.compareTo(node.e)>0){
node.right = remove(node.right,e);
}else if(e.compareTo(node.e)<0){
node.left = remove(node.left,e);
}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 = minimun(minimun(node.right));
successor.right = removemin(node.right);
successor.left = node.left;
node.left =null;
node.right = null;
size--;
return successor;
}
return null;
}
最终整体代码
package com.数据结构.xiaoniu.类;
import com.sun.org.apache.xalan.internal.xsltc.compiler.util.StringStack;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
public class BinarySearchTree<E extends Comparable<E>> implements Iterable{
private class Node{
public E e;
public Node left,right;
public Node (E e){
this.e = e;
left = null;
right = null;
}
public String toString(){
return e.toString();
}
}
private Node root;
private int size;
public BinarySearchTree(){
size =0;
root = null;
}
public int size(){
return size;
}
public boolean isEmpty(){
return size==0&&root==null;
}
public void clear(){
size =0;
root = null;
}
public void add(E e){
root = add(root,e);
}
private Node add(Node node,E e){
if(node==null){
size++;
return new Node(e);
}
if(e.compareTo(node.e)>0){
node.right = add(node.right,e);
}else if(e.compareTo(node.e)<0){
node.left = add(node.left,e);
}else {
node.e = e;
}
return node;
}
public boolean contains(E e){
return contains(root,e);
}
private boolean contains(Node node,E e){
if(node == null){
return false;
}
if(e.compareTo(node.e)==0){
return true;
}
return e.compareTo(node.e)>0 ? contains(node.right,e):contains(node.left,e);
}
public void preOrder(){
preOrder(root);
System.out.println();
preOrderNR();
}
private void preOrderNR(){
Stack<Node> stack = new Stack<>();
stack.push(root);
while(!stack.isEmpty()){
Node node = stack.pop();
System.out.print(node.e+" ");
if (node.right!=null){
//利用栈先入右节点，在入左节点 先进后出 后进先出
stack.push(node.right);
} if(node.left!=null){
stack.push(node.left);
}
}
}
private void preOrder(Node node){
if(node == null){
return;
}
System.out.print(node.e+" ");
preOrder(node.left);
preOrder(node.right);
}
public void inOrder(){
inOrder(root);
System.out.println("=========");
inOrderNR();
}
public void inOrder(Node node){
if(node==null){
return;
}
inOrder(node.left);
System.out.print(node.e+" ");
inOrder(node.right);
}
public void inOrderNR(){
Stack<Node> stack = new Stack();
Node p =root;
while(p!=null){
stack.push(p);
p = p.left;
}
while(!stack.isEmpty()){
Node ret = stack.pop();
System.out.print(ret.e+" ");
if(ret.right!=null){
p = ret.right;
while(p!=null){
stack.push(p);
p = p.left;
}
}
}
}
public void postOrder(){
postOrder(root);
System.out.println();
postOrderNR();
}
private void postOrderNR() {
Stack<Node> stack = new Stack<>();
Node node = root;
Node pre = null;
while(!stack.isEmpty()||node!=null){
while (node!=null){
stack.push(node);
node = node.left;
}
if (!stack.isEmpty()){
node = stack.pop();
if(node.right==null||pre==node.right){
System.out.print(node.e+" ");
pre = node;
node =null;
}else{
stack.push(node);
node = node.right;
}
}
}
}
public void levelOrder(){
//层序遍历
Queue<Node> que = new LinkedList<>();
que.add(root);
while(!que.isEmpty()){
Node e = que.poll();
System.out.print(e.e);
if(e.left!=null){
que.add(e.left);
}
if(e.right!=null){
que.add(e.right);
}
}
}
public E minimum(){
if(size==0){
throw new IllegalArgumentException("Is NULL!");
}
Node n = root;
while (n.left!=null){
n=n.left;
}
return n.e;
}
public E maxmun(){
if(size==0){
throw new IllegalArgumentException("Is NULL!");
}
Node n = root;
while (n.right!=null){
n=n.right;
}
return n.e;
}
public E removeMin(){
//删除最小二叉树中的节点
if(size==0){
throw new IllegalArgumentException("Is NULL!");
}
Node n = root;
while (n.left.left!=null){
n=n.left;
}
E ret = n.left.e;
n.left = n.left.right;
return ret;
}
public E removeMax(){
if(size==0){
throw new IllegalArgumentException("Is NULL!");
}
Node n = root;
while (n.right.right!=null){
n=n.right;
}
E ret = n.right.e;
n.right = n.right.left;
return ret;
}
public E removemin(){
E ret = minimum();
root = removemin(root);
return ret;
}
public E removemax(){
E ret = maxmun();
root = removemax(root);
return ret;
}
private Node removemax(Node node){
if(node.right==null){
Node leftNode = node.left;
node.left = null;
size--;
return leftNode;
}
node = node.right;
node.right = removemax(node.right);
return node;
}
public 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;
}
public Node minimun(Node node){
if(node.left==null){
return node;
}
return minimun(node.left);
}
public Node maximum(Node node){
if(node.right==null){
return node;
}
return minimun(node.right);
}
public void remove(E e){
root = remove(root,e);
}
public Node remove(Node node,E e){
if(node==null){
return null;
}
if(e.compareTo(node.e)>0){
node.right = remove(node.right,e);
}else if(e.compareTo(node.e)<0){
node.left = remove(node.left,e);
}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 = minimun(minimun(node.right));
successor.right = removemin(node.right);
successor.left = node.left;
node.left =null;
node.right = null;
size--;
return successor;
}
return null;
}
private void postOrder(Node node){
if(node == null){
return ;
}
postOrder(node.left);
postOrder(node.right);
System.out.print(node.e+" ");
}
public String toString(){
StringBuilder res =new StringBuilder();
gennerateBSTString(root,0,res);
return res.toString();
}
private void gennerateBSTString(Node node, int depth, StringBuilder res) {
if(node==null){
res.append(generateDepthString(depth)+node.e+"\n");
return;
}
res.append(generateDepthString(depth)+node.e+"\n");
gennerateBSTString(node.left,depth+1,res);
gennerateBSTString(node.right,depth+1,res);
}
private String generateDepthString(int depth) {
StringBuilder sb =new StringBuilder();
for(int i=0;i<depth;i++){
sb.append("--");
}
return sb.toString();
}
@Override
public Iterator<E> iterator() {
return new BinarySearchTreeIterator();
}
private class BinarySearchTreeIterator implements Iterator<E>{
private LinkedList<Node> list = new LinkedList<>();
public BinarySearchTreeIterator(){
Stack<Node> stack = new Stack<>();
Node p = root;
while(p!=null){
stack.push(p);
p =p.left;
}
while (!stack.isEmpty()){
Node n = stack.pop();
list.add(n);
if(n.right!=null){
p = n.right;
while(p!=null){
stack.push(p);
p = p.left;
}
}
}
}
@Override
public boolean hasNext() {
return !list.isEmpty();
}
@Override
public E next() {
return (E) list.removeFirst();
}
}
}
边栏推荐
- 91.（cesium之家）cesium火箭发射模拟
- CF1427F-Boring Card Game【贪心】
- 14. Thymeleaf
- Which translation software is more accurate [Free]
- Software Testing Certificate (1) - Software Evaluator
- 好用的翻译插件-一键自动翻译插件软件
- [Excel知识技能] 将数值格式数字转换为文本格式
- sqlmap combined with dnslog fast injection
- Promise in detail
- Excel English automatic translation into Chinese tutorial
猜你喜欢
15. 拦截器-HandlerInterceptor
Why do programming languages have the concept of variable types?
11. Custom Converter
回收站的文件删了怎么恢复，回收站文件恢复的两种方法
8. WEB 开发-静态资源访问
10. Notes on receiving parameters
![[C language articles] Expression evaluation (implicit type conversion, arithmetic conversion)](/img/ae/74dc5fc676e74ab03607565ca7539e.png)
[C language articles] Expression evaluation (implicit type conversion, arithmetic conversion)
学习Apache ShardingSphere解析器源码（一）
Web APIs BOM- 操作浏览器之综合案例
Design and Realization of Employment Management System in Colleges and Universities
随机推荐
线上突然查询变慢怎么核查
sqlmap结合dnslog快速注入
[Excel knowledge and skills] Convert text numbers to numeric format
【js】获取当前时间的前后n天或前后n个月（时分秒年月日都可）
YOLOv5的Tricks | 【Trick13】YOLOv5的detect.py脚本的解析与简化
李彦宏拆墙交朋友，大厂“塑料友情”能否帮百度啃下硬骨头？
9. Rest 风格请求处理
SQL injection base - order by injection, limit, wide byte
有哪些可以投稿软件工程/系统软件/程序设计语言类外文期刊、会议?
How to determine how many bases a number is?
13. Content Negotiation
Is there a way out in the testing industry if it is purely business testing?
HGAME 2022 Final Pokemon v2 writeup
How to recover data from accidentally deleted U disk, how to recover deleted data from U disk
Introduction to Qt (6) - Implementation of the lottery system
【爬虫】scrapy创建运行爬虫、解析页面（嵌套url）、自定义中间件（设置UserAgent和代理IP）、自定义管道（保存到mysql）
Which translation software is more accurate [Free]
11. 自定义转换器
YOLOv5的Tricks | 【Trick12】YOLOv5使用的数据增强方法汇总
11. Custom Converter