无法删除 CPP 中有两个 children 的二叉树中的节点。我粘贴了下面的代码并突出显示了错误部分

Question

我已经在下面粘贴了我的全部代码。

我可以成功删除没有 child 或一个 child 的节点，但无法删除有两个 children.

的节点

在有两个 children 的节点中，我使用的方法是将目标节点的值与其叶 child 交换，然后尝试删除叶节点。但是在删除它时出现错误 exited with code=3221225725 in 0.474 seconds 我也尝试创建其他函数来删除它但最终还是一样。

我试过删除 delete，代码运行很好，值也成功交换了！我也对二叉搜索树使用了相同的方法，它工作得很好！

#include <iostream>

class BinaryTree
{
  struct Node
{
    int data;
    Node *left_child;
    Node *right_child;
};

Node *root;

Node *appendage(Node *root, int data)
{
    if (root == NULL)
    {
        root = new Node();
        root->data = data;
        root->left_child = NULL;
        root->right_child = NULL;
        return root;
    }

    else if (root->left_child == NULL and root->right_child == NULL)
    {
        root->left_child = appendage(root->left_child, data);
    }

    else if (root->left_child != NULL and root->right_child == NULL)
    {
        root->right_child = appendage(root->right_child, data);
    }

    else
    {
        root->left_child = appendage(root->left_child, data);
    }

    return root;
}

Node *deletion(Node *root, int data)
{
    if (root == NULL)
    {
        return root;
    }

    else if (data != root->data)
    {
        root->left_child = deletion(root->left_child, data);
        root->right_child = deletion(root->right_child, data);
    }

    else
    {
        if (root->left_child == NULL && root->right_child == NULL)
        {
            delete root;
            return NULL;
        }

        else if (root->left_child == NULL)
        {
            Node *temp_node = root;
            root = root->right_child;
            delete temp_node;
        }

        else if (root->right_child == NULL)
        {
            Node *temp_node = root;
            root = root->left_child;
            delete temp_node;
         }
        //////// ***ERROR BELOW (DUE TO DELETE)***

        else //DELETE WITH TWO NODES
        {
            Node *temp_node = last_right_node(root);
            root->data = temp_node->data;
            delete temp_node;
        }

        //////// ***ERROR ABOVE  (DUE TO DELETE)***


    }        
    return root;
}

void inorder_display(Node *root)
{
    if (root == NULL)
    {
        return;
    }
    inorder_display(root->left_child);
    std::cout<<root->data<<" ";
    inorder_display(root->right_child);
}

void preorder_display(Node *root)
{
    if (root == NULL)
    {
        return;
    }
    std::cout<<root->data<<" ";
    preorder_display(root->left_child);
    preorder_display(root->right_child);
}

void postorder_display(Node *root)
{
    if (root == NULL)
    {
        return;
    }
    postorder_display(root->left_child);
    postorder_display(root->right_child);
    std::cout<<root->data<<" ";
}

Node *destroy_tree(Node *root)
{
    if (root != NULL)
    {
        destroy_tree(root->left_child);
        destroy_tree(root->right_child);
        delete root;
    }
    return root;
}

Node *last_right_node(Node *root)
{
    if (root == NULL)
    {
        return root;
    }

    else if (root->right_child == NULL)
    {
        return root;
    }

    else
    {
        return last_right_node(root->right_child);
    }
};

public:

BinaryTree()
{
    root = NULL;
}

void append(int data)
{
    root = appendage(root, data);
}

void remove(int data)
{
    deletion(root,data);
}

void inorder()
{
    inorder_display(root);
    std::cout<<"\n";
}

void preorder()
{
    preorder_display(root);
    std::cout<<"\n";
}

void postorder()
{
    postorder_display(root);
    std::cout<<"\n";
}

int last()
{
    return last_right_node(root)->data;
}

~BinaryTree()
{
    destroy_tree(root);
}
};

 int main()
 {

BinaryTree b;
b.append(1);
b.append(2);
b.append(3);

b.append(4);
b.append(5);

b.inorder();
b.preorder();
b.postorder();

//std::cout<<b.last();

b.remove(2);

b.inorder();

return 0;
}

Answer 1

