算法二叉搜索树的实现与java

Question

我正在尝试使用Cormen的伪代码实现BST算法，但仍然存在问题

以下是我的节点代码：

public class Node {
    Node left;
    Node right;
    int value;

    Node(int value){
        this.value = value;
        this.left = null;
        this.right = null;  
    }
}

对于Bstree：

public class Btree {
    Node root;

    Btree(){
        this.root = null;
    }

    public static void inorderWalk(Node n){
        if(n != null){
            inorderWalk(n.left);
            System.out.print(n.value + " ");
            inorderWalk(n.right);
        }
    }

    public static Node getParent(Btree t, Node n){
        Node current = t.root;
        Node parent = null;


        while(true){
            if (current == null)
                return null;

            if( current.value == n.value ){
                break;
            }

            if (current.value > n.value){
                parent = current;
                current = current.left;
            }
            else{ //(current.value < n.value)
                parent = current;
                current = current.right;
            }       
        }
        return parent;
    }


    public static Node search(Node n,int key){
        if(n == null || key == n.value ){
            return n;
        }
        if(key < n.value){
            return search(n.left,key);
        }
        else{
            return search(n.right,key);

        }
    }

    public static Node treeMinimum(Node x){
        if(x == null){
            return null;
        }


        while(x.left != null){
            x = x.left;
        }
        return x;
    }

    public static Node treeMaximum(Node x){
        if(x == null){
            return null;
        }

        while(x.right != null){
            x = x.right;
        }
        return x;   
    }

    public static Node treeSuccessor(Btree t,Node x){
        if (x.right == null){
            return treeMinimum(x.right);
        }
        Node y = getParent(t,x);
        while(y != null && x == y.right){
            x = y;
            y = getParent(t,y);
        }
        return y;   
    }

    public static Btree insert(Btree t,Node z){
        Node y = null;
        Node x = t.root;

        while(x != null){
            y = x;
            if(z.value < x.value)
                x = x.left;
            else
                x = x.right;
        }
        Node tmp = getParent(t,z);
        tmp = y;
        if(y == null){
            t.root = z;
        }
        else if(z.value < y.value)
            y.left = z;
        else
            y.right = z;

        return t;
    }


    public static Btree delete(Btree t,Node z){
        Node y,x;
        if (z.left == null || z.right == null)
            y = z;
        else
            y = treeSuccessor(t,z);

        if (y.left != null)
            x = y.left;
        else
            x = y.right;
        if (x != null){
            Node tmp = getParent(t,x);
            tmp = getParent(t,y);
        }

        if (getParent(t,y) == null ){
            t.root = x;
        }
        else{
            if( y == getParent(t,y).left ){
                getParent(t,y).left = x;
            }
            else{
                getParent(t,y).right = x;

            }
    }
        if(y != z){
            z.value = y.value;
        }
    return t;
}

public static void main(String[] args){
    Btree test = new Btree(); 
    Node n1 = new Node(6);
    Node n2 = new Node(3);
    Node n3 = new Node(9);
    Node n4 = new Node(1);
    Node n5 = new Node(16);
    Node n6 = new Node(4);
    Node n7 = new Node(2);
    Node n8 = new Node(11);
    Node n9 = new Node(13);


    test = insert(test,n1);
    test = insert(test,n2);
    test = insert(test,n3);
    test = insert(test,n4);
    test = insert(test,n5);
    test = insert(test,n6);
    test = insert(test,n7);
    test = insert(test,n8);
    test = insert(test,n9);
    inorderWalk(test.root);
    System.out.println();
    test = delete(test,n8);
    inorderWalk(test.root);

    System.out.println();
    test = delete(test,n5);
    inorderWalk(test.root);

    System.out.println();
    test = delete(test,n2);
    inorderWalk(test.root);

    System.out.println();
    test = delete(test,n1);
    inorderWalk(test.root);




}

}

主要问题是删除部分，有时它按预期工作，有时删除错误，有时删除空指针异常。问题是什么

附：这不是家庭作业

Answer 1

