问题

我的删除方法包含了4个if语句，用于处理二叉搜索树中的4种不同类型的删除操作。我不确定哪里出错了，但在检查时它没有删除任何节点。如有帮助，谢谢提前。

我怀疑问题出在尝试将节点删除替换为null的地方。

public class BinaryTree<T extends Comparable<T>> {

    private class Node {
       
        private T data;
        private Node left;
        private Node right;
   
        // 左右子节点不一定存在
        public Node(T data) {
            this.data = data;
            this.left = null;
            this.right = null;
        }
    }
   
    private Node root;
    private int count = 0;
   
    // 在这里添加其他方法（省略）
   
    // 删除方法
    public void remove(T data) {
        remove1(root, data);
    }
   
    private Node remove1(Node node, T data) {
        Node parent = root;
        Node currentNode = root;
        Node temp;
        boolean isLeft = true;
       
        // 在这里实现删除逻辑（省略）
       
        return currentNode;
    }
   
    // 找到右子树中的最小节点
    private Node min(Node node) {
        while (node.left != null) {
            node = node.left;
        }
        return node;
    }
   
    // 其他方法（省略）
}

以上是你提供的代码的翻译部分。如果需要进一步帮助或解释，请随时告诉我。

英文翻译

My removal method consists of 4 if statements that tackle the 4 different kinds of removal in a binary search tree. Not sure where wrong but it didn't remove any node when I check it. Any help if appreciated. Thanks in advance'

I suspect the problems lies in are where I try to replace the node removal to be null

public class BinaryTree&lt;T extends Comparable&lt;T&gt;&gt; {

private class Node{
   
    private T data;
    private Node left;
    private Node right;

   
    // left and right child do not have to nessary exist
    public Node ( T data) {
        this.data = data;
        this.left = null;
        this.right = null;
    }}
   
    private Node root;
    private int count = 0;
   
    public void add( T data) {
        if ( isEmpty()) {
            root = new Node(data);
            count++;
        }
        else {
            insert(data, root);
            count++;
        }
    }
   
    public boolean isEmpty() { 
        return root == null;
    }
   
    public T getRoot()  {
        if ( root.data == null) {
            System.out.println(&quot;Root is empty&quot;);
            return null;
        }
        else {
        return  root.data;
    }}
   
    public Node getRootNode() {
        return root;
    }
   
    /*
     * Checking if the data is larger or lesser than the parent&#39;s data
     * If the data is smaller than the parent&#39;s data, node.left is created
     * If the data is bigger than the parent&#39;s data, node.right is created
     */
    private void insert( T data, Node node) {
       
        /*
         * If 1st obj is less than the 2nd obj return a neg
         * if 1st obj is more than the 2nd obj return a pos
         * if equal return 0
         */
        int compare = data.compareTo(node.data);
        if ( compare &lt; 1 ){
            if (node.left == null ) {
                node.left = new Node(data);

            }
           
        // make node.left if it is filled  
            else {
                insert(data, node.left);
            }
        }
       
        else {
            if ( node.right == null) {
                node.right = new Node(data);
            }
            else {
                insert( data, node.right);
            }
        }
    }
   
    public int getSize() {
        return count;
    }
   
    public boolean search ( T data) {
       
        Node temp = searchInner(data, root);
        if ( temp.data == data) {
            System.out.println(temp.data);
            return true;
        }
        else {
            return false;
        }
       
    }
   

    public Node searchInner( T data, Node node) {
       
        int compare = data.compareTo(node.data);
       
        if ( getRoot() == data ) {
            return root;
        }
       
        if ( compare &gt; 0) {
            return searchInner( data, node.right);  
        }
       
        if ( compare &lt; 0 ) {
            return searchInner(data , node.left);
        }
       
        if ( compare == 0 ) {
            return node;
        }
       
        else {
            System.out.println(&quot;Not found&quot;);
            return node;
        }
   
    }

    public void remove( T data) {
        remove1( root, data);
    }
   
