文章详情

短信预约-IT技能 免费直播动态提醒

请输入下面的图形验证码

提交验证

短信预约提醒成功

Java实现二分查找树及其相关操作

2024-04-02 19:55

关注

二分查找树(Binary Search Tree)的基本操作有搜索、求最大值、求最小值、求前驱、求后继、插入及删除。

对二分查找树的进行基本操作所花费的时间与树的高度成比例。例如有n个节点的完全二叉树,对它进行的基本操作的时间复杂度为O(logn)。然而,如果树是一个有n个节点的线性的链,则在这种情况下的时间复杂度为O(n)。

1、什么是二分查找树

二分查找树是一种有组织的二叉树。我们可以通过链接节点表示这样一棵树。每个节点包含键(key),数据(data),左子节点(left),右子节点(right),父节点(parent)这五种属性。

如果一个节点没有父节点或某个子结点,则其对应的属性的值为null。

创建一个Node.java文件,用如下代码表示节点:


public class Node {
    public int key;
    public int data;
    public Node left;
    public Node right;
    public Node parent;
    
    public Node(){}
    
    public Node(int key) {
        this.key = key;
    }
}

创建一个BinarySearchTree.java文件,用如下代码表示二分查找树:


public class BinarySearchTree {
    public Node root;
}

接下来,会逐步补充代码。

对于存储在二分查找树中的键,必须满足下面这个条件(二分查找树特点)

对于二叉树中的任一节点n,如果left是n左子树中的任何一个节点,有left.key <= n.key;如果right是n右子树中的任一节点,则有n.key<=right.key。

如果我们中序遍历二分查找树,能升序打印出所有的键(key)。

可在BinarySearchTree.java文件中加上如下代码实现中序遍历:


private void innerWalk(Node node) {
        if(node != null) {
            innerWalk(node.left);
            System.out.print(node.key + " ");
            innerWalk(node.right);
        }
    }

    public void innerWalk() {
        this.innerWalk(this.root);
        System.out.println();
    }

2、查询二分查找树

2.1、搜索

在二分查找树中搜索键为key的结点,如果找到,则返回该结点,否则,返回null。可利用二分查找树的特性来查找。

可在BinarySearchTree.java文件中加上如下代码实现搜索:


public Node search(int key) {
        Node pointer = this.root;
        while (pointer != null && pointer.key != key) {
            pointer = key < pointer.key ? pointer.left : pointer.right;
        }
        return pointer;
    }

2.2、最小值与最大值

求键最小的节点,可根据二叉树的特点,从根结点开始,遍历跟踪其左子节点,直到最后一个。

可在Node.java文件中加上如下代码实现:


 public Node minimum() {
        Node pointer = this;
        while(pointer.left != null){
            pointer = pointer.left;
        }
        return pointer;
    }

在BinarySearchTree.java文件中加上如下代码:


public Node minimum() {
        return this.root.minimum();
    }

求键最大的节点,可根据二叉树的特点,从根结点开始,遍历跟踪其右子节点,直到最后一个。

可在Node.java文件中加上如下代码实现:


 public Node maximum() {
        Node pointer = this;
        while(pointer.right != null) {
            pointer = pointer.right;
        }
        return pointer;
    }

在BinarySearchTree.java文件中加上如下代码:


public Node minimum() {
        return this.root.maximum();
    }

2.3、前驱与后继

给定一个二分查找树中的节点,有时我们需要发现它在树中所有结点按键升序排序的情况下的直接后继(后面第一个)。

如果树中所有的键是不同的,结点n的直接后继是大于n.key的最小结点。

如果该结点有右节点,则其直接后继是其右子树键最小的那个结点。如果该结点则判断该结点是其父节点的左子节点还是其右子节点。

如果是左子节点,则返回其父节点。如果是右子节点,判断其父节点的其父节点的父节点的左子节点还是右子节点,以此类推。

如果找不到,则返回null。

可在Node.java文件中加上如下实现代码:


public Node successor() {
        Node pointer = this;
        if (pointer.right != null)
            return pointer.right.minimum();
        Node parentPointer = pointer.parent;
        while (parentPointer != null && parentPointer.right == pointer) {
            pointer = parentPointer;
            parentPointer = parentPointer.parent;
        }
        return pointer;
    }

一个节点的直接前继是指树中所有结点按键升序排序的情况下,该节点的前面第一个。求直接前继的与求直接后继是对称的。

