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

Question

我正在创建一个二叉搜索树，它需要能够删除一个节点并在节点被正确删除时返回 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 中搜索和删除。到目前为止，这是我对删除节点功能的了解(假设树已经构建并填充):

节点.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 它不应该再次打印出来但它确实如此)。然后第三个结果发生在第二个 print_preorder 期间。它中断并停在一个空节点上，但左右数据都显示“无法读取内存”。我做错了什么？我想不通。在我尝试删除一个节点之前，我的所有其他树功能(包括预订打印)。

再澄清一点，我的 remove_helper 函数有问题。所以我可以继续从 Tree1 中删除 Tree2 中存在的节点。

Answer 1

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

将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;