    private Node remove1( Node node1, T data) {
       
        Node parent = root;
        Node node = root;
        Node temp;
        boolean isLeft = true;
       
        while ( node.data != data) {
           
            parent = node;
           
            if ( isEmpty()) {
                System.out.println(&quot;Unable to remove, root is empty&quot;);
                break;
            }
           
            if ( compare(data, node.data) &lt; 0) {
                node = node.left;
                isLeft = true;
            }
           
            if ( compare(data, node.data) &gt; 0) {
                node = node.right;
                isLeft = false;
            }
           
            else {
                // remove node if left child available
                if ( node.left == null &amp;&amp; node.right != null) {

                    if ( isLeft) {
                        parent.left = node.right;
                    }
                   
                    else {
                        parent.right = node.right;
                    }
                    count --;
                    break;
                }
               
                //remove node if right child available
                if ( node.right == null &amp;&amp; node.left != null) {

                    if ( isLeft) {
                        parent.left = node.left;
                    }
                   
                    else {
                        parent.right = node.left;
                    }
                    count --;
                    break;
                }
               
                // Remove node if 2 child available
                if ( node.left != null &amp;&amp; node.right != null ) {
                   
                    node = min(node.right);
                    node.right = remove1(node.right, node.data);
                   
                }
               
                // remove node if no child available
                 if ( node.left == null &amp;&amp; node.right == null) {
                    if (  isLeft ) {
                        parent.left = null;
                    }
                    else {
                        parent.right = null;
                    }
                    count --;
                    break;
                }
                                   
            }
       
           
        }
            return node;   
        }
   
    // fine the smallest node in the right subtree
    private Node min ( Node node1 ) {
        while ( node1.left != null) {
            node1 = node1.left;
        }
        return node1;
    }
   
    private int compare( T data, T data1) {
        return data.compareTo(data1);
    }
   
    public void printBST(T data) {
        printTree( root, data);
    }
   
    private void printTree( Node node, T data)
     {
        if(node == null) return;

        System.out.println(data + &quot; + &quot; + node.data);
        printTree(node.left , data);
        printTree(node.right , data);
     }
   
    public int getHeight() {
        return height(root);
    }
   
    private int height( Node node) {

        if  (node == null) return 0;
        else
            return 1 + Math.max(height(node.left), height(node.right));
        }
       
    public void print() {
        println(root);
    }
   
    private void println ( Node node) {
       
        LinkedList&lt;T&gt; q = new LinkedList&lt;T&gt;();
        q.add(node.data);
       
        if ( node == null) {
            return;
        }
       
        int size = getSize();
        while ( size &gt; 0) {

                System.out.print(q);
           
            q.clear();
            if ( node.left != null) {
                q.add(node.left.data);
                size --;
            }
            if ( node.right != null) {
                q.add(node.right.data);
                size --;
            }
            if ( node.right != null&amp;&amp; node.left != null) {
                System.out.println();
            }
            if ( size &gt; 1) {
                System.out.println(&quot;,&quot;);
            }
        }
       
    }
   
    public boolean sameTree( Node root1, Node root2) {
       
        if ( root1 == null &amp;&amp; root2 == null) {
            return true;
        }
       
        if ( root1 != null &amp;&amp; root2 != null) {
            return  root1.data == root2.data &amp;&amp; sameTree(root1.left,root2.left) &amp;&amp; sameTree(root1.right, root2.right);
        }
        else {
            return false;
        }
    }

}

答案1

得分: 0

我已经重新编写了你的BinaryTree类。我已经添加了一个新的remove方法，该方法使用了你的min(Node node)方法和我创建的另一个方法，该方法仅删除树的最小元素。此外，我还修改了你的Node类，通过添加一个新的构造函数，并添加了在BinaryTree类中的size变量。

import java.util.LinkedList;

public class BinaryTree<T extends Comparable<T>> {

    private class Node<T> {

        private T data;
        private Node<T> left;
        private Node<T> right;
        private int size;

        public Node(T value) {
            this(value, null, null);
        }

        public Node(T data, Node<T> left, Node<T> right) {
            this.data = data;
            this.left = left;
            this.right = right;
            size = 1;
            if (left != null) {
                size += left.size;
            }
            if (right != null) {
                size += right.size;
            }
        }
    }
    private Node<T> root;

    public BinaryTree() {
        root = null;
    }

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

    public T getRootData() {
        if (root.data == null) {
            System.out.println("Root is empty");
            return null;
        } else {
            return root.data;
        }
    }

    public Node<T> getRootNode() {
        return root;
    }

    public void insert(T x) {
        root = insert(x, root);
    }

    protected Node<T> insert(T x, Node<T> actual) {
        if (actual == null) {
            return new Node<T>(x);
        }
        int cmp = compare(x, actual.data);
        if (cmp < 0) {
            actual.left = insert(x, actual.left);
        } else if (cmp > 0) {
            actual.right = insert(x, actual.right);
        } else {
            actual.data = x;
        }
        actual.size = 1 + getSize(actual.left) + getSize(actual.right);
        return actual;
    }

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

    private int getSize(Node<T> actual) {
        if (actual == null) {
            return 0;
        } else {
            return actual.size;
        }
    }

    public boolean search(T data) {
        Node<T> temp = searchInner(data, root);
        if (temp.data == data) {
            System.out.println(temp.data);
            return true;
        } else {
            return false;
        }
    }

