二叉搜索树 - 删除功能不起作用

Question

#include <iostream> 
#include <string> 
#include <fstream> 
using namespace std; 
template <class T> 
struct TreeNode{ 
    string value; 
    T key; 
    TreeNode<T> *Parent; 
    TreeNode<T> *LeftChild; 
    TreeNode<T> *RightChild; 
    TreeNode (T k,string Val) 
    { 
    this->value=Val; 
    this->key=k; 
    this->Parent=NULL; 
    this->LeftChild=NULL; 
    this->RightChild=NULL; 
    } 
}; 

template <class T> 
class BinaryTree{ 
    private: 
    TreeNode<T> *Root; 
    public: 
     BinaryTree(); 
     void LoadTree(const char file[]); 
     ~BinaryTree(); 
     void insertNode(T Key,string Val); 
     void deleteNode(T Key); 
     string searchNode(T Key); 
     void UpdateKey(T newkey,T oldkey); 
     int Height(TreeNode<T> *node); 
     int height(); 
}; 

template <class T> 
BinaryTree<T>::BinaryTree() 
{ 
    Root=NULL;      
} 

template <class T> 
void BinaryTree<T>::insertNode(T Key,string Val) 
{ 
    TreeNode<T> **temp=&Root; 
    TreeNode<T> *temp1=NULL; 
    if (*temp==NULL) 
    { 
    Root=new TreeNode<T>(Key,Val); 
    return; 
    } 
    else 
    {    
    while (*temp!=NULL) 
    { 
     temp1=*temp; 
     if (temp1->key>Key) 
     { 
      temp=&(*temp)->LeftChild; 
     } 
     else if (temp1->key<Key) 
     { 
      temp=&(*temp)->RightChild; 
     } 
    } 
    } 
    *temp=new TreeNode<T>(Key,Val);    
    (*temp)->Parent=temp1; 
} 

template <class T> 
void BinaryTree<T>::LoadTree(const char *file) 
{ 
    ifstream fin; 
    fin.open(file); 
    string buffer; 
    T buff; 
    while (!fin.eof()) 
    { 
     getline(fin,buffer,'~'); 
     fin>>buff; 
     if (!buff) 
     continue; 
     insertNode(buff,buffer); 
    }   
    fin.close(); 
} 

void BinaryTree<T>::deleteNode(T Key) 
{ 
    TreeNode<T> *temp=Root; 
    TreeNode<T> *temp1=temp; 
    while (temp!=NULL) 
    { 
     if (temp->key==Key) 
     { 
      temp1=temp;    
      if (temp==Root) 
      { 
       TreeNode<T> *temp2=Root; 
       temp2=temp2->RightChild; 
       while (temp2->LeftChild!=NULL) 
       { 
        temp2=temp2->LeftChild; 
       } 
       temp->key=temp2->key; 
       temp->value=temp2->value; 
       delete temp2;    
      } 
      else if (temp->RightChild==NULL) 
      { 
       TreeNode<T> *temp2=temp; 
       temp2=temp->Parent; 
       if (temp2->RightChild==temp) 
       { 
        temp2->RightChild=temp->LeftChild; 
        (temp->LeftChild)->Parent=temp2; 
       } 
       else if (temp2->LeftChild==temp) 
       { 
        temp2->LeftChild=temp->LeftChild; 
        (temp->LeftChild)->Parent=temp2; 
       } 

       delete temp1; 
       delete temp; 
       return; 
      } 
      else if (temp->LeftChild==NULL) 
      { 
       TreeNode<T> *temp2=temp; 
       temp2=temp->Parent; 
       if (temp2->RightChild==temp) 
       { 
        temp2->RightChild=temp->RightChild; 
        (temp->RightChild)->Parent=temp2; 
       } 
       else if (temp2->LeftChild==temp) 
       { 
        temp2->LeftChild=temp->RightChild; 
        (temp->RightChild)->Parent=temp2; 
       } 
       delete temp1; 
       delete temp; 
       return; 
      } 
      else if (temp->RightChild!=NULL) 
      { 
       TreeNode<T> *tmp=temp; 
       temp=temp->RightChild; 
       if (temp->LeftChild!=NULL) 
       { 
        while (temp->LeftChild!=NULL) 
        { 
         tmp=temp; 
         temp=temp->LeftChild; 
        }  
       } 
       if (tmp!=temp1) 
       tmp->LeftChild==NULL; 
       else 
       temp1->RightChild==NULL; 

       temp1->key=temp->key; 
       temp1->value=temp->value; 
       delete temp; 
       return; 
      } 
     } 
     if (temp->key>Key) 
     { 
      temp=temp->LeftChild; 
     } 
     else if (temp->key<Key) 
     { 
      temp=temp->RightChild; 
     } 
}        
return; 
}   

这是我制作的二叉搜索树的代码的一部分。我在运行删除功能时遇到问题，即对于某些节点，我得到错误“testing.exe已停止工作” .testing是我的主要file.I的名字一再检查，但我似乎没有找到problem.Can任何人看到这个问题？谢谢

Answer 1

在这两种情况下，在删除temp1和temp时，它们都指向相同的地址。

Answer 2

有肯定不止一个问题，您的代码。

假设要删除存储在根目录下的键：

if (temp->key==Key) 
{ 
    temp1=temp;    
    if (temp->RightChild==NULL) 
    { 
    TreeNode<T> *temp2=temp; 
    temp2=temp->Parent;   // temp2 will be NULL here 
    if (temp2->RightChild==temp) 
    { 
     temp2->RightChild=temp->LeftChild; // thus dereferencing NULL either here 
     (temp->LeftChild)->Parent=temp2; 
    } 
    else if (temp2->LeftChild==temp) 
    { 
     temp2->LeftChild=temp->LeftChild; // ... or here 
     (temp->LeftChild)->Parent=temp2; 
    } 

    delete temp1; 
    delete temp; 
    return; 
    } 

的方法，另外考虑看看你的代码的轮廓办案似乎是不正确的：

if (temp->key==Key) 
{ 
    temp1=temp;    
    if (temp->RightChild==NULL) 
    { 
    // do something 
    } 
    else if (temp->LeftChild==NULL) 
    { 
    // do something 
    } 
    else if (temp->RightChild!=NULL) 
    { 
    // do something 
    } 
    else if (temp->LeftChild!=NULL && temp->RightChild==NULL) 
    { 
    // code never reached 
    } 
}