#include <iostream>
using namespace std;
class Element
{
public:
Element* left;
Element* right;
char key;
Element();
Element(char k);
};
Element::Element()
{
left = NULL;
right = NULL;
key = 0;
}
Element::Element(char k)
{
left = NULL;
right = NULL;
key = k;
}
class BinaryTree
{
public:
Element* root;
BinaryTree();
void createTree(Element* e);
void postTravel(Element* e);
void destroyTree();
};
BinaryTree::BinaryTree()
{
root = NULL;
cout<<"please enter the tree element by preorder:(use ‘#‘ as empty node)"<<endl;
createTree(root);
}
void BinaryTree::createTree(Element* e)
{
//create root node
e = new Element();
cin>>e->key;
if(e->key==‘#‘)
{
return ;
}
else
{
//create left child tree
createTree( e->left );
//create right child tree
createTree( e->right );
}
}
void BinaryTree::postTravel(Element* e)
{
if(e->key==‘#‘)
{
cout<<"#"<<endl;
return ;
}
else
{
postTravel(e->left);
postTravel(e->right);
cout<<e->key<<endl;
}
}
int main(void)
{
BinaryTree tree;
tree.postTravel(tree.root);
return 0;
}
想创建的树如下所示，
A / B C / \ / D # # E / \ / F # # # / # #
#号来表示空的结点，按照先序遍历，这棵树的顺序如下：
ABDF####C#E##
编译程序，运行，会提示按照先序遍历输入一棵树的结点，用“#”来表示空结点。输入上面的ABDF####C#E##，运行结果如下：
please enter the tree element by preorder:(use ‘#‘ as empty node) ABDF####C#E## Segmentation fault
发生了段错误。
经过追查，发现是建树的时候发生的错误。在声明一个树的对象的时候，会调用默认的构造方法，而在构造方法中调用了函数createTree，该函数的参数是Element* e。在递归建树的过程中，第一次传递给createTree的参数是root，root的值是NULL。因此编译器将root的值NULL，复制了一份，保存在临时变量中，当使用new Element来分配一个新的对象的时候，并没有把这个新对象的地址保存在root的地址空间中，而是保存在了临时的变量中，所以这就是由于值传递造成的错误。在很多时候，需要特别小心在参数中带有指针的函数，这些函数往往是发生错误的根源。
将该程序进行修改，就可以得到正确的结果：
#include <iostream>
using namespace std;
class Element
{
public:
Element* left;
Element* right;
char key;
Element();
Element(char k);
};
Element::Element()
{
left = NULL;
right = NULL;
key = 0;
}
Element::Element(char k)
{
left = NULL;
right = NULL;
key = k;
}
class BinaryTree
{
public:
Element* root;
BinaryTree();
void createTree(Element** e);
void postTravel(Element* e);
void destroyTree();
};
BinaryTree::BinaryTree()
{
root = NULL;
cout<<"please enter the tree element by preorder:(use ‘#‘ as empty node)"<<endl;
createTree(&root);
}
void BinaryTree::createTree(Element** e)
{
//create root node
*e = new Element();
cin>>(*e)->key;
if((*e)->key==‘#‘)
{
return ;
}
else
{
//create left child tree
createTree( &((*e)->left) );
//create right child tree
createTree( &((*e)->right) );
}
}
void BinaryTree::postTravel(Element* e)
{
if(e->key==‘#‘)
{
cout<<"#"<<endl;
return ;
}
else
{
postTravel(e->left);
postTravel(e->right);
cout<<e->key<<endl;
}
}
int main(void)
{
BinaryTree tree;
tree.postTravel(tree.root);
return 0;
}
运行的结果如下：
please enter the tree element by preorder:(use ‘#‘ as empty node) ABDF####C#E## # # F # D # B # # # E C A