Двоичное дерево поиска не удаляет узел - PullRequest
Новая
       22

Двоичное дерево поиска не удаляет узел

0 голосов
/ 04 октября 2018

Я создал Binary Search Tree и пытаюсь удалить определенные узлы после их добавления.Я могу успешно delete около 5 Nodes, но когда я пытаюсь удалить Node with id 109, он просто игнорирует его и ничего не происходит.Я пробовал много способов удалить его, и он просто не работает. 

myBinaryTree.deleteNode(myBinaryTree.root, 109);

Вот метод delete в моем двоичном дереве. 

public Node deleteNode(Node root, int ID){

    if (root == null)  return root;
    if (ID < root.ID)
        root.leftChild = deleteNode(root.leftChild, ID);
    else if (ID > root.ID)
        root.rightChild = deleteNode(root.rightChild, ID);

    else
    {
        if (root.leftChild == null)
            return root.rightChild;
        else if (root.rightChild == null)
            return root.leftChild;

        root.ID = minValue(root.rightChild);
        root.rightChild = deleteNode(root.rightChild, root.ID);
    }

    return root;
}


int minValue(Node root)
{
    int minv = root.ID;
    while (root.leftChild != null)
    {
        minv = root.leftChild.ID;
        root = root.leftChild;
    }
    return minv;
}

И мой Node: 

public class Node {
    int ID;
    Dancer.Gender gender;
    int height;

    Node leftChild;
    Node rightChild;

    Node(int ID, Dancer.Gender gender, int height) {

        this.ID = ID;
        this.gender = gender;
        this.height = ID;

    }

    public int getID() {
        return ID;
    }

    public void setID(int ID) {
        this.ID = ID;
    }

}

ID работает как задумано, то есть метод deleteNode получает правильный идентификатор, он просто не удаляет его.

Вот изображение дерева, которым я являюсьпытаясь удалить из:

enter image description here

Если требуется дополнительная информация о том, как я добавляю узлы и т. д., я могу предоставить это также.Это настолько странно, что все работает отлично, пока я не попытаюсь удалить узел с ID = 109.

1 Ответ

0 голосов
/ 04 октября 2018

Ваш код выглядит нормально.

Кстати, как вы убедились, что узел не был удален?Я только что проверил ваш код и напечатал обход заказа.И это прекрасно работает. 

// This is java code.
void inorder(Node root){
    if (root ==null)return;
    inorder(root.leftChild);
    System.out.print(root.ID + "  ");
    inorder(root.rightChild);
}

// verify deletion by printing inorder traversal before and after
public static void main(String[] args) {
    // creating the tree
    Node root = new Node(60);
    root.leftChild = new Node(40);
    root.rightChild = new Node(109);
    root.leftChild.leftChild = new Node(20);
    root.leftChild.rightChild = new Node(49);

    inorder(root); // Printing before deleting
    System.out.println();
    myBinaryTree.root = deleteNode(myBinaryTree.root, 109); // delete the node and collect the new reference of the root.
    inorder(root); // Printing after tree
    System.out.println();
}
...