首先，您的实现与面向对象无关（除了使用对象）。例如，插入和删除操作应该在树上操作

此外，我建议将节点类实现为树类的静态成员

public class Tree {
    private Node root = null;

    // remainder omitted

    public boolean insert(int element) {
        if (isEmpty()) {
            root = new Node(element);

            return true; // empty tree, Node could be inserted, return true
        }

         Node current = root; // start at root
         Node parent;         // the current Node's parent

         do {
             parent = current;

             if (element < current.element) {
                 current = current.left; // go to left
             } else if (element > current.element) {
                 current = current.right; // go to right
             } else {
                 return false;  // duplicates are NOT allowed, element could not be inserted -> return false

         } while (current != null);

         Node node = new Node(element);

         if (element < current.element) {
             parent.left = node;
         } else {
             parent.right = node;
         }

         return true; // node successfully inserted
    }

    public boolean isEmpty() {
        return root == null;
    }

    private static class Node { // static member class
        Node left  = null;
        Node right = null;
        final int element;

        Node(int element) {
            this.element = element;
        }
    }
}

Answer 2

代码中的一些直接问题：你的treeSuccessor以

    if (x.right == null){
        return treeMinimum(x.right);
    }

当然应该是if (x.right != null)

你的insert代码有以下行

    Node tmp = getParent(t,z);
    tmp = y;

分配给tmp并立即再次分配给它。在我看来，你根本不需要这些行，因为你不再使用tmp。此时，y是插入其子节点z的节点，所以只需删除这些行即可

同样，在delete中，您有行

    if (x != null){
        Node tmp = getParent(t,x);
        tmp = getParent(t,y);
    }

实际上你什么都不做，因为tmp在这个片段之外是不可见的。然后，在delete中，重复getParent(t,y)表达式，这可能是一个昂贵的操作，因此只需计算一次，并将其分配给某个变量

但总体而言，您的代码虽然看起来是正确的（可能除了delete，我不完全理解它，但看起来可疑），但与典型的二叉树代码不太相似。你并不真的需要getParent和treeSuccessor方法来实现search、insert和delete。对search的基本结构也适用于其他结构，但有以下修改：

• 使用insert时，当您到达null链接时，不要返回null，而是将元素插入到该点
• 使用delete，当您找到元素时，如果它只有一个子元素（或没有子元素），则将其替换为该子元素；如果它有两个子元素，则将其替换为左子树的最大值或右子树的最小值

除此之外，这两种方法都需要在下降到树中时跟踪父节点，但这是对search进行的唯一修改。特别是，永远不需要在树中往上走（这treeSuccessor就可以了）

Answer 3

我得站在Anon一边去重写。空指针来自getParent函数（它显式地返回空值以及其他内容）。因此，我将从这里开始，并修复函数，以便它们返回一件事，并且只在函数末尾返回一件事

Answer 4

。。。你的删除代码怎么了？这没有多大意义。我会考虑用更合乎逻辑的方式改写它。没有无意义的单字母变量名。并添加评论

一种可能的算法是：

Get the parent of the node to delete
Get the right-most node of the left subtree, or the leftmost node of the right subtree
Remove the node to delete and replace it with the node you found
Rebalance the tree

。。。或者，如果你想破解这些东西，所以它是正确的，我会开始看

if (x != null){
    Node tmp = getParent(t,x);
    tmp = getParent(t,y);
}

部分原因是，这显然是错误的

Answer 5

以下是Java中二进制搜索树的完整实现 插入、搜索、countNodes、遍历、删除、清空、最大值&；最小节点、查找父节点、打印所有叶节点、获取标高、获取高度、获取深度、打印左视图、镜像视图

import java.util.NoSuchElementException;
import java.util.Scanner;

import org.junit.experimental.max.MaxCore;

class BSTNode {

    BSTNode left = null;
    BSTNode rigth = null;
    int data = 0;

    public BSTNode() {
        super();
    }

    public BSTNode(int data) {
        this.left = null;
        this.rigth = null;
        this.data = data;
    }

    @Override
    public String toString() {
        return "BSTNode [left=" + left + ", rigth=" + rigth + ", data=" + data + "]";
    }

}


class BinarySearchTree {