我要去 post Java 中的一个部分，但我假设如果你正在做 BinaryTrees，你可以阅读哈哈。无论如何，看起来你已经定义了 Node ，这与我的 BinaryTreeNode<T> 是等价的，然后你想要一个接受左右树节点的构造函数来递归定义树。

protected BinaryTreeNode<T> _root = null ;

public LinkedBinaryTree() {}

public LinkedBinaryTree( T element )
{
    _root = new BinaryTreeNode<T>( element ) ; 
}

public LinkedBinaryTree( T element, 
        LinkedBinaryTree<T> left, LinkedBinaryTree<T> right )
{
    _root = new BinaryTreeNode<T>( element ) ;
    _root.setLeft( left.getRootNode() ) ;
    _root.setRight( right.getRootNode() );
}

public BinaryTreeNode<T> getRootNode() { return _root ; }

这可能有助于重新定义您的结构。

我将展示我的整个删除部分和一些评论。我认为您可能想关注“//has 2 children”else 子句，看看发生了什么；我太累了无法比较我们的（这是我的 binarySEARCHtree 版本）

public T removeElement(T target)
        throws ElementNotFoundException
{
    if( isEmpty() )
        throw new ElementNotFoundException() ;
    
    T result = null ;
    
    if( target.equals( _root.getElement() ) )
    {
        result = _root.getElement() ;
        BinaryTreeNode<T> temp = replacement( _root ) ; 
        
        if( temp == null )
            _root = null ;
        else
        {
            _root.setElement( temp.getElement() );
            _root.setLeft( temp.getLeft() ) ;
            _root.setRight( temp.getRight() ) ;
        }
    }
    else
    {
        BinaryTreeNode<T> parent = _root ;
        if( target.compareTo( _root.getElement() ) < 0 )
            result = removeElement( target, _root.getLeft(), parent ) ;
        else
            result = removeElement( target, _root.getRight(), parent ) ;
    }
    
    return result ;
}

/** @child of @removeElement( T target ) */
private T removeElement( T target, BinaryTreeNode<T> node, BinaryTreeNode<T> parent )
{
    if( node == null )
        throw new ElementNotFoundException() ;
    
    T result = null ; 
    
    if( target.equals( node.getElement() ) )
    {
        result = node.getElement() ;
        BinaryTreeNode<T> temp = replacement( node ) ; 
        
        if( parent.getRight() == node )
            parent.setRight(temp) ;
        else
            parent.setLeft( temp ) ;
    }
    else
    {
        parent = node ;
        if( target.compareTo(node.getElement()) < 0 )
            result = removeElement( target, node.getLeft(), parent ) ;
        else
            result = removeElement( target, node.getRight(), parent ) ;
    }
    
    return result ;
}

/** @child of @removeElement */
private BinaryTreeNode<T> replacement( BinaryTreeNode<T> node )
{
    BinaryTreeNode<T> result = null ;
    
    if( ( node.getLeft() == null ) && ( node.getRight() == null ) )
    {
        result = null ;
    }
    else if( ( node.getLeft() != null ) && ( node.getRight() == null )  )
    {
        result = node.getLeft() ;
    }
    else if( ( node.getLeft() == null ) && ( node.getRight() != null )  )
    {
        result = node.getRight() ;
    }
    else
    { //has 2 children
        BinaryTreeNode<T> parent = node ;
        BinaryTreeNode<T> current = node.getRight() ;
        
        while( current.getLeft() != null )
        {
            parent  = current ;
            current = parent.getLeft() ;
        }
        
        current.setLeft( node.getLeft() ) ;
        if( node.getRight() != current )
        {
            parent.setLeft(current.getRight() ) ;
            current.setRight( node.getRight() ) ;
        }
        
        result = current ;
    }

    return result ;
}

Answer 2

