搜索
首页Javajava教程Java实现二叉搜索树算法的代码详解(图)

二叉查找树可以递归地定义如下,二叉查找树或者是空二叉树,或者是满足下列性质的二叉树:

(1)若它的左子树不为空,则其左子树上任意结点的关键字的值都小于根结点关键字的值。

(2)若它的右子树不为空,则其右子树上任意结点的关键字的值都大于根节点关键字的值。

(3)它的左、右子树本身又是一个二叉查找树。

从性能上来说如果二叉查找树的所有非叶子结点的左右子树的结点数目均保持差不多(平衡),那么二叉查找树的搜索性能逼近二分查找;但它比连续内存空间的二分查找的优点是,改变二叉查找树结构(插入与删除结点)不需要移动大段的内存数据,甚至通常是常数开销。二叉查找树可以表示按顺序序列排列的数据集合,因此二叉查找树也被称为二叉排序树,并且同一个数据集合可以表示为不同的二叉查找树。二叉查找树的结点的数据结构定义为:

struct celltype{

    records data; 

    celltype * lchild, * rchild;

}

typedef celltype * BST;

在Java中,节点的数据结构定义如下:

package wx.algorithm.search.bst;

/**

 * Created by apple on 16/7/29.

 */

/**

 * @function 二叉搜索树中的节点

 */

public class Node {

    //存放节点数据

    int data;

    //指向左子节点

    Node left;

    //指向右子节点

    Node right;

    /**

     * @function 默认构造函数

     * @param data 节点数据

     */

    public Node(int data) {

        this.data = data;

        left = null;

        right = null;

    }

}

查找

而二叉查找树的查找过程为从根结点开始,如果查询的关键字与结点的关键字相等,那么就命中;否则,如果查询关键字比结点关键字小,就进入左儿子;如果比结点关键字大,就进入右儿子;如果左儿子或右儿子的指针为空,则报告找不到相应的关键字。

BST Search(keytype k, BST F){

    //在F所指的二叉查找树中查找关键字为k的记录。若成功,则返回响应结点的指针,否则返回空

    if(F == NULL) //查找失败

        return NULL;

    else if(k == F -> data.key){ //查找成功

        return F;

    }

    else if (k < F -> data.key){ //查找左子树

        return Search(k,F -> lchild);    

    }

    else if (k > F -> data.key){ //查找右子树

        return Search(k,F -> rchild);

    }

}

插入

把一个新的记录R插入到二叉查找树,应该保证在插入之后不破坏二叉查找树的结构性质。因此,为了执行插入操作首先应该查找R所在的位置。查找时,仍然采用上述的递归算法。若查找失败,则把包含R的结点插在具有空子树位置,若查找成功,则不执行插入,操作结束。

void Insert(records R, BST &F){

        //在F所指的二叉查找树中插入一个新纪录R

        if(F == NULL){

             F = new celltype;

             F -> data = R;

             F -> lchild = NULL;

             F -> rchild = NULL;

        }

        else if (R.key < F -> data.key){

             Insert(R,F -> lchild);

            }else if(R.key > F -> data.key){

             Insert(R,F -> rchild);

        }

        //如果 R.key == F -> data.key 则返回

    }

删除

删除叶节点

删除只有一个子节点的内部节点

删除有两个子节点的内部节点

如果我们进行简单的替换,那么可能碰到如下情况:

因此我们要在子树中选择一个合适的替换节点,替换节点一般来说会是右子树中的最小的节点:

Java 实现

BinarySearchTree的Java版本代码参考BinarySearchTree:

package wx.algorithm.search.bst;

/**
 * Created by apple on 16/7/29.
 */

/**
 * @function 二叉搜索树的示范代码
 */
public class BinarySearchTree {

    //指向二叉搜索树的根节点
    private Node root;

    //默认构造函数
    public BinarySearchTree() {
        this.root = null;
    }

    /**
     * @param id 待查找的值
     * @return
     * @function 默认搜索函数
     */
    public boolean find(int id) {

        //从根节点开始查询
        Node current = root;

        //当节点不为空
        while (current != null) {

            //是否已经查询到
            if (current.data == id) {
                return true;
            } else if (current.data > id) {
                //查询左子树
                current = current.left;
            } else {
                //查询右子树
                current = current.right;
            }
        }
        return false;
    }

    /**
     * @param id
     * @function 插入某个节点
     */
    public void insert(int id) {

        //创建一个新的节点
        Node newNode = new Node(id);

        //判断根节点是否为空
        if (root == null) {
            root = newNode;
            return;
        }

        //设置current指针指向当前根节点
        Node current = root;

        //设置父节点为空
        Node parent = null;

        //遍历直到找到第一个插入点
        while (true) {

            //先将父节点设置为当前节点
            parent = current;

            //如果小于当前节点的值
            if (id < current.data) {

                //移向左节点
                current = current.left;

                //如果当前节点不为空,则继续向下一层搜索
                if (current == null) {
                    parent.left = newNode;
                    return;
                }
            } else {

                //否则移向右节点
                current = current.right;

                //如果当前节点不为空,则继续向下一层搜索
                if (current == null) {
                    parent.right = newNode;
                    return;
                }
            }
        }
    }

