文档章节

二叉查找树 Java实现

o
 osc_w9s1w4o0
发布于 2019/03/28 22:43
字数 1736
阅读 8
收藏 0

精选30+云产品,助力企业轻松上云!>>>

定义: 一棵二叉查找树是一棵二叉树,每个节点都含有一个Comparable的键(以及对应的值)。 每个节点的键都大于左子树中任意节点的键而小于右子树中任意节点的键。

image

树的术语:

Name Function
路径 顺着连接点的边从一个节点走向另一个节点,所经过的节点的顺序排列就称为路径。
树顶端的节点就称为根,一棵树只有一个根,如果要把一个节点和边的集合定义为树,那么从根到其他任何一个节点都必须有一条路径。
父节点 每个节点(除了根)都恰好有一条边向上连接到另一个节点,上面的节点就称为下面节点的“父节点”。
子节点 每个节点都可能有一条或多条边向下连接其他节点,下面的这些节点就称为它的“子节点”。
叶节点 没有子节点的节点称为“叶子节点”或简称“叶节点”。树只能有一个根,但是可以有很多叶节点。
子树 每个节点都可以作为子树的根,它和它所有的子节点,子节点的子节点等都含在子树中。
访问 当程序控制流程到达某个节点的时候,就称为“访问”这个节点,通常是为了在这个节点处执行某种操作,例如查看节点某个数据字段的值或者显示节点。
遍历 遍历树意味着要遵循某种特定的顺序访问树中的所有节点。
一个节点的层数是指从根开始到这个节点有多少“代”。
关键字 可以看到,对象中通常会有一个数据域被指定为关键字值。这个值通常用于查询或者其他操作。
二叉树 如果树中的每个节点最多只能有两个子节点,这样的树就称为“二叉树”。

性质:

  1. 若它的左子树不为空,则左子树上的所有节点的值都小于它的根节点的值;
  2. 若它的右子树不为空,则右子树上所有节点的值都大于它的根节点的值;
  3. 其他的左右子树也分别为二叉查找树;
  4. 二叉查找树是动态查找表,在查找的过程中可见添加和删除相应的元素,在这些操作中需要保持二叉查找树的以上性质。

根据其二叉树的特性,节点类如下:

public class Node {
    public int index;//关键字段
    public String data;//值
    public Node leftNode;//左节点
    public Node rightNode;//右节点

    @Override
    public boolean equals(Object obj) {
        return EqualsBuilder.reflectionEquals(this, obj);
    }

    @Override
    public int hashCode() {
        return HashCodeBuilder.reflectionHashCode(this);
    }
}

其中引用了commons-lang3包中的内容,作为对象进行比较

查找某个节点,相当于二分查找,如果小于当前节点,则走左边,如果大于当前节点,则走右边。当最后叶子节点还没有找到,则没有找到

public Node findNode(int key){
    Node current = root;
    while(current.index != key){
        if(key < current.index){//左节点
            current = current.leftNode;
        }else{//右节点
            current = current.rightNode;
        }
        if(current == null){
            return null;
        }
    }
    return current;
}

插入节点,按照插入的节点都不会出现重复关键字。每一次插入都将变为根节点的子节点,例如根节点关键字为1,接下来插入的节点则变为根节点的右子节点。

public void insertNode(int key,String value){
    Node node = new Node();
    node.index = key;
    node.data = value;
    
    if(root == null){
        root = node;
        return;
    }
    //找到插入节点的位置
    Node parent = root;
    Node current = root;
    while(true){
        parent = current;
        if(key == current.index){
            return;
        }
        if(key < current.index){//左节点
            current = current.leftNode;
            if(current == null){//当前节点已经是叶子结点了
                parent.leftNode = node;    
                return;
            }
        }else{
            current = current.rightNode;
            if(current == null){
                parent.rightNode = node;
                return;
            }
        }
    }
}

遍历节点,中序遍历.

  1. 调用自身来遍历节点的左子树
  2. 访问这个节点
  3. 掉用自身来遍历节点的右子树
public void inOrder(Node localRoot) {
    if (localRoot != null) {
        inOrder(localRoot.leftNode);
        System.out.println("索引:" + localRoot.index + ",值:" + localRoot.data);
        inOrder(localRoot.rightNode);
    }
}    

删除节点,分三种情况:

  1. 删除节点没有子节点,那么将父节点的左节点或者是右节点设置为空
  2. 删除节点只有一个子节点,删除该节点后,该节点的子节点变为父节点的子节点,如果删除节点时父节点的左节点,那么父节点的左节点指向该节点的子节点,反之则右节点指向删除节点的子节点。
  3. 删除节点有两个字节点,删除了该节点后,则需要选择一个后继节点,并且还不破坏该二叉树的特性(左节点要小于右节点),一般是从删除节点的右节点中找到一个后继节点,而这个节点是右子树的最小值。