可在Node.java文件中加上如下实现代码:


 public Node predecessor() {
        Node pointer = this;
        if (pointer.left != null)
            return pointer.left.maximum();
        Node parentPointer = pointer.parent;
        while (parentPointer != null && parentPointer.left == pointer) {
            pointer = parentPointer;
            parentPointer = parentPointer.parent;
        }
        return pointer;
    }

3、插入与删除

插入与删除会导致二分查找树发生改变,但必须保持其特点。

3.1、插入

在树中找到一个键(key)最接近要插入结点键(key)的结点,且有可以插入的位置,然后插入合适的位置。

可在BinarySearchTree.java文件中加上如下实现代码:


 public void insert(Node node) {
        Node pointer = this.root;
        Node parentPointer = null;
        while (pointer != null) {
            parentPointer = pointer;
            pointer = node.key < pointer.key ? pointer.left : pointer.right;
        }
        node.parent = parentPointer;
        if (parentPointer == null)
            this.root = node;
        else if (node.key < parentPointer.key) {
            parentPointer.left = node;
        } else {
            parentPointer.right = node;
        }
    }

3.2、删除

删除节点后,我门要保持二分查找树的特点。

如果要删除节点没有任何子节点,直接可以删除它,不用做任何处理。

如果要删除节点只有一个左子树,可以用左子树的根节点代替要删除节点,也可以用左子树中键(key)最大的节点来代替要删除节点。

如果要删除结点只有一个右子树,可以用右子树的根节点代替要删除节点,也可以用右子树中键(key)最小的结点来代替要删除结点。

如果要删除结点既有左子树,又有右子树,可以用左子树中键(key)最大的结点代替要删除结点,也可以用右子树中键最小的结点代替要删除结点。

假设要从二分查找树tree中删除节点node,一种删除方法的具体步骤如下:

如果s是node的右子节点,可以用s代替node。
否则,用s的右子节点代替s,然后再用s代替node。

由于我们需要在二分查找树中替换子树的方法,可以先写一个替换子树的方法。

可在BinarySearchTree.java文件中加上如下实现代码:



    private void transplant(Node node1, Node node2) {
        if (node1.parent == null) {
            this.root = node2;
        } else if (node1.parent.left == node1) {
            node1.parent.left = node2;
        } else {
            node1.parent.right = node2;
        }

        if (node2 != null)
            node2.parent = node1.parent;
        node1.parent = null;
    }

接下来解释删除节点操作的代码实现。

可在BinarySearchTree.java文件中加上如下实现代码:


 public void delete(Node node) {
        if (node.left == null) {
            this.transplant(node, node.right);
        } else if (node.right == null) {
            this.transplant(node, node.left);
        } else {
            Node successor = node.successor();
            if (successor.parent != node) {
                this.transplant(successor, successor.right);
                successor.right = node.right;
                successor.right.parent = successor;
            }
            this.transplant(node, successor);
            successor.left = node.left;
            successor.left.parent = successor;
        }
    }

4、完整代码

Node.java文件


public class Node {
    public int key;
    public int data;
    public Node left;
    public Node right;
    public Node parent;

    public Node() {
    }

    public Node(int key) {
        this.key = key;
    }

    public Node minimum() {
        Node pointer = this;
        while (pointer.left != null)
            pointer = pointer.left;
        return pointer;
    }

    public Node maximum() {
        Node pointer = this;
        while (pointer.right != null)
            pointer = pointer.right;
        return pointer;
    }

    public Node successor() {
        Node pointer = this;
        if (pointer.right != null)
            return pointer.right.minimum();
        Node parentPointer = pointer.parent;
        while (parentPointer != null && parentPointer.right == pointer) {
            pointer = parentPointer;
            parentPointer = parentPointer.parent;
        }
        return pointer;
    }

    public Node predecessor() {
        Node pointer = this;
        if (pointer.left != null)
            return pointer.left.maximum();
        Node parentPointer = pointer.parent;
        while (parentPointer != null && parentPointer.left == pointer) {
            pointer = parentPointer;
            parentPointer = parentPointer.parent;
        }
        return pointer;
    }
}

BinarySearchTree.java文件


public class BinarySearchTree {
    public Node root;

    private void innerWalk(Node node) {
        if (node != null) {
            innerWalk(node.left);
            System.out.print(node.key + " ");
            innerWalk(node.right);
        }
    }

    public void innerWalk() {
        this.innerWalk(this.root);
        System.out.println();
    }

