BJFU_数据结构习题_289二叉排序树的限定条件下的数据输出

小咪咪 2023-05-30 06:21 12阅读 0赞

欢迎登录北京林业大学OJ系统  
[http://www.bjfuacm.com][http_www.bjfuacm.com]

### 289二叉排序树的限定条件下的数据输出 ###

**描述**  
已知二叉排序树采用二叉链表存储结构，根结点的指针为T,链结点的结构为(lchild,data,rchild),其中lchild、rchild分别指向该结点左，右孩子的指针，data域存放结点数据。试编写算法，从小到大输出二叉排序树中所有数值大于等于x的结点的数据。要求先找到第一个满足条件的结点后，再依次输出其他满足条件的结点。  
**输入**  
多组数据，每组三行。第一行为二叉排序树的结点数n。第二行为空格分隔的n个数字，对应二叉排序树中的n个结点。第三行为一个数字x。n=0时输入结束。  
**输出**  
每组数据输出一行。从小到大输出大于等于x的结点数据。每个数据用空格分隔。 输入样例  
**输入样例 1**  
5  
1 5 3 2 4  
3  
9  
1 30 2 15 6 7 3 9 233  
30  
0  
**输出样例 1**  
3 4 5  
30 233

#include<iostream>
    using namespace std;
    int c[100];
    int flag;
    int k;
    typedef struct BSTNode
    {
        
    	int data;
    	struct BSTNode *lchild;
    	struct BSTNode *rchild;
    }BSTNode,*BSTree;
    void Insert(BSTree &T,int e)
    {
        
    	if(!T)
    	{
        
    		T=new BSTNode;
    		T->data=e;
    		T->lchild=NULL;
    		T->rchild=NULL;
    	}
    	else
    	{
        
    		if(e<T->data)
    			Insert(T->lchild,e);
    		else
    			Insert(T->rchild,e);
    	}
    }
    void InOrderTraverse(BSTree T,int n,int key)
    {
        
    	if(T)
    	{
        
    		InOrderTraverse(T->lchild,n,key);
    		c[++k]=T->data;
    		if(c[k]>=key)
    		{
        
    			if(flag==0)
    			{
        
    				cout<<c[k];
    				flag=1;
    			}
    			else
    				cout<<" "<<c[k];
    		}
          	InOrderTraverse(T->rchild,n,key);
    	}
    }
    int main()
    {
        
    	int n,e,key;;
    	while(cin>>n&&n!=0)
    	{
        		
    		BSTree T=NULL;
    		for(int i=0;i<n;i++)
    		{
        
    			cin>>e;
    			Insert(T,e);
    		}
    		cin>>key;
    		flag=0;
    		InOrderTraverse(T,n,key);
    		cout<<endl;
    	}
    	return 0;
    }

[http_www.bjfuacm.com]: http://www.bjfuacm.com