    BSTNode root = null;

    public BinarySearchTree() {

    }

    public void insert(int data) {
        BSTNode node = new BSTNode(data);
        if (root == null) {
            root = node;
            return;
        }

        BSTNode currentNode = root;
        BSTNode parentNode = null;

        while (true) {
            parentNode = currentNode;
            if (currentNode.data == data)
                throw new IllegalArgumentException("Duplicates nodes note allowed in Binary Search Tree");

            if (currentNode.data > data) {
                currentNode = currentNode.left;
                if (currentNode == null) {
                    parentNode.left = node;
                    return;
                }
            } else {
                currentNode = currentNode.rigth;
                if (currentNode == null) {
                    parentNode.rigth = node;
                    return;
                }
            }
        }
    }

    public int countNodes() {
        return countNodes(root);
    }

    private int countNodes(BSTNode node) {
        if (node == null) {
            return 0;
        } else {
            int count = 1;
            count += countNodes(node.left);
            count += countNodes(node.rigth);
            return count;
        }
    }

    public boolean searchNode(int data) {
        if (empty())
            return empty();
        return searchNode(data, root);
    }

    public boolean searchNode(int data, BSTNode node) {
        if (node != null) {
            if (node.data == data)
                return true;
            else if (node.data > data)
                return searchNode(data, node.left);
            else if (node.data < data)
                return searchNode(data, node.rigth);
        }
        return false;
    }

    public boolean delete(int data) {
        if (empty())
            throw new NoSuchElementException("Tree is Empty");

        BSTNode currentNode = root;
        BSTNode parentNode = root;
        boolean isLeftChild = false;

        while (currentNode.data != data) {
            parentNode = currentNode;
            if (currentNode.data > data) {
                isLeftChild = true;
                currentNode = currentNode.left;
            } else if (currentNode.data < data) {
                isLeftChild = false;
                currentNode = currentNode.rigth;
            }
            if (currentNode == null)
                return false;
        }

        // CASE 1: node with no child
        if (currentNode.left == null && currentNode.rigth == null) {
            if (currentNode == root)
                root = null;
            if (isLeftChild)
                parentNode.left = null;
            else
                parentNode.rigth = null;
        }

        // CASE 2: if node with only one child
        else if (currentNode.left != null && currentNode.rigth == null) {
            if (root == currentNode) {
                root = currentNode.left;
            }
            if (isLeftChild)
                parentNode.left = currentNode.left;
            else
                parentNode.rigth = currentNode.left;
        } else if (currentNode.rigth != null && currentNode.left == null) {
            if (root == currentNode)
                root = currentNode.rigth;
            if (isLeftChild)
                parentNode.left = currentNode.rigth;
            else
                parentNode.rigth = currentNode.rigth;
        }

        // CASE 3: node with two child
        else if (currentNode.left != null && currentNode.rigth != null) {

            // Now we have to find minimum element in rigth sub tree
            // that is called successor
            BSTNode successor = getSuccessor(currentNode);
            if (currentNode == root)
                root = successor;
            if (isLeftChild)
                parentNode.left = successor;
            else
                parentNode.rigth = successor;
            successor.left = currentNode.left;
        }

        return true;
    }

    private BSTNode getSuccessor(BSTNode deleteNode) {

        BSTNode successor = null;
        BSTNode parentSuccessor = null;
        BSTNode currentNode = deleteNode.left;

        while (currentNode != null) {
            parentSuccessor = successor;
            successor = currentNode;
            currentNode = currentNode.left;
        }

        if (successor != deleteNode.rigth) {
            parentSuccessor.left = successor.left;
            successor.rigth = deleteNode.rigth;
        }

        return successor;
    }

    public int nodeWithMinimumValue() {
        return nodeWithMinimumValue(root);
    }

    private int nodeWithMinimumValue(BSTNode node) {
        if (node.left != null)
            return nodeWithMinimumValue(node.left);
        return node.data;
    }

    public int nodewithMaximumValue() {
        return nodewithMaximumValue(root);
    }

