如何在二叉树构建时就确定每一个节点的父亲?
原有以下类:
struct BiNode {//节点类
public:
char data;//节点数据
BiNode *lchild, *rchild;//左右孩子
BiNode **parent;//父亲节点
};
class BiTree {//二叉树
private:
BiNode * root;//根节点
BiNode* create(string &s, int &pos);//构造节点
public:
BiTree() { root = NULL;height = 0; }//构造函数,根初始化为空,高度初始化为0
void createBiTree(string s);
}
根据前序遍历构造二叉树的函数为:
BiNode * BiTree::create(string &s, int &pos)//输入的是一个string,以该string的第pos个字符string[pos]的值作为data,构建一个节点
{
++pos;//pos的初始值为-1,所以要先递增;这里的pos必须是引用类型,否则无法递增
BiNode * t;
if ((unsigned) pos >= s.size())//如果pos越界,返回NULL
return NULL;
else
{
if (s[pos] == '#')
t = NULL;//该节点为空节点
else //其他情况,非空节点
{
t = new BiNode;
t->data = s[pos];//用s[pos]作为s的data
t->lchild = create(s, pos);//递归构造左孩子
if(t->lchild) t->lchild->parent = &t;
t->rchild = create(s, pos);//递归构造右孩子;注意此处是根据前序遍历VLR构造二叉树;注意递归的顺序
if (t->rchild) t->rchild->parent = &t;
}
return t;
}
}
///按照前序遍历序列创建二叉树,调用上面的create函数
void BiTree::createBiTree(string s)
{
int pos = -1;
root = create(s, pos);//返回的是树的根节点
root->parent = NULL;
}
原有的类BiNode中只定义了左右孩子,parent是我自己加入的。编译后提示parent访问权限错误,请问该如何在构造二叉树的时候就确实好父子关系?也就是可以对任意节点调用parent。
难道要用二级指针,把parent声明为BiNode **parent吗?麻烦给个思路
#C/C++#
