很难从我的二叉搜索树中删除一个节点

Question

我正在创建一个二叉搜索树，它需要能够删除一个节点，return 如果节点被正确删除则为 true，如果树中不存在该值则为 false。我这样做是因为我需要删除多个数字，并且我想创建一个 while 循环以在它为真时将其全部删除。例如，一棵树具有以下整数：{79、83、147、71、95、49、15、191}。另一棵树有以下整数 {26, 79, 144, 88, 147, 200, 90 }。我的任务是找到树 1 中存在于树 2 中的任何元素，并将它们从树 1 中删除（在本例中为 79 和 147）。我想创建一个循环遍历树 2 中的所有数字并从树 1 中搜索和删除。这是我到目前为止的删除节点功能（假设树已经构建并填充）：

Node.h:

template<class ItemType>
class Node {
public:
    ItemType data;
    Node * left;
    Node * right;

    //Constructors / Destructors
    Node ();
    Node ( ItemType inData );
    ~Node ();
};

//--------------------------------------------------------------//
//--                Constructor / Destructor                  --//
//--------------------------------------------------------------//
/** Standard Constructor */
template<class ItemType>
Node<ItemType>::Node () {
    left = right = NULL;
}

/** Overload Constructor */
template<class ItemType>
Node<ItemType>::Node ( ItemType inData ) {
    data = inData;
    left = right = NULL;
}

/** Standard Destructor */
template<class ItemType>
Node<ItemType>::~Node () {
    right = left = NULL;
}

来自Source.cpp：

Tree2.postorder_print ();

int ridOf = 79;

if (Tree2.remove ( ridOf )) {
        Tree2.postorder_print ();
        cout << endl << "Number of Nodes: " << Tree2.get_num_of_nodes () << endl;
        cout << "Height:          " << Tree2.get_tree_height () << endl << endl;
    }

来自Tree.h：

template<class ItemType>
void BTree<ItemType>::postorder_print_helper ( Node<ItemType> * inRoot, int & count ) {
    if (inRoot != NULL) {
        postorder_print_helper ( inRoot->left, count );
        postorder_print_helper ( inRoot->right, count );
        count++;
        std::cout << setw ( 4 ) << inRoot->data << " ";
        if (count % 5 == 0) { std::cout << endl; }
    }
} // end of void BTree<ItemType>::postorder_print_helper ( Node<ItemType> * inRoot )  




template<class ItemType>
void BTree<ItemType>::postorder_print_helper ( Node<ItemType> * inRoot, int & count ) {
    if (inRoot != NULL) {
        postorder_print_helper ( inRoot->left, count );
        postorder_print_helper ( inRoot->right, count );
        count++;
        std::cout << setw ( 4 ) << inRoot->data << " ";
        if (count % 5 == 0) { std::cout << endl; }
    }
} // end of void BTree<ItemType>::postorder_print_helper ( Node<ItemType> * inRoot ) 




template<class ItemType>
bool BTree<ItemType>::remove_helper (Node<ItemType> * inRoot, ItemType toRemove) {
    //if this is the node with the data
    if (inRoot->data == toRemove) {
        //Create Null Node that points to NUll
        Node<ItemType> * nullNode = new Node < ItemType > ;
        //if inRoot has No Children
        if (inRoot->left == NULL && inRoot->right == NULL ) {
            inRoot = nullNode;
            return true;
        }
        //if inRoot has 2 Children
        else if (inRoot->left != NULL && inRoot->right != NULL) {
            Node<ItemType> * temp = new Node < ItemType >;
            temp = return_max_value ( inRoot->left );
            Node<ItemType> * tempRight = new Node < ItemType >;
            tempRight = inRoot->right;
            Node<ItemType> * tempLeft = new Node < ItemType >;
            tempLeft = inRoot->left;
            inRoot = nullNode;
            inRoot = temp;
            temp->left = tempLeft;
            temp->right = tempRight;

            return true;
        }
        //if inRoot has 1 child
        else {
            //if inRoot has left child
            if (inRoot->right == NULL) {
                Node<ItemType> * temp = new Node < ItemType >;
                temp = inRoot->left;
                inRoot = nullNode;
                inRoot = temp;
                return true;
            }
            //if inRoot has right child
            else {
                Node<ItemType> * temp = new Node < ItemType >;
                temp = inRoot->right;
                inRoot = nullNode;
                inRoot = temp;
                return true;
            }
        }
    }
    //If not the node with the data See if toRemove is less than inRoot and perform recursive action
    else if ( toRemove < inRoot->data ) {
        remove_helper ( inRoot->left, toRemove );
    } //end if (toRemove < inRoot->data) 
    //See if toRemove is greater than inRoot and perform recursive action
    else if ( toRemove > inRoot->data)  {
        remove_helper ( inRoot->right, toRemove );
    }// end of else 

    //return false if data cannot be found
    else return false;
}