    private int nodewithMaximumValue(BSTNode node) {
        if (node.rigth != null)
            return nodewithMaximumValue(node.rigth);
        return node.data;
    }

    public int parent(int data) {
        return parent(root, data);
    }

    private int parent(BSTNode node, int data) {
        if (empty())
            throw new IllegalArgumentException("Empty");
        if (root.data == data)
            throw new IllegalArgumentException("No Parent node found");

        BSTNode parent = null;
        BSTNode current = node;

        while (current.data != data) {
            parent = current;
            if (current.data > data)
                current = current.left;
            else
                current = current.rigth;
            if (current == null)
                throw new IllegalArgumentException(data + " is not a node in tree");
        }
        return parent.data;
    }

    public int sibling(int data) {
        return sibling(root, data);
    }

    private int sibling(BSTNode node, int data) {
        if (empty())
            throw new IllegalArgumentException("Empty");
        if (root.data == data)
            throw new IllegalArgumentException("No Parent node found");

        BSTNode cureent = node;
        BSTNode parent = null;
        boolean isLeft = false;

        while (cureent.data != data) {
            parent = cureent;
            if (cureent.data > data) {
                cureent = cureent.left;
                isLeft = true;
            } else {
                cureent = cureent.rigth;
                isLeft = false;
            }
            if (cureent == null)
                throw new IllegalArgumentException("No Parent node found");
        }
        if (isLeft) {
            if (parent.rigth != null) {
                return parent.rigth.data;
            } else
                throw new IllegalArgumentException("No Sibling is there");
        } else {
            if (parent.left != null)
                return parent.left.data;
            else
                throw new IllegalArgumentException("No Sibling is there");
        }
    }

    public void leafNodes() {
        if (empty())
            throw new IllegalArgumentException("Empty");
        leafNode(root);
    }

    private void leafNode(BSTNode node) {
        if (node == null)
            return;
        if (node.rigth == null && node.left == null)
            System.out.print(node.data + " ");
        leafNode(node.left);
        leafNode(node.rigth);
    }

    public int level(int data) {
        if (empty())
            throw new IllegalArgumentException("Empty");
        return level(root, data, 1);
    }

    private int level(BSTNode node, int data, int level) {
        if (node == null)
            return 0;
        if (node.data == data)
            return level;
        int result = level(node.left, data, level + 1);
        if (result != 0)
            return result;
        result = level(node.rigth, data, level + 1);
        return result;
    }

    public int depth() {
        return depth(root);
    }

    private int depth(BSTNode node) {
        if (node == null)
            return 0;
        else
            return 1 + Math.max(depth(node.left), depth(node.rigth));
    }

    public int height() {
        return height(root);
    }

    private int height(BSTNode node) {
        if (node == null)
            return 0;
        else
            return 1 + Math.max(height(node.left), height(node.rigth));
    }

    public void leftView() {
        leftView(root);
    }

    private void leftView(BSTNode node) {
        if (node == null)
            return;
        int height = height(node);

        for (int i = 1; i <= height; i++) {
            printLeftView(node, i);
        }
    }

    private boolean printLeftView(BSTNode node, int level) {
        if (node == null)
            return false;

        if (level == 1) {
            System.out.print(node.data + " ");
            return true;
        } else {
            boolean left = printLeftView(node.left, level - 1);
            if (left)
                return true;
            else
                return printLeftView(node.rigth, level - 1);
        }
    }

    public void mirroeView() {
        BSTNode node = mirroeView(root);
        preorder(node);
        System.out.println();
        inorder(node);
        System.out.println();
        postorder(node);
        System.out.println();
    }

    private BSTNode mirroeView(BSTNode node) {
        if (node == null || (node.left == null && node.rigth == null))
            return node;

        BSTNode temp = node.left;
        node.left = node.rigth;
        node.rigth = temp;

        mirroeView(node.left);
        mirroeView(node.rigth);
        return node;
    }

    public void preorder() {
        preorder(root);
    }

