时间戳

首页 > 解决方案 > 无法删除二叉树中在 CPP 中有两个子节点的节点。我粘贴了下面的代码并突出显示了错误部分

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

问题描述

我在下面粘贴了我的整个代码。

我能够成功删除没有孩子或一个孩子的节点，但无法删除有两个孩子的节点。

在有两个孩子的节点中，我使用的方法是将目标节点的值与它的叶子节点交换，然后尝试删除叶子节点。但是，在删除它时，会在 0.474 秒内使用 code=3221225725 退出错误，我还尝试创建其他函数来删除它，但最终得到相同的结果。

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

#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;
}

标签： c++binary-tree

解决方案

我将在 Java 中发布一个部分，但我假设如果您正在使用 BinaryTrees，您可以阅读它哈哈。无论如何，看起来您已经Node定义了与 my 等效的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 ; }

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

我将展示我的整个删除部分并附上一些评论。我想你可能想关注“//有 2 个孩子”的 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 ;
}

推荐阅读