Stack Vorlage hat einige logische Fehler für die Implementierung von binären Baum

Question

Ich habe eine Vorlage von Stack und eine Vorlage von TreeNode (Binary Tree). Es folgt der Code von zwei Klassen (Stack und TreeNode). Ich habe erfolgreich Daten in den Baum eingefügt, indem ich die insert() -Funktion verwendet habe, aber es gibt ein Problem, wenn ich es mit dem Stack zurückgeholt habe. Es folgen die Kompilierzeitfehler:

Fehler 1 Fehler C2143: Syntaxfehler: fehlende ';' vor '*' c: \ users \ computerhaus \ desktop \ baum 1 \ baum 1 \ source.cpp 8 1 Baum 1

Fehler 2 Fehler C4430: fehlender Typ Specifier - int angenommen. Hinweis: \ users \ Computer Haus \ Desktop \ tree 1 \ tree 1 \ source.cpp 8 1 Baum 1

#include<iostream> 
#include<stdlib.h> 
using namespace std; 

template<class T> 
class Stack{ 
private: 
    TreeNode<T> *headNode, *pastCurrentNode; 

public: 
    Stack(){ 
     headNode = new TreeNode<T>; 
     headNode=NULL; 
    } 

    void push(T x){ 
     TreeNode<T>* newNode = new TreeNode<T>; 
     newNode->set(x); 

     if(headNode != NULL){ 
      newNode->setNext(headNode); 
      pastCurrentNode=headNode; 
      headNode=newNode; 
     } 
     else{ 
      headNode=newNode; 
      pastCurrentNode=headNode; 
     } 
    } 

    T pop(){ 
     TreeNode<T>* p = new TreeNode<T>; 
     p = headNode; 
     headNode = pastCurrentNode; 
     T x = p->get(); 
     delete p; 
     return x; 
    } 

    T top(){return headNode->get();} 

    bool isEmpty(){return (headNode == NULL);} 
}; 

template<class T> 
class TreeNode{ 
private: 
    TreeNode* right, *left; 
    T* object; 


public: 
    TreeNode(){ 
     this->left = this->right = NULL; 
     object = NULL; 
    } 

    TreeNode(T* object){ 
     this->object = object; 
     this->left = this->right = NULL; 
    } 

    T* getInfo(){ 
     return this->object; 
    } 

    void setInfo(T* object){ 
     this->object = object; 
    } 

    TreeNode* getLeft(){return this->left;} 
    void setLeft(TreeNode* left){this->left = left;} 
    TreeNode* getRight(){return this->right;} 
    void setRight(TreeNode* right){this->right = right;} 

    int isLeaf(){ 
     if(this->left==NULL && this->right == NULL){ 
      return 1; 
     } 
     return 0; 
    } 

}; 


void insert(TreeNode<int>* root, int* info){ 
    TreeNode<int>* newNode = new TreeNode<int>(info); 
    TreeNode<int>*p, *q; 

    p = q = root; 

    while(*info != *p->getInfo() && q != NULL) 
    { 
     p = q; 

     if(*info < *p->getInfo()) 
      q = p->getLeft(); 
     else 
      q = p->getRight(); 

    } 

    if(*info == *p->getInfo()){ 
     cout<<"Error: Duplication: "<<*info<<endl; 
     delete newNode; 
    } 
    else if(*info < *p->getInfo()){ 
     p->setLeft(newNode); 
    } 
    else{ 
     p->setRight(newNode); 
    } 
} 



void sInOrder(TreeNode<int>* root){ 
    Stack< TreeNode<int>* > stack; 
    TreeNode<int>* p; 

    p=root; 

    do{ 
     while(p != NULL){ 
      stack.push(p); 
      p = p->getLeft(); 
     } 
     //At this point left tree is empty 

     if(! stack.isEmpty()){ 
      p = stack.pop(); 
      cout<<*p->getInfo()<<" "; 
      //go back and traverse right subtree 
      p = p->getRight(); 
     } 
    } 
    while(!stack.isEmpty() || p!=NULL); 

} 

int main(){ 

    int x[]={14,15,4,9,7,18,3,5,16,4,20,17,9,14,5,-1}; 
    TreeNode<int>* root = new TreeNode<int>; 

    root->setInfo(&x[0]); 

    for(int i=1; x[i]>0; i++){ 
     insert(root, &x[i]); 
    } 

    cout<<"\nStacked In Order: "; sInOrder(root); 
    cout<<endl; 


    system("pause"); 
} 

Answer 1

Sie haben: C++ nicht default-int c unterstützen

TreeNode<T> *headNode, *pastCurrentNode; 

aber TreeNode wird nicht vor dieser Zeile deklariert. Sie müssen entweder eine Vorwärtsdeklaration von TreeNode oder die vollständige Definition von TreeNode hinzufügen, bevor Sie TreeNode<T>* headNode verwenden können.

Forward-Deklaration:

template <class T> class TreeNode; 

wird für die Erklärungen von headNode und pastCurrentNode genügen. Allerdings wird es nicht für

genügen

Stack(){ 
    headNode = new TreeNode<T>; 
    headNode=NULL; // This is a problem anyway. 
        // You have just leaked memory. 
} 

Um in der Lage zu sein, verwenden

headNode = new TreeNode<T>; 

Sie die vollständige Definition von TreeNode benötigen.

Da TreeNode hängt nicht von Stack, mein Rat an Sie wäre, die vollständige Definition von TreeNode vor der Definition von Stack zu bewegen.

aktualisieren, als Reaktion auf Kommentar des OP

// Define TreeNode first. 

template<class T> 
class TreeNode{ 
private: 
    TreeNode* right, *left; 
    T* object; 


public: 
    TreeNode(){ 
     this->left = this->right = NULL; 
     object = NULL; 
    } 

    // Add rest of TreeNode definition 
}; 

// Now define Stack. 

template<class T> 
class Stack{ 
private: 
    TreeNode<T> *headNode, *pastCurrentNode; 

public: 
    Stack(){ 
     headNode = new TreeNode<T>; 
     headNode=NULL; 
    } 

    // Add rest of Stack definition 

}; 

PS ich bemerkt, dass Sie

TreeNode<T>* newNode = new TreeNode<T>; 
    newNode->set(x); 

in Stack::push verwenden. Es gibt jedoch keine set Funktion in TreeNode. Sie müssen Ihren Code entsprechend aktualisieren, damit dies funktioniert.