9497 利用递归实现查找中序遍历序列中第i个结点

左手的ㄟ右手 2023-02-16 05:52 15阅读 0赞

时间限制:1000MS 代码长度限制:10KB  
提交次数:815 通过次数:426

题型: 编程题 语言: G++;GCC  
Description  
创建一棵具有若干结点的二叉排序树，对其进行前、中、后序遍历并输出。最后查找中序遍历序列中第i个结点。

\#include “stdio.h”  
\#include “malloc.h”  
\#define TRUE 1  
\#define FALSE 0  
\#define OK 1  
\#define ERROR 0  
\#define INFEASIBLE -1  
\#define OVERFLOW -2  
typedef int Status;

typedef int ElemType;  
typedef struct BiTNode\{  
ElemType data;  
struct BiTNode \*lchild,\*rchild;//左右孩子指针  
\} BiTNode,\*BiTree;

Status InsertBiTree(BiTree &T,int e) //插入新结点  
\{  
if(T==NULL)\{  
T=(BiTNode \*)malloc(sizeof(BiTNode));  
T->data=e;T->lchild=NULL;  
T->rchild=NULL;  
return 1;  
\}  
if(T->data<e)  
InsertBiTree(T->rchild,e);  
else  
InsertBiTree(T->lchild,e);  
return 0;  
\}

Status PrintElement( ElemType e ) \{ // 输出元素e的值  
printf("%d ", e );  
return OK;  
\}// PrintElement

Status PreOrderTraverse( BiTree T, Status(\*Visit)(ElemType) )//前序遍历二叉树  
\{  
if(T==NULL) return 0;  
Visit( T->data );  
PreOrderTraverse(T->lchild,Visit);  
PreOrderTraverse(T->rchild,Visit);  
return OK;  
\} // PreOrderTraverse

Status InOrderTraverse( BiTree T, Status(\*Visit)(ElemType) ) //中序遍历二叉树  
\{  
if(T==NULL) return 0;  
InOrderTraverse(T->lchild,Visit);  
Visit(T->data);  
InOrderTraverse(T->rchild,Visit);  
return 1;  
\} // InOrderTraverse

Status PostOrderTraverse( BiTree T, Status(\*Visit)(ElemType) )//后序遍历二叉树  
\{  
if(T==NULL) return 0;  
PostOrderTraverse(T->lchild,Visit);  
PostOrderTraverse(T->rchild,Visit);  
Visit(T->data);  
return 1;

\} // PostOrderTraverse

BiTNode\* FindNode( BiTree Ta,i) //查找中序遍历序列中第i个结点。  
\{  
//补充内容  
\}

int main() //主函数  
\{  
BiTree T=NULL;  
int i,n,e;  
scanf("%d",&n);//生成二叉排序树Ta  
for(i=0;i<n;i++)\{  
scanf("%d",&e);  
InsertBiTree(T,e);  
\}  
//前、中、后序遍历二叉树  
PreOrderTraverse(T,PrintElement);  
printf("\\n");  
InOrderTraverse(T,PrintElement);  
printf("\\n");  
PostOrderTraverse(T,PrintElement);  
printf("\\n");

scanf("%d",&i);
        
        //补全代码

\}//main

输入格式  
第一行 树的结点个数  
第二行 输入上一行指定的整数  
第三行 输入一个待查找结点序号  
第四行 输入一个待查找结点序号

输出格式  
第一~三行输出前、中、后序遍历二叉树  
第四行 结点值或相应提示  
第五行 结点值或相应提示

输入样例  
5  
50 20 10 80 70  
4  
8

输出样例  
50 20 10 80 70  
10 20 50 70 80  
10 20 70 80 50  
70  
Error

作者 30003021

#include<iostream>
    using namespace std;
    int a[1000],count=1;
    typedef struct node 
    { 
    	int key;
    	struct node *lchild,*rchild;
    }Tree,*PTree;
    void Insert(PTree &T,int e)//插入新节点 
    { 
    	if(!T)
    	{ 
    		T=new Tree;
    		T->key=e;
    		T->lchild=NULL;
    		T->rchild=NULL;
    	}
    	else if(e>T->key)
    	Insert(T->rchild,e);
    	else
    	Insert(T->lchild,e);
    }
    void PreOrder(PTree &T)//先序遍历 
    { 
    	if(T)
    	{ 
    		cout<<T->key<<' ';
    		PreOrder(T->lchild);
    		PreOrder(T->rchild);
    	}
    
    }
    void InOrder(PTree &T)//中序遍历 
    { 
    	if(T)
    	{ 
    		InOrder(T->lchild);
    		cout<<T->key<<' ';
    		InOrder(T->rchild);
    	}
    }
    void LastOrder(PTree &T)//后序遍历 
    { 
    	if(T)
    	{ 
    		LastOrder(T->lchild);
    		LastOrder(T->rchild);
    		cout<<T->key<<' ';
    	}
    }
    void traval(PTree &T)//三种次序遍历 
    { 
    	PreOrder(T);//先序遍历 
    	cout<<endl;
    	InOrder(T);//中序遍历 
    	cout<<endl;
    	LastOrder(T);//后序遍历 
    	cout<<endl;
     }
     void InOrderSearch(PTree &T)//中序遍历查找 
    { 
    	if(T)
    	{ 
    		InOrderSearch(T->lchild);
    		a[count++]=T->key;
    		InOrderSearch(T->rchild);
    	}
    }
    int main()
    { 
    	int n,i,x,lis;
    	PTree T=NULL;
    	cin>>n;
    	for(i=1;i<=n;i++)
    	{ 
    		cin>>x;
    		Insert(T,x);
    	}
    	traval(T);//三种次序遍历树
    	InOrderSearch(T);
    	cin>>lis;
    	if(lis<count)
    	cout<<a[lis]<<endl;
    	else
    	cout<<"Error"<<endl;
    	cin>>lis;
    	if(lis<count)
    	cout<<a[lis]<<endl;
    	else
    	cout<<"Error"<<endl;
    	return 0;
    }