关于二叉树的问题
现在Parent求双亲函数运行不成功，输出总为‘？’（一个问号）先将全部代码贴出，还需要一个求指定结点到根结点路径的函数，请教高手帮忙#include<iostream.h>
#include<string>
template <class T>
struct BiNode //二叉树的结点结构
{
T data;
BiNode<T> *lchild, *rchild;
};
template <class T>
class BiTree
{
public:
BiNode<T>*p;
T x;
BiTree( ); //构造函数，初始化一棵二叉树，其前序序列由键盘输入
~BiTree(void); //析构函数，释放二叉链表中各结点的存储空间
BiNode<T>* Getroot(); //获得指向根结点的指针
void PreOrder(BiNode<T> *root); //前序遍历二叉树
void InOrder(BiNode<T> *root); //中序遍历二叉树
void PostOrder(BiNode<T> *root); //后序遍历二叉树
void LeverOrder(BiNode<T> *root); //层序遍历二叉树
int Getheight(BiNode<T> *root); //获取树的深度
T Parent(BiNode<T>*root,T x);
private:
BiNode<T> *root; //指向根结点的头指针
BiNode<T> *Creat( ); //有参构造函数调用
void Release(BiNode<T> *root); //析构函数调用
};
template<class T>
BiTree<T>::BiTree( )
{
this->root = Creat( );
}
template<class T>
BiTree<T>::~BiTree(void)
{
Release(root);
}
template<class T>
BiNode<T>* BiTree<T>::Getroot( )
{
return root;
}
template<class T>
void BiTree<T>::PreOrder(BiNode<T> *root)
{
if(root==NULL) return;
else{
cout<<root->data<<" ";
PreOrder(root->lchild);
PreOrder(root->rchild);
}
}
template <class T>
void BiTree<T>::InOrder (BiNode<T> *root)
{
if (root==NULL) return; //递归调用的结束条件
else{
InOrder(root->lchild); //中序递归遍历root的左子树
cout<<root->data<<" "; //访问根结点的数据域
InOrder(root->rchild); //中序递归遍历root的右子树
}
}
template <class T>
void BiTree<T>::PostOrder(BiNode<T> *root)
{
if (root==NULL) return; //递归调用的结束条件
else{
PostOrder(root->lchild); //后序递归遍历root的左子树
PostOrder(root->rchild); //后序递归遍历root的右子树
cout<<root->data<<" "; //访问根结点的数据域
}
}
template <class T>
void BiTree<T>::LeverOrder(BiNode<T> *root)
{
const int MaxSize = 100;
int front = 0;
int rear = 0; //采用顺序队列，并假定不会发生上溢
BiNode<T>* Q[MaxSize];
BiNode<T>* q;
if (root==NULL) return;
else{
Q[rear++] = root;
while (front != rear)
{
q = Q[front++];
cout<<q->data<<" ";
if (q->lchild != NULL) Q[rear++] = q->lchild;
if (q->rchild != NULL) Q[rear++] = q->rchild;
}
}
}
template <class T>
int BiTree<T>::Getheight(BiNode<T> *root)
{
int lh,rh;
if(root==NULL) return 0;
else
{
lh=Getheight(root->lchild);
rh=Getheight(root->rchild);
}
if(lh>rh)
return lh+1;
else
return rh+1;
}
template <class T>
T BiTree<T>::Parent(BiNode<T>*root,T x)
{
if(root)
{
if(root->data==x) return p->data;//返回双亲的值
else
{
p=root;
Parent(root->lchild,x);
Parent(root->rchild,x);
}
}
}
template <class T>
BiNode<T>* BiTree<T>::Creat( )
{
BiNode<T>* root;
T ch;
cout<<"请输入创建一棵二叉树的结点数据"<<endl;
cin>>ch;
if (ch=='#') root = NULL;
else{
root = new BiNode<T>; //生成一个结点
root->data=ch;
root->lchild = Creat( ); //递归建立左子树
root->rchild = Creat( ); //递归建立右子树
}
return root;
}
template<class T>
void BiTree<T>::Release(BiNode<T> *root)
{
if (root != NULL){
Release(root->lchild); //释放左子树
Release(root->rchild); //释放右子树
delete root;
}
}
void main()
{
BiTree<char> bt; //创建一棵树
BiNode<char>* root = bt.Getroot( ); //获取指向根结点的指针
bt.p=root;
cout<<"------前序遍历------ "<<endl;
bt.PreOrder(root);
cout<<endl;
cout<<"------中序遍历------ "<<endl;
bt.InOrder(root);
cout<<endl;
cout<<"------后序遍历------ "<<endl;
bt.PostOrder(root);
cout<<endl;
cout<<"------层序遍历------ "<<endl;
bt.LeverOrder(root);
cout<<endl;
cout<<"树的深度为:"<<endl;
cout<<bt.Getheight(root)<<endl;
cin>>bt.x;
cout<<bt.Parent(root,bt.x)<<endl;
}
