2

我的二叉搜索树打印代码中有一些错误，我不知道为什么。（底部有错误）

#ifndef MYBSTREE_H
#define MYBSTREE_H

#include "abstractbstree.h"
#include "abstractstack.h"
using namespace std;

class LinkedStack *head = NULL;           //LINE 7

template<typename T>
class TreeNode
{
  public:
    T m_data;
    TreeNode* m_right;
    TreeNode* m_left;

};


template<typename T>
class LinkedStack: public AbstractStack<TreeNode<T>*>
{
  public:
    TreeNode<T>* m_data;
    LinkedStack *m_next;

    LinkedStack()
    {
      if(head != NULL)
        head = new LinkedStack;
      m_data = 0;
      m_next = NULL;
    }

    void clear()
    {
      while(head -> m_next != NULL)
      {
        LinkedStack *tmp = head -> m_next;
        head -> m_ldata= tmp -> m_ldata;
        head -> m_next = tmp -> m_next;
        delete tmp;
      }
    }


    void push(TreeNode<T>* x)
    {
      LinkedStack *tmp = new LinkedStack;
      tmp -> m_data = m_data;
      tmp -> m_next = m_next;
      m_data = x;
      m_next = tmp;
    }

    void pop()
    {
      if (isEmpty())
        cout<<"Panic! Nothing to pop"<<endl;
      else
      {
        LinkedStack *tmp;
        tmp = m_next;
        m_data = tmp -> m_data;
        m_next = tmp -> m_next;
        delete tmp;
      }
    }

    int& top()
    {
      if (isEmpty())
        cout<<"Panic! List is Empty"<<endl;

        return m_ldata;
    }

    bool isEmpty()
    {
      bool empty = false;

      if (m_next == NULL)
      {
        empty = true;
      }

      return empty;
    }
};

template<typename T>
class MyBSTree:public AbstractBSTree<T>
{
  private:

    TreeNode<T>* m_root;

  public:

    ~MyBSTree()  
    {
      clear();
    }

    MyBSTree()
    {
      m_root -> m_data = T();
      m_root -> m_right = NULL;
      m_root -> m_left = NULL;
    };

    int size() const
    {
        if(m_root==NULL)
          return 0;
        else
          return (size(m_root->m_left)+1+size(m_root->m_right));
    }

    bool isEmpty() const
    {
      if (m_root== NULL)
        return true;

      else
        return false;
    }

    int height() const
    {
      int lh,rh;
      if(m_root==NULL)
      {
        return 0;
      }
      else
      {
        lh = height(m_root->m_left);
        rh = height(m_root->m_right);

        if(lh > rh)
          return lh + 1;
        else
          return rh + 1;
      }
    }

    const T& findMax() const
    {
      TreeNode<T>* p = m_root;
      while(p -> m_right != NULL)
        p = p -> m_right;
      return p;
    }

    const T& findMin() const
    {
      TreeNode<T>* p = m_root;
      while(p -> m_left != NULL)
        p = p -> m_left;
      return p;
    }
/*
    int contains(const T& x) const;
*/
    void clear()
    {
      delete m_root;
    }

    void insert(const T& x)
    {
      TreeNode<T>* p = m_root;

      do
      {  
        if (x == p -> m_root)
          return;
        else if ( x < p->m_data)
        {
          if(p->m_left == NULL)
          {
              p->m_left = new TreeNode<T>;
              p -> m_left -> m_data = x;
              return;
          }
          else
            p = p -> m_left;
        }
        else if( x > p->m_data)
        {
          if(p->m_right == NULL)
          {
            p->m_right = new TreeNode<T>;
            p-> m_right -> m_data = x;
            return;
          }
          else
            p = p -> m_right;
        } 
      }while(p -> m_right != NULL && p -> m_left != NULL);
    }