    private void preorder(BSTNode node) {
        if (node != null) {
            System.out.print(node.data + " ");
            preorder(node.left);
            preorder(node.rigth);
        }
    }

    public void inorder() {
        inorder(root);
    }

    private void inorder(BSTNode node) {
        if (node != null) {
            inorder(node.left);
            System.out.print(node.data + " ");
            inorder(node.rigth);
        }
    }

    public void postorder() {
        postorder(root);
    }

    private void postorder(BSTNode node) {
        if (node != null) {
            postorder(node.left);
            postorder(node.rigth);
            System.out.print(node.data + " ");
        }
    }

    public boolean empty() {
        return root == null;
    }

}

public class BinarySearchTreeTest {
    public static void main(String[] l) {
        System.out.println("Weleome to Binary Search Tree");
        Scanner scanner = new Scanner(System.in);
        boolean yes = true;
        BinarySearchTree tree = new BinarySearchTree();
        do {
            System.out.println("\n1. Insert");
            System.out.println("2. Search Node");
            System.out.println("3. Count Node");
            System.out.println("4. Empty Status");
            System.out.println("5. Delete Node");
            System.out.println("6. Node with Minimum Value");
            System.out.println("7. Node with Maximum Value");
            System.out.println("8. Find Parent node");
            System.out.println("9. Count no of links");
            System.out.println("10. Get the sibling of any node");
            System.out.println("11. Print all the leaf node");
            System.out.println("12. Get the level of node");
            System.out.println("13. Depth of the tree");
            System.out.println("14. Height of Binary Tree");
            System.out.println("15. Left View");
            System.out.println("16. Mirror Image of Binary Tree");
            System.out.println("Enter Your Choice :: ");
            int choice = scanner.nextInt();
            switch (choice) {
            case 1:
                try {
                    System.out.println("Enter Value");
                    tree.insert(scanner.nextInt());
                } catch (Exception e) {
                    System.out.println(e.getMessage());
                }
                break;

            case 2:
                System.out.println("Enter the node");
                System.out.println(tree.searchNode(scanner.nextInt()));
                break;

            case 3:
                System.out.println(tree.countNodes());
                break;

            case 4:
                System.out.println(tree.empty());
                break;

            case 5:
                try {
                    System.out.println("Enter the node");
                    System.out.println(tree.delete(scanner.nextInt()));
                } catch (Exception e) {
                    System.out.println(e.getMessage());
                }

            case 6:
                try {
                    System.out.println(tree.nodeWithMinimumValue());
                } catch (Exception e) {
                    System.out.println(e.getMessage());
                }
                break;

            case 7:
                try {
                    System.out.println(tree.nodewithMaximumValue());
                } catch (Exception e) {
                    System.out.println(e.getMessage());
                }
                break;

            case 8:
                try {
                    System.out.println("Enter the node");
                    System.out.println(tree.parent(scanner.nextInt()));
                } catch (Exception e) {
                    System.out.println(e.getMessage());
                }
                break;

            case 9:
                try {
                    System.out.println(tree.countNodes() - 1);
                } catch (Exception e) {
                    System.out.println(e.getMessage());
                }
                break;

            case 10:
                try {
                    System.out.println("Enter the node");
                    System.out.println(tree.sibling(scanner.nextInt()));
                } catch (Exception e) {
                    System.out.println(e.getMessage());
                }
                break;

            case 11:
                try {
                    tree.leafNodes();
                } catch (Exception e) {
                    System.out.println(e.getMessage());
                }

            case 12:
                try {
                    System.out.println("Enter the node");
                    System.out.println("Level is : " + tree.level(scanner.nextInt()));
                } catch (Exception e) {
                    System.out.println(e.getMessage());
                }
                break;

            case 13:
                try {
                    System.out.println(tree.depth());
                } catch (Exception e) {
                    System.out.println(e.getMessage());
                }
                break;

            case 14:
                try {
                    System.out.println(tree.height());
                } catch (Exception e) {
                    System.out.println(e.getMessage());
                }
                break;

            case 15:
                try {
                    tree.leftView();
                    System.out.println();
                } catch (Exception e) {
                    System.out.println(e.getMessage());
                }
                break;

            case 16:
                try {
                    tree.mirroeView();
                } catch (Exception e) {
                    System.out.println(e.getMessage());
                }
                break;

            default:
                break;
            }
            tree.preorder();
            System.out.println();
            tree.inorder();
            System.out.println();
            tree.postorder();
        } while (yes);
        scanner.close();
    }
}

Answer 6

根据我对二进制搜索树的理解，下面的实现已经完成，敬请关注 并让我知道任何需要的反馈

1. 插入
2. 有序旅行
3. 搜索
4. 移除

请看一下主要的方法。因此，请提供您的反馈，以便我方进一步改进

public class BinarySearchTree {

