堆棧模板實現二叉樹有一些邏輯錯誤

Question

我有一個堆棧模板和TreeNode（二叉樹）模板。以下是兩個類的代碼（堆棧和TreeNode）。我使用insert（）函數成功地將數據插入到樹中，但是在使用堆棧取回數據時出現問題。以下是編譯時錯誤：

錯誤1錯誤C2143：語法錯誤：缺少';'之前'*'c：\ users \ computer house \ desktop \ tree 1 \ tree 1 \ source.cpp 8 1樹1

錯誤2錯誤C4430：缺少類型說明符 - int假定。注意：C++不支持默認int C：\用戶\計算機房子\桌面\樹1 \樹1 \ source.cpp 8 1 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

您有：

TreeNode<T> *headNode, *pastCurrentNode; 

但TreeNode未在該行之前聲明。您需要添加TreeNode的前向聲明或TreeNode的完整定義，然後才能使用TreeNode<T>* headNode。

向前聲明：

template <class T> class TreeNode; 

將滿足的headNode和pastCurrentNode的聲明。但是，它不會足夠了

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

爲了能夠使用

headNode = new TreeNode<T>; 

你需要的TreeNode完整定義。

由於TreeNode不依賴於Stack，我對你的建議將是Stack定義之前移動的TreeNode完整定義。

更新，響應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我注意到，您在使用Stack::push

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

。但是，TreeNode中沒有set函數。你需要適當地更新你的代碼才能工作。