Problem1867--【查找】7-3 二叉排序树的限定条件下的数据输出

1867: 【查找】7-3 二叉排序树的限定条件下的数据输出

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 1  Solved: 1
[Submit] [Status] [Web Board] [Creator:]

Description

已知二叉排序树采用二叉链表存储结构,根结点的指针为T,链结点的结构为(lchild,data,rchild),其中lchild、rchild分别指向该结点左,右孩子的指针,data域存放结点数据。试编写算法,从小到大输出二叉排序树中所有数值大于等于x的结点的数据。要求先找到第一个满足条件的结点后,再依次输出其他满足条件的结点。

Input

多组数据,每组三行。第一行为二叉排序树的结点数n。第二行为空格分隔的n个数字,对应二叉排序树中的n个结点。第三行为一个数字x。n=0时输入结束。

Output

每组数据输出一行。从小到大输出大于等于x的结点数据。每个数据用空格分隔。

Sample Input Copy

5
1 5 3 2 4
3
9
1 30 2 15 6 7 3 9 233
30
0

Sample Output Copy

3 4 5
30 233

HINT

#include<iostream>
using namespace std;
typedef struct BSTNode
{//二叉排序树的二叉链表存储表示
    int data;
    struct BSTNode *lchild,*rchild;
}BSTNode,*BSTree;
int sum;////设一个全局变量sum,为了判断该数据是否为输出的最后一个数
void InsertBST(BSTree &T,int e)
{//当二叉排序树T中不存在关键字等于e的数据元素时,则插入该元素
    /**************begin************/
   
    /**************end************/
}
BSTree CreateBSTree(int n)
{//构建二叉排序树
    BSTree T=NULL;
    int e;
    for(int i=0;i<n;i++)
    {
        cin>>e;
        InsertBST(T,e);
    }
    return T;
}
void InOrderTraverse(BSTree T,int x)
{//中序遍历二叉树T的递归算法
    if(T==NULL) return;   //空树
    else
    {
        InOrderTraverse(T->lchild,x);//递归遍历左子树
        sum--;         //每次遍历时sum减1
        if(T->data>=x)
        {                               //输出二叉排序树中所有数值大于等于x的结点的数据
            cout<<T->data;              //先输出数据
            if(sum==0) cout<<endl;    //如果是最后一个元素,换行
            else cout<<" ";           //非末位元素,输出空格
        }
        InOrderTraverse(T->rchild,x);//递归遍历右子树
    }
}
int main()
{
    int n,x;        //二叉排序树的结点数n,数字x
    while(cin>>n)
    {
        if(n==0) break;
        BSTree T=NULL;
        T=CreateBSTree(n);
        cin>>x;          //输入数字x
        sum=n;          //结点数n赋给sum
        InOrderTraverse(T,x);
    }
    return 0;
}

Source/Category