    public Node search(int key) {
        Node pointer = this.root;
        while (pointer != null && pointer.key != key) {
            pointer = key < pointer.key ? pointer.left : pointer.right;
        }
        return pointer;
    }

    public Node minimum() {
        return this.root.minimum();
    }

    public Node maximum() {
        return this.root.maximum();
    }

    public void insert(Node node) {
        Node pointer = this.root;
        Node parentPointer = null;
        while (pointer != null) {
            parentPointer = pointer;
            pointer = node.key < pointer.key ? pointer.left : pointer.right;
        }
        node.parent = parentPointer;
        if (parentPointer == null)
            this.root = node;
        else if (node.key < parentPointer.key) {
            parentPointer.left = node;
        } else {
            parentPointer.right = node;
        }
    }

    
    private void transplant(Node node1, Node node2) {
        if (node1.parent == null) {
            this.root = node2;
        } else if (node1.parent.left == node1) {
            node1.parent.left = node2;
        } else {
            node1.parent.right = node2;
        }

        if (node2 != null)
            node2.parent = node1.parent;
        node1.parent = null;
    }

    public void delete(Node node) {
        if (node.left == null) {
            this.transplant(node, node.right);
        } else if (node.right == null) {
            this.transplant(node, node.left);
        } else {
            Node successor = node.successor();
            if (successor.parent != node) {
                this.transplant(successor, successor.right);
                successor.right = node.right;
                successor.right.parent = successor;
            }
            this.transplant(node, successor);
            successor.left = node.left;
            successor.left.parent = successor;
        }
    }
}

5、演示

演示代码


public class Test01 {
    public static void main(String[] args) {
        Node n1 = new Node(1);
        Node n2 = new Node(2);
        Node n3 = new Node(3);
        Node n4 = new Node(4);
        Node n5 = new Node(5);

        BinarySearchTree bst = new BinarySearchTree();
        bst.insert(n3);
        bst.insert(n4);
        bst.insert(n2);
        bst.insert(n1);
        bst.insert(n5);

        System.out.println("bst.minimum().key: " + bst.minimum().key);
        System.out.println("bst.maximum().key: " + bst.maximum().key);
        System.out.println("n3.successor().key: " + n3.successor().key);
        System.out.println("n3.predecessor().key: " + n3.predecessor().key);
        System.out.println("bst.search(4).key: " + bst.search(4).key);

        System.out.print("tree: ");
        bst.innerWalk();
        System.out.print("delete n3: ");
        bst.delete(n3);
        bst.innerWalk();
        System.out.print("delete n2: ");
        bst.delete(n2);
        bst.innerWalk();
        System.out.print("delete n1: ");
        bst.delete(n1);
        bst.innerWalk();
        System.out.print("delete n4: ");
        bst.delete(n4);
        bst.innerWalk();
        System.out.print("delete n5: ");
        bst.delete(n5);
        bst.innerWalk();
    }
}

结果

bst.minimum().key: 1
bst.maximum().key: 5
n3.successor().key: 4
n3.predecessor().key: 2
bst.search(4).key: 4
tree: 1 2 3 4 5
delete n3: 1 2 4 5
delete n2: 1 4 5
delete n1: 4 5
delete n4: 5
delete n5:

到此这篇关于Java实现二分查找树及其相关操作的文章就介绍到这了,更多相关java二分查找树内容请搜索编程网以前的文章或继续浏览下面的相关文章希望大家以后多多支持编程网!

阅读原文内容投诉

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

软考中级精品资料免费领

  • 历年真题答案解析
  • 备考技巧名师总结
  • 高频考点精准押题
  • 2024年上半年信息系统项目管理师第二批次真题及答案解析(完整版)

    难度     813人已做
    查看
  • 【考后总结】2024年5月26日信息系统项目管理师第2批次考情分析

    难度     354人已做
    查看
  • 【考后总结】2024年5月25日信息系统项目管理师第1批次考情分析

    难度     318人已做
    查看
  • 2024年上半年软考高项第一、二批次真题考点汇总(完整版)

    难度     435人已做
    查看
  • 2024年上半年系统架构设计师考试综合知识真题

    难度     224人已做
    查看

相关文章

发现更多好内容

猜你喜欢

AI推送时光机
位置:首页-资讯-后端开发
咦!没有更多了?去看看其它编程学习网 内容吧
首页课程
资料下载
问答资讯