我正在编码以打印BST预购和后购遍历。
类树定义如下
class BinSearchTree{
char symbol;
BinSearchTree *lChild;
BinSearchTree *rChild;
public:
BinSearchTree(char letter) { symbol = letter;lChild = NULL; rChild = NULL;}
BinSearchTree() { symbol = '0';}
BinSearchTree* buildTree(BinSearchTree *tree, char letter);
void printTreePreOrder (BinSearchTree *temp, std::ofstream &fp1);
void printTreeInOrder (BinSearchTree *temp, std::ofstream &fp1);
};
我使用了一个简单的递归来创建BST
BinSearchTree* BinSearchTree::buildTree(BinSearchTree *tree, char letter){
if (tree == NULL) {
tree = new BinSearchTree (letter);
return tree;
}
else {
if (letter<(tree->symbol))
{
tree->lChild = (BinSearchTree*) buildTree(tree->lChild, letter);
return tree;
}
else{
tree->rChild = (BinSearchTree*) buildTree(tree->rChild, letter);
return tree;
}
}
return tree;
}
但是当我打印遍历时,我会遇到分段错误。我将这段代码用于预购,并将类似的代码用于后购
void BinSearchTree::printTreePreOrder (BinSearchTree *temp, std::ofstream &fp1) {
if (temp == NULL){
return;
}
else{
fp1 << symbol << " ";
printTreePreOrder(lChild, fp1);
printTreePreOrder(rChild, fp1);
}
}
在我的主代码中,我使用创建我的树
T = new BinSearchTree(str[0]);
for(i=1; i<num; i++){
fp >> str[i];
T->buildTree(T,str[i]);
}
并使用进行遍历
T->printTreePreOrder(T,fp1)
从几天以来,我一直在努力找出错误,我认为这是一个愚蠢的错误。感谢您的帮助。
PS-在Ubuntu 14.04上工作,使用G++编译器。
首先,您需要决定遍历算法在类中还是在类外的位置。现在,该方法属于该类,但接收该类类型的参数(这看起来很奇怪,在这种特殊情况下是错误的)。
void BinSearchTree::printTreePreOrder (BinSearchTree *temp, std::ofstream &fp1);
正确的签名应该是:
void BinSearchTree::printTreePreOrder(std::ofstream &fp1)
在这种情况下,您使用实际节点作为根进行迭代,代码将类似于:
void BinSearchTree::printTreePreOrder(std::ofstream &fp1) {
fp1 << symbol << " ";
if (lChild != NULL)
printTreePreOrder(lChild, fp1);
if (rChild != NULL)
printTreePreOrder(rChild, fp1);
}
或者,如果函数超出类:
void printTreePreOrder(BinSearchTree *temp, std::ofstream &fp1) {
if (temp == NULL)
return ;
else {
fp1 << temp->symbol << " ";
if (temp->lChild != NULL)
printTreePreOrder(temp->lChild, fp1);
if (temp->rChild != NULL)
printTreePreOrder(temp->rChild, fp1);
}
}
在这种情况下,您需要访问实际实现中的成员symbol
、lChild
和rChild
是私有的(或者将方法声明为friend)。
你的问题是你错过了匹配的参数和成员变量,例如:
在您对printTreePreOrder
方法的调用中:T->printTreePreOrder(T,fp1)
在这种情况下temp
将是T
,lChild
和rChild
将是T
的子级,这里没有问题,假设两个子级存在,您打印T
的symbol
,并在该调用中调用printTreePreOrder(lChild, fp1);
temp
等于lChild
,但lChild
和rChild
已经引用了T
的成员变量,这就是问题所在。
在您的情况下,最好是in class
,因为它没有声明members variables public
或friend
。
方法buildTree
的返回似乎很奇怪和错误(它和printThreePreOrder
有同样的问题。你不需要返回任何东西,新数据被插入到实际节点或转发到其中一个子节点,不需要返回什么:
代码将类似于(类中版本):
void BinSearchTree::buildTree(char letter){
if (letter < tree->symbol) {
if (lChild == NULL)
lChild = new BinSearchTree(letter);
else
lChild->buildTree(letter);
} else {
if (rChild == NULL)
rChild = new BinSearchTree(letter);
else
rChild->buildTree(letter);
}
}