    /**
     * @param id
     * @return
     * @function 删除树中的某个元素
     */
    public boolean delete(int id) {

        Node parent = root;
        Node current = root;

        //记录被找到的节点是父节点的左子节点还是右子节点
        boolean isLeftChild = false;

        //循环直到找到目标节点的位置,否则报错
        while (current.data != id) {
            parent = current;
            if (current.data > id) {
                isLeftChild = true;
                current = current.left;
            } else {
                isLeftChild = false;
                current = current.right;
            }
            if (current == null) {
                return false;
            }
        }

        //如果待删除的节点没有任何子节点
        //直接将该节点的原本指向该节点的指针设置为null
        if (current.left == null && current.right == null) {
            if (current == root) {
                root = null;
            }
            if (isLeftChild == true) {
                parent.left = null;
            } else {
                parent.right = null;
            }
        }

        //如果待删除的节点有一个子节点,且其为左子节点
        else if (current.right == null) {

            //判断当前节点是否为根节点
            if (current == root) {
                root = current.left;
            } else if (isLeftChild) {

                //挂载到父节点的左子树
                parent.left = current.left;
            } else {

                //挂载到父节点的右子树
                parent.right = current.left;
            }
        } else if (current.left == null) {
            if (current == root) {
                root = current.right;
            } else if (isLeftChild) {
                parent.left = current.right;
            } else {
                parent.right = current.right;
            }
        }

        //如果待删除的节点有两个子节点
        else if (current.left != null && current.right != null) {

            //寻找右子树中的最小值
            Node successor = getSuccessor(current);
            if (current == root) {
                root = successor;
            } else if (isLeftChild) {
                parent.left = successor;
            } else {
                parent.right = successor;
            }
            successor.left = current.left;
        }
        return true;
    }

    /**
     * @param deleleNode
     * @return
     * @function 在树种查找最合适的节点
     */
    private Node getSuccessor(Node deleleNode) {
        Node successsor = null;
        Node successsorParent = null;
        Node current = deleleNode.right;
        while (current != null) {
            successsorParent = successsor;
            successsor = current;
            current = current.left;
        }
        if (successsor != deleleNode.right) {
            successsorParent.left = successsor.right;
            successsor.right = deleleNode.right;
        }
        return successsor;
    }

    /**
     * @function 以中根顺序遍历树
     */
    public void display() {
        display(root);
    }

    private void display(Node node) {

        //判断当前节点是否为空
        if (node != null) {

            //首先展示左子树
            display(node.left);

            //然后展示当前根节点的值
            System.out.print(" " + node.data);

            //最后展示右子树的值
            display(node.right);
        }
    }

}

测试函数:

package wx.algorithm.search.bst;

import org.junit.Before;
import org.junit.Test;

/**
 * Created by apple on 16/7/30.
 */
public class BinarySearchTreeTest {

    BinarySearchTree binarySearchTree;

    @Before
    public void setUp() {
        binarySearchTree = new BinarySearchTree();
        binarySearchTree.insert(3);
        binarySearchTree.insert(8);
        binarySearchTree.insert(1);
        binarySearchTree.insert(4);
        binarySearchTree.insert(6);
        binarySearchTree.insert(2);
        binarySearchTree.insert(10);
        binarySearchTree.insert(9);
        binarySearchTree.insert(20);
        binarySearchTree.insert(25);
        binarySearchTree.insert(15);
        binarySearchTree.insert(16);
        System.out.println("原始的树 : ");
        binarySearchTree.display();
        System.out.println("");

    }

    @Test
    public void testFind() {

        System.out.println("判断4是否存在树中 : " + binarySearchTree.find(4));

    }

    @Test
    public void testInsert() {

    }

    @Test
    public void testDelete() {

        System.out.println("删除值为2的节点 : " + binarySearchTree.delete(2));
        binarySearchTree.display();

        System.out.println("\n 删除有一个子节点值为4的节点 : " + binarySearchTree.delete(4));
        binarySearchTree.display();

        System.out.println("\n 删除有两个子节点的值为10的节点 : " + binarySearchTree.delete(10));
        binarySearchTree.display();

    }

}

以上是Java实现二叉搜索树算法的代码详解(图)的详细内容。更多信息请关注PHP中文网其他相关文章!

声明
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn
JVM中的类加载程序子系统如何促进平台独立性?JVM中的类加载程序子系统如何促进平台独立性?Apr 23, 2025 am 12:14 AM

