二叉搜索树 - 删除功能不工作 [英] Binary Search Tree--delete function not working

问题描述

#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是我的主要文件的名称。我已经检查了一遍又一次，但我似乎找到问题。任何人都看到问题？

This is part of the code for a Binary Search tree that I am making.I am facing a problem when I run the delete function i.e for some nodes, i am getting the error "testing.exe has stopped working".testing is name of my main file.I have checked again and again but I don't seem to find the problem.Can anyone see the problem?Thanks

推荐答案

在这两种情况下，您删除 temp1 和 temp ，它们都指向同一个地址。

In both cases where you delete temp1 and temp, they both point to the same address.

这篇关于二叉搜索树 - 删除功能不工作的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！