我更改了最后一个右节点函数，它 returns 叶节点的父节点。我已将目标节点的子节点与最后一个右节点（叶节点）链接起来，然后在将其从父节点中删除后，我将其与目标节点交换！它适用于所有情况！

        /*
        Depth First Traversals: 
        (a) Inorder (Left, Root, Right) : 4 2 5 1 3 
        (b) Preorder (Root, Left, Right) : 1 2 4 5 3 
        (c) Postorder (Left, Right, Root) : 4 5 2 3 1
        */

        #include <iostream>

        class BinaryTree
        {
            struct Node
            {
                int data;
                Node *left_child;
                Node *right_child;
            };

            Node *root;
            //////// *** CHANGES BELOW HERE *** 
            Node *last_right_node(Node *root)
            {
                Node *parent_node = root;

                if ((root->right_child)->right_child == NULL)
                {
                    return parent_node;
                }        

                return last_right_node(root->right_child);
            }
            //////// *** CHANGES ABOVE HERE *** 

            Node *appendage(Node *root, int data)
            {
                if (root == NULL)
                {
                    root = new Node();
                    root->data = data;
                    root->left_child = NULL;
                    root->right_child = NULL;
                    return root;
                }

                else if (root->left_child == NULL and root->right_child == NULL)
                {
                    root->left_child = appendage(root->left_child, data);
                }

                else if (root->left_child != NULL and root->right_child == NULL)
                {
                    root->right_child = appendage(root->right_child, data);
                }

                else
                {
                    root->left_child = appendage(root->left_child, data);
                }

                return root;
            }

            Node *deletion(Node *root, int data)
            {
                if (root == NULL)
                {
                    return root;
                }

                else if (data != root->data)
                {
                    root->left_child = deletion(root->left_child, data);
                    root->right_child = deletion(root->right_child, data);
                }

                else
                {
                    if (root->left_child == NULL && root->right_child == NULL)
                    {
                        delete root;
                        return NULL;
                    }

                    else if (root->left_child == NULL)
                    {
                        Node *temp_node = root;
                        root = root->right_child;
                        delete temp_node;
                    }

                    else if (root->right_child == NULL)
                    {
                        Node *temp_node = root;
                        root = root->left_child;
                        delete temp_node;
                    }
                    //////// *** SOLVED BELOW *** 
                    else
                    {
                        // PARENT NODE OF LEAF NODE
                        Node *temp_node = last_right_node(root);
                        // LEAF NODE
                        Node *leaf_node = temp_node->right_child;
                        // REMOVING LEAF NODE FROM TREE
                        temp_node->right_child = NULL;
                        // LINKING LEAF NODE WITH TARGET NODE CHILDREN
                        leaf_node->left_child = root->left_child;
                        leaf_node->right_child = root->right_child;
                        // SWAPPING THE NODE
                        root = leaf_node;
                    }
                    //////// *** SOLVED ABOVE *** 
                }        
            
                return root;
            }
            
            void inorder_display(Node *root)
            {
                if (root == NULL)
                {
                    return;
                }
                inorder_display(root->left_child);
                std::cout<<root->data<<" ";
                inorder_display(root->right_child);
            }

            void preorder_display(Node *root)
            {
                if (root == NULL)
                {
                    return;
                }
                std::cout<<root->data<<" ";
                preorder_display(root->left_child);
                preorder_display(root->right_child);
            }

            void postorder_display(Node *root)
            {
                if (root == NULL)
                {
                    return;
                }
                postorder_display(root->left_child);
                postorder_display(root->right_child);
                std::cout<<root->data<<" ";
            }

            Node *destroy_tree(Node *root)
            {
                if (root != NULL)
                {
                    destroy_tree(root->left_child);
                    destroy_tree(root->right_child);
                    delete root;
                }
                return root;
            }


            public:

            BinaryTree()
            {
                root = NULL;
            }

            void append(int data)
            {
                root = appendage(root, data);
            }

            void remove(int data)
            {
                root = deletion(root,data);
            }

            void inorder()
            {
                inorder_display(root);
                std::cout<<"\n";
            }

            void preorder()
            {
                preorder_display(root);
                std::cout<<"\n";
            }

            void postorder()
            {
                postorder_display(root);
                std::cout<<"\n";
            }

            ~BinaryTree()
            {
                destroy_tree(root);
            }
        };

        int main()
        {
            BinaryTree b;
            b.append(1);
            b.append(2);
            b.append(3);
            
            b.append(4);
            b.append(5);
            
            b.inorder();
            b.preorder();
            b.postorder();

            b.remove(1);

            b.inorder();

            return 0;
        }

无法删除 CPP 中有两个 children 的二叉树中的节点。我粘贴了下面的代码并突出显示了错误部分

Unable to delete Node in Binary Tree which have two children in CPP. I've pasted the code below and highlighted out the error part

c++

binary-tree