类加载器通过统一的类文件格式、动态加载、双亲委派模型和平台无关的字节码,确保Java程序在不同平台上的一致性和兼容性,实现平台独立性。

Java编译器会产生特定于平台的代码吗?解释。Java编译器会产生特定于平台的代码吗?解释。Apr 23, 2025 am 12:09 AM

Java编译器生成的代码是平台无关的,但最终执行的代码是平台特定的。1.Java源代码编译成平台无关的字节码。2.JVM将字节码转换为特定平台的机器码,确保跨平台运行但性能可能不同。

JVM如何处理不同操作系统的多线程?JVM如何处理不同操作系统的多线程?Apr 23, 2025 am 12:07 AM

多线程在现代编程中重要,因为它能提高程序的响应性和资源利用率,并处理复杂的并发任务。JVM通过线程映射、调度机制和同步锁机制,在不同操作系统上确保多线程的一致性和高效性。

在Java的背景下,'平台独立性”意味着什么?在Java的背景下,'平台独立性”意味着什么?Apr 23, 2025 am 12:05 AM

Java的平台独立性是指编写的代码可以在任何安装了JVM的平台上运行,无需修改。1)Java源代码编译成字节码,2)字节码由JVM解释执行,3)JVM提供内存管理和垃圾回收功能,确保程序在不同操作系统上运行。

Java应用程序仍然可以遇到平台特定的错误或问题吗?Java应用程序仍然可以遇到平台特定的错误或问题吗?Apr 23, 2025 am 12:03 AM

Javaapplicationscanindeedencounterplatform-specificissuesdespitetheJVM'sabstraction.Reasonsinclude:1)Nativecodeandlibraries,2)Operatingsystemdifferences,3)JVMimplementationvariations,and4)Hardwaredependencies.Tomitigatethese,developersshould:1)Conduc

云计算如何影响Java平台独立性的重要性?云计算如何影响Java平台独立性的重要性?Apr 22, 2025 pm 07:05 PM

云计算显着提升了Java的平台独立性。 1)Java代码编译为字节码,由JVM在不同操作系统上执行,确保跨平台运行。 2)使用Docker和Kubernetes部署Java应用,提高可移植性和可扩展性。

Java的平台独立性在广泛采用中扮演着什么角色?Java的平台独立性在广泛采用中扮演着什么角色?Apr 22, 2025 pm 06:53 PM

Java'splatformindependenceallowsdeveloperstowritecodeonceandrunitonanydeviceorOSwithaJVM.Thisisachievedthroughcompilingtobytecode,whichtheJVMinterpretsorcompilesatruntime.ThisfeaturehassignificantlyboostedJava'sadoptionduetocross-platformdeployment,s

容器化技术(例如Docker)如何影响Java平台独立性的重要性?容器化技术(例如Docker)如何影响Java平台独立性的重要性?Apr 22, 2025 pm 06:49 PM

容器化技术如Docker增强而非替代Java的平台独立性。1)确保跨环境的一致性,2)管理依赖性,包括特定JVM版本,3)简化部署过程,使Java应用更具适应性和易管理性。

See all articles

热AI工具

Undresser.AI Undress

Undresser.AI Undress

人工智能驱动的应用程序,用于创建逼真的裸体照片

AI Clothes Remover

AI Clothes Remover

用于从照片中去除衣服的在线人工智能工具。

Undress AI Tool

Undress AI Tool

免费脱衣服图片

Clothoff.io

Clothoff.io

AI脱衣机

Video Face Swap

Video Face Swap

使用我们完全免费的人工智能换脸工具轻松在任何视频中换脸!

热工具

禅工作室 13.0.1

禅工作室 13.0.1

功能强大的PHP集成开发环境

DVWA

DVWA

Damn Vulnerable Web App (DVWA) 是一个PHP/MySQL的Web应用程序,非常容易受到攻击。它的主要目标是成为安全专业人员在合法环境中测试自己的技能和工具的辅助工具,帮助Web开发人员更好地理解保护Web应用程序的过程,并帮助教师/学生在课堂环境中教授/学习Web应用程序安全。DVWA的目标是通过简单直接的界面练习一些最常见的Web漏洞,难度各不相同。请注意,该软件中

mPDF

mPDF

mPDF是一个PHP库,可以从UTF-8编码的HTML生成PDF文件。原作者Ian Back编写mPDF以从他的网站上“即时”输出PDF文件,并处理不同的语言。与原始脚本如HTML2FPDF相比,它的速度较慢,并且在使用Unicode字体时生成的文件较大,但支持CSS样式等,并进行了大量增强。支持几乎所有语言,包括RTL(阿拉伯语和希伯来语)和CJK(中日韩)。支持嵌套的块级元素(如P、DIV),

SublimeText3 英文版

SublimeText3 英文版

推荐:为Win版本,支持代码提示!

SublimeText3汉化版

SublimeText3汉化版

中文版,非常好用