public boolean delete(int key) {
        Node current = root;
        Node parent = root;
        boolean isLeftChild = true;
        //找到被删除的节点,并标识该节点是否为左节点
        while (current.index != key) {
            parent = current;
            if (key < current.index) {
                isLeftChild = true;
                current = current.leftNode;
            } else {
                isLeftChild = false;
                current = current.rightNode;
            }
            if (current == null) {
                return false;
            }
        }
        //第一种情况,删除节点为子节点
        if (current.leftNode == null && current.rightNode == null) {
            if (current == root) {
                root = null;
            } else {
                if (isLeftChild) {
                    parent.leftNode = null;
                } else {
                    parent.rightNode = null;
                }
            }
        } else if ((current.leftNode != null && current.rightNode == null) || (current.leftNode == null && current.rightNode != null)) {
            //第二中情况,删除节点只包含一个子节点,则将子节点移动动当前节点中
            if (current.rightNode == null) {//删除的节点的左节点有值,右节点为空
                if (root == current) {
                    root = current.leftNode;
                } else {
                    if (isLeftChild) {
                        parent.leftNode = current.leftNode;
                    } else {
                        parent.rightNode = current.leftNode;
                    }
                }
            } else {//删除的节点的右节点有值,左节点为空
                if (root == current) {
                    root = current.rightNode;
                } else {
                    if (isLeftChild) {
                        parent.leftNode = current.rightNode;
                    } else {
                        parent.rightNode = current.rightNode;
                    }
                }
            }
        } else if (current.leftNode != null && current.rightNode != null) {
            //第三种情况,删除节点中有左右两个节点
            //找到后继节点
            Node processer = processer(current);
            if (current == root) {//删除是根节点,则
                root = processer;
            } else {
                if (isLeftChild) {
                    parent.leftNode = processer;
                } else {
                    parent.rightNode = processer;
                }
            }
            //选中的节点的左节点与删除节点的左节点相连
            processer.leftNode = current.leftNode;
        }
        return true;
    }
    
    //找到后继节点
    private Node processer(Node delNode) {
        Node parent = delNode;
        Node success = delNode;
        Node current = delNode.rightNode;
        while (current != null) {
            // 后继节点父节点首先保存后继节点的状态
            parent = current;
            success = current;
            // 后继节点 不断的向左更新
            current = current.leftNode;
        }
        // 假如我们找到的后继节点不直接是 要删除节点的右节点  而是在其右节点那条子树上面最小的一个节点
        if (success != delNode.rightNode) {
            //后继节点的父节点断开其与后继节点左边的引用,重新连接上后继节点的右子节点(因为后继节点是没有左子节点的,锁以要保存之前树的状态,还要把后继节点的右子节点处理一下,不管 其存在不存在)
            parent.leftNode = success.rightNode;
            // 这时候后继节点的右边已经空了 上一条语句已经将其给了自己父节点的左子节点    然后让后继节点的右边 连接要删除节点的右子树
            success.rightNode = delNode.rightNode;
        }
        return success;
    }
o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。
《数据结构与算法系列》合集整理

《数据结构与算法系列》合集整理 整理来自博客园skywang12345,以下摘自作者介绍: “最近抽空整理了"数据结构和算法"的相关文章。在整理过程中,对于每种数据结构和算法分别给出"C"、"C++"...

kaixin_code
2018/12/01
328
0
查找算法总结及其算法实现Python/Java

本文分享自微信公众号 - 后端技术漫谈(Rude3Knife)。 如有侵权,请联系 support@oschina.cn 删除。 本文参与“OSC源创计划”,欢迎正在阅读的你也加入,一起分享。...

后端技术漫谈
2019/04/19
0
0
查找算法总结及其算法实现Python/Java

本文分享自微信公众号 - 后端技术漫谈(Rude3Knife)。 如有侵权,请联系 support@oschina.cn 删除。 本文参与“OSC源创计划”,欢迎正在阅读的你也加入,一起分享。...

后端技术漫谈
2019/03/06
0
0
算法4心得

1、从数据的角度理解Java类 int是Java的基本数据类型,它有两个基本特性: 它的值是一个固定的整数集合,即-2147483648和2147483647之间的整数 对它可以执行5种操作,即+、-、*、/、%。 作者...

听你呀
04/10
0
0
数据结构与算法——常用数据结构及其Java实现

本文采用Java语言来进行描述,帮大家好好梳理一下数据结构与算法,在工作和面试中用的上。亦即总结常见的的数据结构,以及在Java中相应的实现方法,务求理论与实践一步总结到位。 常用数据结...

Java面经
2019/05/07
4
0

没有更多内容

加载失败,请刷新页面

加载更多

平时使用的Lszrz到底是什么协议?说说Xmodem/Ymodem/Zmodem

XMODEM, YMODEM, and ZMODEM 由于平时使用rz/sz较多,r/s好理解,一个send一个receive。但是由不太清楚z是什么意思,故有此文。 sx/rx, sb/rb (b=batch)和sz/rz分别实现了xmodem,ymodem和z...

独钓渔
43分钟前
17
0
真正的强智能时代已经到来。道翰天琼认知智能机器人平台API大脑。

最近,我常说人工智能的寒冬快要来了,提醒业界要做好思想准备,但同时我也说:冬天来了,春天就不会远了…… 2019年6月我写了篇文章《深度学习的问题究竟在哪?》,说到深度学习的一个主要问...

jackli2020
52分钟前
24
0
什么是控制型人格,控制型人格的筛查测试

一、 什么是控制性人格 拥有控制型人格的人,他们会尽力的隐藏自己的意图,但是又会使用很微妙的方式来利用周围人的弱点,进而占取便宜时,使他们能够得到自己想要的东西。这类人的控制欲非常...

蛤蟆丸子
今天
14
0
【Spring】Spring AOP 代理对象生成逻辑源码分析

1. spring aop案例(POJO注入) 1.0 被代理接口 TargetInterface /** * 被代理的接口 * @author Yang ZhiWei */public interface TargetInterface { void show(); String show......

ZeroneLove
今天
36
0
聊聊dubbo-go的gracefulShutdownFilter

序 本文主要研究一下dubbo-go的gracefulShutdownFilter gracefulShutdownFilter dubbo-go-v1.4.2/filter/filter_impl/graceful_shutdown_filter.go type gracefulShutdownFilter struct {......

go4it
今天
30
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部