堆栈模板在实现二叉树时存在一些逻辑错误

Question

我有一个栈模板和一个TreeNode（二叉树）模板。下面是两个类（stack和TreeNode）的代码。我使用 insert() 函数成功地将数据插入到树中，但是在使用堆栈检索数据时出现问题。以下是编译时错误：

错误 1 错误 C2143：语法错误：缺少“;”在 '*' 之前 c:\users\computer house\desktop\tree 1\tree 1\source.cpp 8 1 树 1

错误 2 错误 C4430：缺少类型说明符 - 假定为 int。注意：C++ 不支持 default-int c:\users\computer house\desktop\tree 1\tree 1\source.cpp 8 1 Tree 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<T>* headNode.

之前，您需要添加 TreeNode 的前向声明或 TreeNode 的完整定义

前向声明：

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，我建议您将 TreeNode 的完整定义移到 Stack 的定义之前。

更新，回应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 我注意到你正在使用

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

在 Stack::push 中。但是，TreeNode中没有set函数。您需要适当更新代码才能使其正常工作。

堆栈模板在实现二叉树时存在一些逻辑错误

Stack template has some logical error for implementing binary tree

c++

tree

stack

data-structures