    void remove(const T& x)
    {
        if(m_root == NULL)
            return;

        TreeNode<T>* q = m_root;
        TreeNode<T>* p;

        while(q != NULL)
        {
            if(m_root->m_data == x)
            {
                delete q;
                return;
            }
            else if(x > q->m_data)
            {
                p = q; 
                q = q->m_right;
            }
            else
            {
                p = q; 
                q = q->m_left;            
            }
        }

        if(q->m_left == NULL && q->m_right == NULL)
        {
            if(p == q)
                delete p;
            else if(p->m_left == q)
            {
                p->m_left = NULL;
                delete q;
            }
            else 
            {
                p->m_right = NULL;
                delete q;
            }
            return;
        }

        if((q->m_left == NULL && q->m_right != NULL) || (q->m_left != NULL && q->m_right == NULL))
        {
            if(q->m_left == NULL && q->m_right != NULL)
            {
                if(p->m_left == q)
                {
                    p->m_left = q->m_right;
                    delete q;
                }
                else
                {
                    p->m_right = q->m_right;
                    delete q;
                }
            }
            else
            {
                if(p->m_left == q)
                {
                    p->m_left = q->m_left;
                    delete q;
                }
                else
                {
                    p->m_right = q->m_left;
                    delete q;
                }
            }
            return;
        }

        if (q->m_left != NULL && q->m_right != NULL)
        {
            TreeNode<T>* check;
            check = q->m_right;
            if((check->m_left == NULL) && (check->m_right == NULL))
            {
                q = check;
                delete check;
                q->m_right = NULL;
            }
            else
            {
                if((q->m_right)->m_left != NULL)
                {
                    TreeNode<T>* m_leftq;
                    TreeNode<T>* m_leftp;
                    m_leftp = q->m_right;
                    m_leftq = (q->m_right)->m_left;
                    while(m_leftq->m_left != NULL)
                    {
                        m_leftp = m_leftq;
                        m_leftq = m_leftq->m_left;
                    }
                    q->data = m_leftq->data;
                    delete m_leftq;
                    m_leftp->m_left = NULL;
                }
                else
                {
                    TreeNode<T>* tmp;
                    tmp = q->m_right;
                    q->data = tmp->data;
                    q->m_right = tmp->m_right;
                    delete tmp;
                }
            }
            return;
        }
    }

    void printPreOrder() const
    {
      LinkedStack stack;
      stack<T>.push(m_root);                           //THIS LINE
      while(!stack.isEmpty())                          //THIS LINE
        {
          TreeNode<T>* root = stack.push();        //THIS LINE
          stack.pop();                             //THIS LINE
          if(root!= NULL)
          {
            stack.push(root->right);           //THIS LINE
            stack.push(root->m_left);          //THIS LINE
            cout << root->m_data << " ";
          }

        }

    }
/*
    void printPostOrder() const;

    void print() const;
    */
};


#endif

我得到的是错误说：

MyBSTree.h: In member function âvoid MyBSTree<T>::printPreOrder() constâ:
MyBSTree.h:362:9: error: invalid use of incomplete type âstruct LinkedStackâ
MyBSTree.h:7:7: error: forward declaration of âstruct LinkedStackâ

对于我在该特定功能中标记的所有行，我都知道这一点。我很确定它与模板语法有关，但我不确定。

4

2 回答 2

3

线class LinkedStack *head = NULL;没有意义。如果您想了解自己的LinkedStack，您应该：

  1. class在这一行中删除
  2. 传递正确的类型，因为它是一个模板
  3. 在模板类定义之后执行

像这样的东西：LinkedStack<your type> *head = NULL;

于 2012-11-07T19:31:12.880 回答
3

我不明白你的意思

class LinkedStack *head = NULL;           //LINE 7

这应该是前向声明吗？在这种情况下，它应该是

template<typename T>
class LinkedStack;

如果在那之后你试图初始化一个实例，那么它应该是

LinkedStack<int> *head = NULL; //int as a typename T

但是您不能将两者混合在一行中:)

于 2012-11-07T19:32:51.857 回答