二叉搜索树删除（Inorder Pred方法）C ++ [英] Binary Search Tree Deletion (Inorder Pred method) C++

问题描述

好的，所以我认为它是固定的，但我得到完全不一致的结果。
我重写了它从头开始新鲜，这里是我的结果。我得到没有错误，没有崩溃，它只是不会删除他们。它完全混乱了树，给了我一吨多的叶子，并混合一切。不确定要去哪里

Ok so I thought it was fixed, but I'm getting totally inconsistent results. I rewrote it kind of from scratch to start fresh and here are my results. I get no errors, no crashing, it just doesn't remove them. It just totally messes up the tree and gives me a ton more leaves, and mixes everything up. Not sure where else to go

template <class T>
void BST<T>::remove(struct Node<T>*& root, const T& x)
{
   Node<T>* ptr = root;
   bool found = false;
   Node<T>* parent;


   while (ptr != NULL && !found)
   {
       if (x < ptr->data)
       {
           parent = ptr;
           ptr = ptr->left;
       }
       else if (x > ptr->data)
       {
           parent = ptr;
           ptr = ptr->right;
       }
       else
           found = true;
   }

   if (found == false)
       return;
   else
   {
       if(ptr->left != NULL && ptr->right != NULL)
       {
           Node<T>* inOrderPtr = ptr->left;
           parent = ptr;
           while (inOrderPtr->right != NULL)
           {
               parent = inOrderPtr;
               inOrderPtr = inOrderPtr->right;
           }

           ptr->data = inOrderPtr->data;
           ptr = inOrderPtr;
       }
    Node<T>* subPtr = ptr->left;
    if (subPtr == NULL)
        subPtr = ptr->right;

    else if (parent->left == ptr)
        parent->left = subPtr;

    else
        parent->right = subPtr;

    delete ptr;
    }

推荐答案

树独特？它看起来像是从你的代码...

Are each T found in the tree unique? It looks like they are from your code...

看起来这应该工作：

else case删除根节点：

In the else case deleting the root node:

Node<T> *tmp_r = root->left;
Node<T> *parent = root;
while (tmp_r->right != NULL)
{
    parent = tmp_r;
    tmp_r = tmp_r->right;
}
Node<T> *tmp_l = tmp_r;
while (tmp_l->left != NULL)
    tmp_l = tmp_l->left;

tmp_l->left = root->left;
tmp_r->right = root->right;
parent->right = NULL;

parent = root;
root = tmp_r;
delete parent;

这篇关于二叉搜索树删除（Inorder Pred方法）C ++的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！