바이너리 트리 오류에서 삭제

Question

바이너리 트리에서 가장 큰 숫자를 탐지하기 위해 작은 코드를 작성 했으므로 간단하고 잘 작동하며 마지막 오른쪽 노드 (경우에 따라)까지 멀리 이동 한 다음 나는 이걸 삭제하고 싶다. 나는 비슷한 물음으로 보았지만 숫자 만 지워야한다. 그러나 검색을 마치고 돌아 오면 내 prog이 충돌한다. 삭제하고 다시 나열하십시오.

다음

T Remove(Node* theRoot) 
     { 
     if (root == NULL) 
     { 
      cout<<"There is no tree"; 
      return -1; 
     } 

     if (theRoot->rChildptr != NULL) 
      return Largest(theRoot->rChildptr); 
     else 
      delete theRoot; 
      return theRoot->data; 

    } 

전체 코드입니다 :

#include <iostream> 
#include <string> 
#include <cstdlib> 


using namespace std; 


template<class T> 
class BinaryTree 
{ 

struct Node 
    { 
     T data; 
     Node* lChildptr; 
     Node* rChildptr; 

     Node(T dataNew) 
     { 
      data = dataNew; 
      lChildptr = NULL; 
      rChildptr = NULL; 

     } 
    }; 
private: 
    Node* root; 

     void Insert(T newData, Node* &theRoot) 
     { 
      if(theRoot == NULL) 
      { 
       theRoot = new Node(newData); 
       return; 
      } 

      if(newData < theRoot->data) 
       Insert(newData, theRoot->lChildptr); 
      else 
       Insert(newData, theRoot->rChildptr); 
     } 

     void PrintTree(Node* theRoot) 
     { 
      if(theRoot != NULL) 
      { 
       PrintTree(theRoot->lChildptr); 
       cout<< theRoot->data<<" \n"; 
       PrintTree(theRoot->rChildptr); 
      } 
     } 
     T Largest(Node* theRoot) 
      { 
      if (root == NULL) 
      { 
       cout<<"There is no tree"; 
       return -1; 
      } 

      if (theRoot->rChildptr != NULL) 
       return Largest(theRoot->rChildptr); 
      else 
       delete theRoot; 
       return theRoot->data; 

     } 
     T Remove(Node* theRoot) 
     { 
      if (root == NULL) 
      { 
       cout<<"There is no tree"; 
       return -1; 
      } 

      if (theRoot->rChildptr != NULL) 
       return Largest(theRoot->rChildptr); 
      else 
       delete theRoot; 
       return ; 
     }; 

    public: 
     BinaryTree() 
     { 
      root = NULL; 
     } 

     void AddItem(T newData) 
     { 
      Insert(newData, root); 
     } 

     void PrintTree() 
     { 
      PrintTree(root); 
     } 
     T Largest() 
     { 
      return Largest(root); 
     } 
     //void Remove() 
     //{ 
     // Remove(root); 
     //} 

    }; 

    int main() 
    { 
     BinaryTree<int> *myBT = new BinaryTree<int>(); 
     myBT->AddItem(2); 
     myBT->AddItem(20); 
     myBT->AddItem(5); 
     myBT->AddItem(1); 
     myBT->AddItem(10); 
     myBT->AddItem(15); 
      //for(int i = 0; i < 10; i++)   //randommal tolti fel 
       //myBT->AddItem(rand() % 100); 
     cout << "BinaryTree:" << endl;    //kilistazaa a fat 
     myBT->PrintTree(); 
     cout << "Largest element: " << myBT->Largest() << endl; //visszaadja a legnagyobb elemet 
     //myBT->Remove(); 
     myBT->PrintTree(); 
    } 

실제 삭제 기능은 그래서는 음식물을 실행할 수 있습니다 // 주석에

여기 내 검색입니다.

Answer 1

단순히 원하지 않는 객체 인 delete을 사용할 수 없으므로 찾을 노드를 삭제해야합니다. 그리고 노드에 자식이있는 경우 다른 노드의 자식 노드를 트리에 다시 연결해야 도달 할 수 있습니다.

너무 까다로운 이유는 제대로 업데이트해야한다는 것입니다. 삭제되는 노드에 대한 부모 참조. 삭제 된 노드의 자식 중 하나에 대한 '자식'포인터 중 하나. 삭제 된 노드의 양쪽 자식으로부터의 부모 링크. 비 순차적 업데이트를 수행하면 부실 포인터와 메모리 손상을 읽을 수 있으므로 노드 내에서 더 이상 참조가 필요없고 참조를 제거 할 때까지 노드 제거를 기다려야합니다. 노드는 다른 곳에서 왔습니다.

업데이트

는 "지난 권리 노드가"사실에 트리의 루트가 될 수 있다는 것을 잊지 마십시오 :

5 
    4 
    3 
2 
1 

5은의 가장 큰, 가장 오른쪽, 노드 귀하의 나무, 그리고 만약 당신이 그것을 삭제, 당신은 전체 나무를 잃었습니다.

여기에 표시되지 않는 재조정을하지 않는 한, 당신이 경우, 당신은 또한이 사건을 처리해야합니다 :

• 삭제 : Wikipedia에서

  2 
  1 
  

  우리의 친구들은 이진 검색 트리에서 노드를 삭제하는 방법을 분석하는 데 매우 친절했다 leaf (자식이없는 노드) : 잎을 삭제하는 것은 간단합니다. 트리에서 제거하기 만하면됩니다.

• 하나의 하위 노드 삭제 : 노드를 제거하고 하위 노드로 바꿉니다.
• 두 명의 자식이있는 노드 삭제 : 삭제할 노드를 호출합니다. N. N을 삭제하지 않습니다. 대신 해당 후속 노드 인 또는 선행 노드 인 R을 선택하십시오. N의 값을 다음과 같이 바꾸십시오. R의 값은, 당신의 삭제 코드는 이러한 경우의 세 가지를 모두 처리해야 R.

을 삭제합니다. 삭제할 노드가 트리의 루트 일 수 있고 부모 노드가없는 것을 잊지 마십시오.

Answer 2

전체 프로그램을 게시하여 컴파일 할 수 있습니까? 하지만 근본적으로 문제는 theRoot-> rChildptr이 NULL 일 때 theRoot를 삭제하고 return 문이 아무데도 가리키는 root-> 데이터를 반환하려고 시도한다는 것입니다.

Answer 3

theRoot을 삭제하고 참조 해제하려고합니다. 당신이 노드에 저장된 값을 반환 할 경우는 다음과 같이 먼저 로컬 복사본을 만들 필요가 :

T value = theRoot->data; 
delete theRoot; 
return value; 

는 else 문의 일부가 의도 return thetRoot->data; 라인인가? 만약 당신이 이런 식으로 주위에 괄호를 추가 할 필요가 있도록 :

if (theRoot->rChildptr != NULL) 
{ 
    return Largest(theRoot->rChildptr); 
} 
else 
{ 
    T value = theRoot->data; 
    delete theRoot; 
    return value; 
} 

을 또는 (아이 포인터가 null의 경우 항상 반환 이후) 단순히 전부 다른 케이스를 제거 : 또한 필요합니다

if (theRoot->rChildptr != NULL) 
{ 
    return Largest(theRoot->rChildptr); 
} 

T value = theRoot->data; 
delete theRoot; 
return value; 

을 부모 노드가 여전히 삭제 된 자식을 가리 키지 않는지 확인하십시오 (많은 코드를 게시하지 않았기 때문에 계속 진행되는 것을보기가 어렵습니다).