    public Node<T> searchInner(T data, Node<T> node) {
        int compare = data.compareTo(node.data);

        if (getRootData() == data) {
            return root;
        }

        if (compare > 0) {
            return searchInner(data, node.right);
        }

        if (compare < 0) {
            return searchInner(data, node.left);
        }

        if (compare == 0) {
            return node;
        } else {
            System.out.println("Not found");
            return node;
        }
    }

    public void remove(T data) {
        remove1(root, data);
    }

    private Node<T> remove1(Node<T> actual, T data) {
        if (actual == null) {
            return actual;
        }
        int cmp = compare(data, actual.data);
        if (cmp < 0) {
            actual.left = remove1(actual.left, data);
        } else if (cmp > 0) {
            actual.right = remove1(actual.right, data);
        } else {
            if (actual.right == null) {
                return actual.left;
            }
            if (actual.left == null) {
                return actual.right;
            }
            actual.data = min(actual.right).data;
            actual.right = removeMin(actual.right);
        }
        return actual;
    }

    public Node<T> removeMin() {
        Node<T> min = min(root);
        root = removeMin(root);
        return min;
    }

    private Node<T> removeMin(Node<T> actual) {
        if (actual.left == null) {
            return actual.right;
        }
        actual.left = removeMin(actual.left);
        actual.size--;
        return actual;
    }

    private Node<T> min(Node<T> node1) {
        while (node1.left != null) {
            node1 = node1.left;
        }
        return node1;
    }

    private int compare(T data, T data1) {
        return data.compareTo(data1);
    }

    public void printBST(T data) {
        printTree(root, data);
    }

    private void printTree(Node<T> node, T data) {
        if (node == null) {
            return;
        }

        System.out.println(data + " + " + node.data);
        printTree(node.left, data);
        printTree(node.right, data);
    }

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

    private int height(Node<T> node) {
        if (node == null) {
            return 0;
        } else {
            return 1 + Math.max(height(node.left), height(node.right));
        }
    }

    public void print() {
        println(root);
    }

    private void println(Node<T> node) {
        LinkedList<T> q = new LinkedList<T>();
        q.add(node.data);

        if (node == null) {
            return;
        }

        int size = getSize();
        while (size > 0) {
            System.out.print(q);

            q.clear();
            if (node.left != null) {
                q.add(node.left.data);
                size--;
            }
            if (node.right != null) {
                q.add(node.right.data);
                size--;
            }
            if (node.right != null && node.left != null) {
                System.out.println();
            }
            if (size > 1) {
                System.out.println(",");
            }
        }
    }

    public boolean sameTree(Node<T> root1, Node<T> root2) {
        if (root1 == null && root2 == null) {
            return true;
        }

        if (root1 != null && root2 != null) {
            return root1.data == root2.data && sameTree(root1.left, root2.left) && sameTree(root1.right, root2.right);
        } else {
            return false;
        }
    }
}

希望这对你有帮助。

英文翻译

I have rewritten your BinaryTree class. I have added a new remove method, which uses your min(Node node) method and other one I have created, that only removes the minimum element of the tree. In addition, I have modified your Node class too by adding a new constructor and added your size variable that was in BinaryTree class
I have modified all of this in order to make the method remove() working properly


import java.util.LinkedList;

public class BinaryTree&lt;T extends Comparable&lt;T&gt;&gt; {

    private class Node&lt;T&gt; { //Here we specify what the node contains

        private T data;
        private Node&lt;T&gt; left;
        private Node&lt;T&gt; right;
        private int size;

        public Node(T value) {
            this(value, null, null);
        }

        // left and right child do not have to nessary exist
        public Node(T data, Node&lt;T&gt; left, Node&lt;T&gt; right) {
            this.data = data;
            this.left = null;
            this.right = null;
            size = 1;
            if (left != null) {
                size += left.size;
            }
            if (right != null) {
                size += right.size;
            }
        }
    }
    private Node root;

    public BinaryTree() { //Added a constructor to set the root node to null
        root = null;
    }

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

    public T getRootData() { //Changed the name to other more clear
        if (root.data == null) {
            System.out.println(&quot;Root is empty&quot;);
            return null;
        } else {
            return (T) root.data;
        }
    }

    public Node getRootNode() {
        return root;
    }

    public void insert(T x) { //The new insert method
        root = insert(x, root);
    }