    private Node root;

    public  BinarySearchTree() {
        root = null;        
    }
    public BinarySearchTree(int rootData) {
        root = new Node(rootData);
    }

    public void insertElement(int element,Node parent) {

        Node temp = root;
        if(parent!=null) temp = parent;

        if(temp!=null) {
            Node node = new Node(element);
            if(element<temp.getData()) {
                if(temp.getLeft()!=null)
                    insertElement(element, temp.getLeft());
                else
                    temp.setLeft(node);
            }else if(element>temp.getData()) {              
                if(temp.getRight()!=null)
                    insertElement(element, temp.getRight());
                else
                    temp.setRight(node);
            }
        }
    }


    public void traverseInOrder() {
        if(root!=null) {
            traverse(root.getLeft());
            System.out.println(root.getData());
            traverse(root.getRight());
        }
    }

    public void traverse(Node temp) {       
        if(temp!=null) {
            traverse(temp.getLeft());
            System.out.println(temp.getData());
            traverse(temp.getRight());

        }
    }

    public int searchElement(int element,Node node) {

        Node temp = root;
        if(node!=null) temp = node;
        if(temp!=null) {
            if(temp.getData()<element) {
                if(temp.getRight()!=null)
                    return searchElement(element, temp.getRight());             
            }else if(temp.getData()>element) {
                if(temp.getLeft()!=null)
                    return searchElement(element,temp.getLeft());
            }else if(temp.getData()==element){
                return temp.getData();
            }
        }
        return -1;
    }


    public void remove(int element,Node node,Node predecer) {

        Node temp = root;
        if(node!=null) temp = node;

        if(temp!=null) {
            if(temp.getData()>element) {
                remove(element, temp.getLeft(), temp);
            }else if(temp.getData()<element) {
                remove(element, temp.getRight(), temp);
            }else if(element==temp.getData()) {
                if(temp.getLeft()==null && temp.getRight()==null) {
                    if(predecer.getData()>temp.getData()) {
                        predecer.setLeft(null);
                    }else if(predecer.getData()<temp.getData()) {
                        predecer.setRight(null);
                    }
                }else if(temp.getLeft()!=null && temp.getRight()==null) {
                    predecer.setRight(temp.getLeft());
                }else if(temp.getLeft()==null && temp.getRight()!=null) {
                    predecer.setLeft(temp.getRight());
                }else if(temp.getLeft()!=null && temp.getRight()!=null) {
                    Node leftMostElement = findMaximumLeft(temp.getLeft());
                    if(leftMostElement!=null) {
                        remove(leftMostElement.getData(), temp, temp);
                        temp.setData(leftMostElement.getData());
                    }
                }
            }
        }
    }
    
    public Node findMaximumLeft(Node parent) {
        Node temp = parent;
        if(temp.getRight()!=null)
            return findMaximumLeft(temp.getRight());
        else 
            return temp;

    }
    public static void main(String[] args) {
        BinarySearchTree bs = new BinarySearchTree(10);
        bs.insertElement(29, null);
        bs.insertElement(19, null);
        bs.insertElement(209, null);
        bs.insertElement(6, null);
        bs.insertElement(7, null);
        bs.insertElement(17, null);
        bs.insertElement(37, null);
        bs.insertElement(67, null);
        bs.insertElement(-7, null);

        bs.remove(6, null, null);
        bs.traverseInOrder();}}