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â
我得到了所有的線我都標誌着在那個特定的功能。我很確定它與模板語法有關，但我不確定。
混合使用這兩個這可能與問題沒有關係，但是您打印的方式可能是錯誤的。你已經檢查過了if（root-> left！= NULL），然後按下'和右邊的。你正在做的情況下，該節點只有一個權利，也沒有左邊的方式，那麼它仍然會通過'如果（）'，但將在'stack.push（）'' – noMAD