|
笔者查阅了网上关于二叉树寻找根结点的算法，众说纷纭，有：在节点结构体中加一条指向父节点的指针；非递归遍历树的方式寻找父节点；直接利用树的递归遍历，打印输出父节点…… 笔者认为添加父节点指针的方法，不能很好地体现树的逻辑结构。树的结构体（特指二叉树的存储结构）已经很成熟而且近乎约定俗成了，再重新添加一个指针，很多关于二叉树的基本操作都要重新变化，实在繁琐。所以本文直接利用树的递归遍历方式寻找树的根结点，因为树的定义中本就体现了递归的特点，所以大多数关于树的操作，递归的方法都可有效实现，而且代码可读性强。此外，对于非递归方式的解法，本文不再赘述，请读者自便。 *另：本文只提供一种思路，并不是万能模板，具体问题还需结合实际情况决定！
【问题描述】构造一棵二叉排序树（也叫二叉查找树），可以是一棵空树。 二叉排序树定义： 1.若左子树非空，则左子树上所有关键字值均不大于根结点的关键字值； 2.若右子树非空，则右子树上所有关键字值均不小于根结点的关键字值； 3.左、右子树本身也是一棵二叉排序树。 现在给你N个关键字值各不相同的结点，要求你按顺序插入一个初始为空树的二叉排序树中，每次插入成功后，求相应的父节点的关键字值。如果没有父亲节点，则输出-1。 input： 第一行，一个数字N(Ndata=x;
return T;
}
else if(x < T->data){
T->lchild=Insert(T->lchild,x);
}
else if(x > T->data){
T->rchild=Insert(T->rchild,x);
}
return T;
}
/*遍历一棵树找到各结点的父节点--先序遍历模型，注意遍历孩子节点的条件：孩子非空*/
void findParent(Node *T,int x){
if(!T) return;
if(T->lchild!=NULL && T->lchild->data==x) // 左孩子非空才可遍历，否则递归边界出错
printf("%d的父节点是：%d\n",x,T->data);
if(T->rchild!=NULL && T->rchild->data==x)
printf("%d的父节点是：%d\n",x,T->data);
if(T->lchild)
findParent(T->lchild,x);
if(T->rchild)
findParent(T->rchild,x);
return;
}
int main(){
int n;
while(scanf("%d",&n)!=EOF){
loc=0;
Node *T=NULL; // 建立一个根结点
for(int i=0;i |