我的一些结果是不同的，而且都是错误的。一个结果是不断打印树的无限循环。另一个结果是它执行了删除并且看起来是成功的但是如果你看两个打印输出，它们是相同的并且节点没有被删除（如果 false 是 returned 它不应该再次打印出来但是它确实）。然后第三个结果发生在第二个 print_preorder 期间。它中断并停在一个空节点上，但左右数据都显示 "Unable to read memory." 我做错了什么？我想不通。在我尝试删除一个节点之前，我的所有其他树功能（包括预订打印）。

为了进一步说明，我的 remove_helper 函数有问题。所以我可以继续从 Tree1 中删除 Tree2 中存在的节点。

Answer 1

你想要做的是两棵树之间的倒相交。您可以通过创建一个带有两个参数的函数来做到这一点。一个参数是您要从 (tree1) 中删除内容的树，另一个是您要检查的树 (tree2)。

然后在函数中使用递归检查 tree2。对于您取出的每个元素，您使用该元素来搜索它是否存在于 tree1 中（在这种情况下也将其删除）。然后继续在 tree1 中搜索 tree2 中的每个节点，直到遍历 tree2 中的每个元素。

Answer 2

remove_helper 正在尝试更改 inRoot 参数的值。但是 inRoot 是按值传递的，因此在您的函数中所做的任何更改都不会反映在调用函数中。

把remove_helper函数改成inRoot引用，就可以修改调用函数中使用的参数值了：

template<class ItemType>
bool BTree<ItemType>::remove_helper (Node<ItemType> * &inRoot, ItemType toRemove) {

此外，这段代码似乎不正确：

    //Create Null Node that points to NUll
    Node<ItemType> * nullNode = new Node < ItemType > ;

该节点未指向 NULL，它指向一个空节点。在代码的更下方，您正在检查 inRoot->left == NULL，因此您应该将指针设置为 NULL，而不是指向空节点。

你也有很多内存泄漏，记住 - 如果你用 new 创建一些东西，那么某处也应该有一个相应的 delete。

编辑：还有一件事 - 你永远不想这样做：

 Node<ItemType> * tempRight = new Node < ItemType >;
 tempRight = inRoot->right;

您正在分配一些内存并在 tempRight 中指向它，然后立即将 tempRight 设置为其他内容。这是内存泄漏而且是不必要的——您不需要为每个指针分配内存。将其更改为：

 Node<ItemType> * tempRight = inRoot->right;

Answer 3

好的，在@TheDark 的帮助下，这是我的 remove_helper 函数：

template<class ItemType>
bool BTree<ItemType>::remove_helper (Node<ItemType> * &inRoot, ItemType toRemove) {
    //if this is the node with the data
    if (inRoot->data == toRemove) {
        //if inRoot has No Children
        if (inRoot->left == NULL && inRoot->right == NULL ) {
            inRoot = NULL;
            std::cout << "one" << std::endl;
            return true;
        }
        //if inRoot has 2 Children
        else if (inRoot->left != NULL && inRoot->right != NULL) {
            inRoot->data = return_max_value ( inRoot->left )->data;
            remove_helper (inRoot->left,inRoot->data);
            std::cout << "two" << std::endl;
            return true;
        }
        //if inRoot has 1 child
        else {
            std::cout << "zero" << std::endl;
            //if inRoot has left child
            if (inRoot->right == NULL) {
                Node<ItemType> * temp = new Node < ItemType >;
                temp = inRoot->left;
                inRoot = NULL;
                inRoot = temp;
                return true;
            }
            //if inRoot has right child
            else {
                Node<ItemType> * temp = new Node < ItemType >;
                temp = inRoot->right;
                inRoot = NULL;
                inRoot = temp;
                return true;
            }
        }
    }
    //If not the node with the data See if toRemove is less than inRoot and perform recursive action
    else if ( toRemove < inRoot->data ) {
        remove_helper ( inRoot->left, toRemove );
    } //end if (toRemove < inRoot->data) 
    //See if toRemove is greater than inRoot and perform recursive action
    else if ( toRemove > inRoot->data)  {
        remove_helper ( inRoot->right, toRemove );
    }// end of else 

    //return false if data cannot be found
    else return false;
}

将参数设置为按引用传递后，我修复了删除具有 2 个子节点的节点。我只是从左边的最大值复制数据，然后递归删除它来自的节点。现在已经完成了，我可以继续下一步了！谢谢大家。

很难从我的二叉搜索树中删除一个节点

Having difficulty with removing a node from my binary search tree

c++

recursion

binary-search-tree