Binärbaum Traversal Baum nicht abgeschlossen

Question

Ich habe ein Binär-Baum-Programm für meine Präsentation versucht, eine Postorder Traversal mit Dateieingabe machen, stellte sich heraus, wenn der Einfügeschritt starten der Baum hat nur 1 Knoten und dann wiederholen, bis es gelesen bis zum Ende der Datei. Irgendwelche Ideen was hier schief gelaufen ist?

Dies sind die Daten i

in txt verwenden

5709611981 A N 0623sweet@gmail.com

5909680109 A N 35563@bodin.ac.th

5909680059 N a.supitcha@hotmail. com A

5909610114 A N aladen009@hotmail.com

5909610031 N aomsin3475@gmail.com A

5909520024 A N apisittest@hotmail.com

5909680018 A N apstaan@gmail.com

5709650567 A S apuonn_ap@hotmail.com

5709650062 A S athachai-riders@hotmail.com

5909610064 A N babe-anusorn@hotmail.com

5909650193 A S baifeern@gmail.com

5709650021 A S ball.bus@hotmail.com

5909610460 A N bambee18341@gmail.com

5909650011 A S bell12546789@gmail.com

5809650798 A S big__007@hotmail.com

Code:

class Person{ 
private: 
    string id; 
    string section; 
    string status; 
    string email; 
public: 
    Person(); 
    Person(string id,string section,string email,string status); 
    string getID(); 
    string getSection(); 
    string getStatus(); 
    string getEmail(); 
    void setID(string newid); 
    void setEmail(string newEmail); 
    void setSection(string newsection); 
    void setStatus(string newstatus); 
    }; 

    class BinarySearchTree 
    { 
private: 
    struct tree_node 
    { 
     tree_node* left; 
     tree_node* right; 
     Person data; 
    }; 
    tree_node* root; 

public: 
    BinarySearchTree() 
    { 
     root = NULL; 
    } 

    bool isEmpty() const { return root == NULL;} 
    void print_postorder(); 
    void postorder(tree_node*); 
    void print_preorder(); 
    void preorder(tree_node*); 
    void insert(Person); 
    void remove(string); 
    void search(string key); 
    void changeStatus(string key,string newstatus); 
    }; 

    Person::Person() 
    { 

    } 

    Person::Person(string newid,string newsection,string newemail,string newstatus){ 
id = newid; 
section = newsection; 
email = newemail; 
status = newstatus; 
    } 
    string Person::getID(){ 
return id; 
     } 
    string Person::getSection(){ 
return section; 
     } 
    string Person::getEmail(){ 
return email; 
     } 
    string Person::getStatus(){ 
return status; 
     } 
    void Person::setStatus(string newstatus){ 
status = newstatus; 
     } 
    void Person::setID(string newid){ 
status = newid; 
     } 
    void Person::setEmail(string newemail){ 
status = newemail; 
     } 
    void Person::setSection(string newsection){ 
status = newsection; 
     } 
     void BinarySearchTree::insert(Person p){ 
tree_node* t = new tree_node; 
tree_node* parent; 
t->data = p; 
t->left = NULL; 
t->right = NULL; 
parent = NULL; 


if(isEmpty()) root = t; 
else{ 
    tree_node* curr; 
    curr = root; 
    while(curr) 
    { 
     parent = curr; 
     if(t->data.getID() > curr->data.getID()){ 
     curr=curr->right; 
     } 
     else{ 
      curr = curr->left; 
     } 
    } 

    if(t->data.getID() < parent->data.getID()){ 
     parent->left = t; 
    } 
    else{ 
     parent->right = t; 
      } 
     } 
     } 

       void BinarySearchTree::print_postorder(){ 
    postorder(root); 
} 

void BinarySearchTree::postorder(tree_node* p) 
{ 
    if(p != NULL) 
    { 
     if(p->left){ 
      postorder(p->left); 
     } 
     if(p->right){ 
      postorder(p->right); 
     } 
     cout<<" "<<p->data.getID() << " " << endl ; 
    } 
    else { 
    cout<<" NULL P " << endl ; 
    return; 
    } 
} 

void BinarySearchTree::search(string key){ 
    bool found = false; 

    tree_node* curr; 
    tree_node* parent; 
    curr = root; 
    while(curr != NULL){ 
     if(curr->data.getID() == key){ 
      found = true ; 
      cout << "Contact Email : " << curr->data.getEmail() << endl; 
     } 
     else 
     { 
      parent = curr; 
      if(key>curr->data.getID()){ 
       curr = curr->right; 
      } 
      else curr = curr->left; 
     } 
    } 
    if(!found){ 
     cout<<" This student is not in this class. " << endl; 
     return; 
    } 


} 

void fillTree(BinarySearchTree b) 
{ 
ifstream file; 
file.open("classlist60.txt"); 
if(!file){ 
    cout << "File error." << endl; 
} 

string id; 
string section; 
string email; 
string status; 
Person p; 
int count = 0; 
int halt = 0 ; 
while(file >> id >> section >> email >> status) 
{ 
    p.setID(id); 
    p.setSection(section); 
    p.setEmail(email); 
    p.setStatus(status); 
    count++; 
    if(status == "W"){ 
     halt++; 
    } 
    b.insert(p); 
} 
b.print_postorder(); 

cout << endl << " Total registered students :" << count << endl; 
cout << " Num of withdrawal Students :" << halt << endl; 
file.close(); 
} 

int main(){ 
BinarySearchTree b; 
string id; 
string email; 
fillTree(b); 

cout << endl << " Search Email for student ID : " ; 
cin >> id; 
b.search(id); 

return 0; 
} 

Das Ergebnis ist:

Das Ergebnis sollte alle Details der Studenten in Postorder sein und über Eingabebaum stellte sich heraus suchen sein kann, ist fast leer

Answer 1

In Ihrer insert Funktion verknüpfen Sie die Eltern mit dem Knoten t, aber Sie nicht Verknüpfen Sie den Knoten t mit dem Knoten, den er ersetzt. So verlieren Sie am Ende, worauf die Eltern hinwiesen. Sie müssen den neuen Knoten zwischen dem übergeordneten Element und seinem untergeordneten Element einfügen.

Die Idee ist die gleiche wie Einfügen in eine verkettete Liste.Bevor Sie einsetzen, müssen Sie:

  parent 
     / \ 
     child t 

Aber was Sie wollen, ist dies:

  parent 
     / \ 
     child t 
       \ 
       child 

, die Ihren Code eine einfache Modifikation ist:

  parent 
     / \ 
     child child 

Ihr Code tut dies

if(t->data.getID() < parent->data.getID()){ 
    t->left = parent->left; // link to parent's previous child 
    parent->left = t; 
} 
else{ 
    t->right = parent->right; // link to parent's previous child 
    parent->right = t; 
     } 
    } 
    }