    protected Node&lt;T&gt; insert(T x, Node&lt;T&gt; actual) {
        //We check if the node exists, in case not we just create a new node
        if (actual == null) {
            return new Node&lt;T&gt;(x);
        }
        int cmp = compare(x, actual.data);
        if (cmp &lt; 0) {
            actual.left = insert(x, actual.left);
        } else if (cmp &gt; 0) {
            actual.right = insert(x, actual.right);
        } else {
            // If the node exists we just update his content
            actual.data = x;
        }
        actual.size = 1 + getSize(actual.left) + getSize(actual.right);
        return actual;
    }

     public int getSize() { //New method
        return getSize(root);
    }

    private int getSize(Node&lt;T&gt; actual) {
        if (actual == null) {
            return 0;
        } else {
            return actual.size;
        }
    }

    public boolean search(T data) {

        Node temp = searchInner(data, root);
        if (temp.data == data) {
            System.out.println(temp.data);
            return true;
        } else {
            return false;
        }

    }

    public Node searchInner(T data, Node node) {

        int compare = data.compareTo((T) node.data);

        if (getRootData() == data) {
            return root;
        }

        if (compare &gt; 0) {
            return searchInner(data, node.right);
        }

        if (compare &lt; 0) {
            return searchInner(data, node.left);
        }

        if (compare == 0) {
            return node;
        } else {
            System.out.println(&quot;Not found&quot;);
            return node;
        }

    }

    public void remove(T data) {

        remove1(root, data);
    }

    private Node remove1(Node actual, T data) {
        if (actual == null) {
            return actual;
        }
        int cmp = compare(data, (T) actual.data);
        //Check whether the value is lesser greater or equal than the one we are just visiting
        if (cmp &lt; 0) {
            actual.left = remove1(actual.left, data);
        } else if (cmp &gt; 0) {
            actual.right = remove1(actual.right, data);
        } else {
            if (actual.right == null) {
                return actual.left;
            }
            if (actual.left == null) {
                return actual.right;
            }
            actual.data = min(actual.right).data;
            actual.right = removeMin(actual.right);
        }
        return actual;
    }

    public Node removeMin() {
        //A new method to remove the minimum element
        Node min = min(root);
        root = removeMin(root);
        return min;
    }

    private Node removeMin(Node actual) {
        if (actual.left == null) {
            return actual.right;
        }
        actual.left = removeMin(actual.left);
        actual.size--;
        return actual;
    }

    // fine the smallest node in the right subtree
    private Node min(Node node1) {
        while (node1.left != null) {
            node1 = node1.left;
        }
        return node1;
    }

    private int compare(T data, T data1) {
        return data.compareTo(data1);
    }

    public void printBST(T data) {
        printTree(root, data);
    }

    private void printTree(Node node, T data) {
        if (node == null) {
            return;
        }

        System.out.println(data + &quot; + &quot; + node.data);
        printTree(node.left, data);
        printTree(node.right, data);
    }

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

    private int height(Node node) {

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

    public void print() {
        println(root);
    }

    private void println(Node node) {

        LinkedList&lt;T&gt; q = new LinkedList&lt;T&gt;();
        q.add((T) node.data);

        if (node == null) {
            return;
        }

        int size = getSize();
        while (size &gt; 0) {

            System.out.print(q);

            q.clear();
            if (node.left != null) {
                q.add((T) node.left.data);
                size--;
            }
            if (node.right != null) {
                q.add((T) node.right.data);
                size--;
            }
            if (node.right != null &amp;&amp; node.left != null) {
                System.out.println();
            }
            if (size &gt; 1) {
                System.out.println(&quot;,&quot;);
            }
        }

    }

    public boolean sameTree(Node root1, Node root2) {

        if (root1 == null &amp;&amp; root2 == null) {
            return true;
        }

        if (root1 != null &amp;&amp; root2 != null) {
            return root1.data == root2.data &amp;&amp; sameTree(root1.left, root2.left) &amp;&amp; sameTree(root1.right, root2.right);
        } else {
            return false;
        }

    }
}

I hope this helps to you

专注分享java语言的经验与见解，让所有开发者获益！

二叉搜索树删除节点函数未能移除节点。

问题

答案1

Go like channels in Java

在低资源环境下使用Apache Cassandra和Go服务器

avatica-go客户端读取Phoenix查询服务器：[驱动程序：连接错误]

向Spring端点发送POST请求，返回状态码400。

Spring Boot控制器从Golang应用程序接收到的重定向请求会被重复执行两次。

可以在不将其读入内存的情况下多次重用HTTP请求体吗？

How to register my go lang microservice in Spring Eureka Service Discovery

在应用程序-go + BDD-java中模拟第三方服务

What is value, reference vs pointer and what these three example used to pass?

Do goroutines and light-weight Java threads mean we never need use thread pools and async code again?

发表评论