如何在二叉搜索树java中添加delete方法

kzmpq1sx  于 2021-07-11  发布在  Java
关注(0)|答案(2)|浏览(380)

我正在创建一个二叉搜索树delete node方法,到目前为止,我有一个查找max和min的方法,还有insert方法。
你能给我一个大概的算法吗。。。
这是我目前的工作

public class BST {
    private Node root; //first node top of the tree

    public void insert(int key){
        Node newNode = new Node (key);
            if(root == null){ //check node, no tree yet
                root = newNode; //give the tree a node
            } 

            else {
                Node current = root; //assigned root as current
                Node parent;
                while(true) {
                    parent = current;
                    if (key < current.key) {
                        current = current.leftChild;

                        if(current == null) {
                            parent.leftChild = newNode;
                            return;
                        }
                    } else {
                            current = current.rightChild;
                            if(current == null) {
                                parent.rightChild = newNode;
                                return;}
                        }
                }
            } 
    }
        public Node findMin(){
            Node current = root; //assigned root as current
            Node last = null;

            while(current != null) {
                last = current;
                current = current.leftChild;
            }

            return last;
        }

        public Node findMax() {
            Node current = root;
            Node last = null;

            while(current != null) {
                last = current;
                current = current.rightChild;
            }

            return last;
        }
}

public class Node {
    int key;
    Node leftChild, rightChild;

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

public class BSTApp {
    public static void main (String args[]){
        BST tree = new BST();
        tree.insert(10);
        tree.insert(15);
        tree.insert(100);
        tree.insert(88);
        tree.insert(2);

        System.out.println(tree.findMin().key); //Search for Min in BST
        System.out.println(tree.findMax().key);  //Search for Min in BST
    }
}

我正在努力推进我的研究,这样我就能在数据结构和算法方面取得进展。我希望你们都能帮助我。

hof1towb

hof1towb1#

static void delete(Node root, int key) 
{ 
    if (root == null) 
        return; 

    if (root.left == null && 
    root.right == null) 
    { 
        if (root.key == key) 
            return; 
        else
            return; 
    } 

    Queue<Node> q = new LinkedList<Node>(); 
    q.add(root); 
    Node temp = null, keyNode = null; 

    // Do level order traversal until 
    // we find key and last node. 
    while (!q.isEmpty()) 
    { 
        temp = q.peek(); 
        q.remove(); 

        if (temp.key == key) 
            keyNode = temp; 

        if (temp.left != null) 
            q.add(temp.left); 

        if (temp.right != null) 
            q.add(temp.right); 
    } 

    if (keyNode != null) 
    { 
        int x = temp.key; 
        deleteDeepest(root, temp); 
        keyNode.key = x; 
    } 
}
wljmcqd8

wljmcqd82#

public Node deleteNode(Node n, int key) {
     if (n == null) {
         return n;
     }
     if (key < n.key) {
         n.leftChild = deleteNode(n.leftChild, key);
     } else if (key > n.key) {
         n.rightChild = deleteNode(n.rightChild, key);
     } else {
         if (n.leftChild == null) {
             return n.rightChild;
         } else if (n.rightChild == null) {
             return n.leftChild;
         }
         n.key = minimum(n.rightChild);
         n.rightChild = deleteNode(n.rightChild, n.key);
     }
     return n;
 }

  public void deleteNode(int key) {
     deleteNode(root, key);
 }

 public int minimum(Node node) {
     if (node.leftChild == null) {
         return node.key;
     }
     return minimum(node.leftChild);
 }

相关问题