设计一个算法，对于给定的二叉排序树中任意结点p，找出p结点中序前驱和中序后继结点。

Question

设计一个算法，对于给定的二叉排序树中任意结点p，找出p结点中序前驱和中序后继结点。

注：根据关键字序列 a[]={25,18,46,2,53,39,32,4,74,67,60,11} 构建二叉排序树；再进行结点查找；最后输出运行截图中应包含p结点和中序前驱、中序后继结点。

Answer 1

  //遍历  中序
void print1(struct node*root,int data)
{
     struct node*a[20];    //先定义两个结构体数组 
     struct node*a1[20];    //第一个结构体数组用 出入栈操作   第二个来记录 
     struct node*pnode=root;   
     int i=-1;
     int t=0;
     while(pnode || i!=-1)
     {
     	while(pnode)     //先去树的最左边 
     	{
     		a[++i]=pnode;   //入栈 
     		pnode=pnode->left;
		 }
		 if(i!=-1)
		 {
		 	pnode=a[i--];  //出栈 
            a1[t++]=pnode;   //记录 
		 	pnode=pnode->right;
		 }
	 }
	 for(i=0;i<t;i++)   //遍历第二个 结构体数组 
	 {
	 	if(a1[i]->data==data)   //当结构体数组的数据和 输入的数据相同时 
	 	{
	 		if(i==0)     //i=0 就是在第一个的位置 
	 		{
	 			printf("中序的前面:NULL\n中序的后面:%d",a1[i+1]->data);
	 			return;
			}
			else if(i==t-1)   //在最后一个位置 
			{
				printf("中序的前面:%d\n中序的后面:NULL",a1[i-1]->data);
				return;
			}      //在中间时 
	 		printf("中序的前面:%d\n中序的后面:%d",a1[i-1]->data,a1[i+1]->data);
	 		return ;
		 }
	 }
	 printf("没有这个值\n");  //如果循环结束 说明没有找到 
	 return; 
	 
 }