Удаление узла в двоичном дереве

Ниже приведен код, который я написал для случая, когда deleteItem находится в конечном узле. Даже если я приравниваю найденный листовой узел к «нулевому», то и тогда, когда я печатаю неупорядоченный порядок обхода дерева, этот элемент не удаляется и появляется на экране. Что мне не хватает?

public void deleteNode(T deleteItem)
    {
        TreeNode<T> node = root;
        if(root == null)
        {
            System.out.print("Binary Tree does not exist");
            System.exit(0);
        }
        while((node.data != deleteItem) && (node.leftNode != null || node.rightNode != null))
        {
            if(deleteItem.compareTo(node.data)<0)
                node = node.leftNode;
            else
                node = node.rightNode;
        }
        //System.out.printf("deleting item is: %s\n", node.data);
        if(node.data != deleteItem)
        {   
            System.out.println("\ndeleteItem not found in the tree");
            System.exit(0);
        }
        else
        {
            if(node.leftNode == null && node.rightNode == null)
            {
                node = null;
            }
        }
    }

java tree binary-tree binary-search-tree
person user3048786    schedule 27.06.2014    source источник

Ответы (1)


arrow_upward
1
arrow_downward

Java — это "Передача по значению", поэтому TreeNode<T> tmp = root здесь означает присвоение ссылок tmp root, что означает просто у вас есть две разные ссылки на один и тот же экземпляр. В соответствии с этим, когда вы говорите node = null, вы устанавливаете свои локальные ссылки на null, что означает, что родитель узла по-прежнему ссылается на него. Таким образом, чтобы удалить листовой узел из дерева, вам нужно отслеживать его родителя, а затем удалить ссылку на узел (удалить ссылку в дереве, а не вашу локальную копию), что будет примерно так:

public void deleteNode(T deleteItem) {
        TreeNode<T> node = root;
        TreeNode<T> parent = null; // parent of the deleted node.
        if(root == null) {
            System.out.print("Binary Tree does not exist");
            System.exit(0);
        }
        while((node.data != deleteItem) && 
              (node.leftNode != null || node.rightNode != null)) {
            parent = node; // keep track of the parent of the deleted node
            if(deleteItem.compareTo(node.data) < 0)
                node = node.leftNode;
            else
                node = node.rightNode;
        }
        if(node.data != deleteItem) {   
            System.out.println("\ndeleteItem not found in the tree");
            System.exit(0);
        }
        else {
            if(parent.leftNode == node)
                parent.leftNode = null;
            else
                parent.rightNode = null;
        }
    }
person Kerollos Asaad    schedule 18.10.2014