3月21日OJ刷题_设有一二叉树采用二叉链存储,根结点指针为t,试找到一个结点值为item的结点

基于递归的折半查找

描述

请编写一个递归的折半查找算法，查找给定有序数组中的某一元素。

输入

多组数据，每组数据有三行。第一行为数组长度n，第二行为n个递增排列的数字，第三行为需要查找的数字k。当n=0时输入结束。

输出

每组数据输出一行，如果可以找到数字，则输出“YES”，否则输出“NO”。

输入样例 1 

5
1 4 6 7 8
6
6
1 2 5 7 9 100
8
0

输出样例 1

YES
NO

#include<bits/stdc++.h>
using namespace std;
 
void Find(int a[],int k,int low,int high)
{
    if(high<low)
    {
        cout<<"NO"<<endl;
        return;
    }
    int mid=(low+high)/2;
    if(a[mid]==k)
    {
        cout<<"YES"<<endl;
        return;
    }
    else
    {
        if(k<a[mid])
            Find(a,k,low,mid-1);
        else
            Find(a,k,mid+1,high);
    }
}
int main()
{
    int a[100];
    int n;
    while(cin>>n&&n!=0)
    {
        for(int i=0;i<n;i++)
        {
            cin>>a[i];
        }
        int k;
        cin>>k;
        Find(a,k,0,n-1);
    }
}

二叉排序树的判定

描述

假设二叉树每个结点的元素均为一个单字符，根据给定的字符序列按照先序遍历的顺序递归创建该树的二叉链表，然后判断该二叉树是否为二叉排序树。

输入

多组数据，每组数据有一行。每行为一个二叉树对应的前序序列（其中‘#’表示空树）。当序列为“#”时，输入结束。

输出

每组数据输出1行，若此二叉树为二叉排序树则输出“YES”，否则输出“NO”。

输入样例 1 

ba##c##
ca##b##
#

输出样例 1

YES
NO

 

#include<bits/stdc++.h>
using namespace std;
typedef struct BiNode
{
    char data;
    BiNode *lchild,*rchild;
}BiNode,*BiTree;
 
void Create(BiTree &bt,char s[],int &i)
{
    if(s[i]=='#')
    {
        bt=NULL;
    }
    else
    {
        bt=new BiNode;
        bt->data=s[i];
        Create(bt->lchild,s,++i);
        Create(bt->rchild,s,++i);
    }
}
int flag;
int t;
void Judge(BiTree bt)
{
    if(bt)
    {
        Judge(bt->lchild);
        if(t>bt->data)
        {
            flag=0;
            return;
        }
      else
      {
        t=bt->data;
      }
        Judge(bt->rchild);
    }
}
void PreOrder(BiTree bt)
{
    if(bt!=NULL)
    {
        cout<<bt->data<<" ";
        PreOrder(bt->lchild);
        PreOrder(bt->rchild);
    }
}
int main()
{
    char ch[100];
    while(cin>>ch&&ch[0]!='#')
    {
        BiTree bt;
        int i=-1;
        Create(bt,ch,++i);
        flag=1;
        t=0;
        Judge(bt);
        if(flag)
			cout<<"YES"<<endl;
		else
			cout<<"NO"<<endl;
    }
}

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

描述

已知二叉排序树采用二叉链表存储结构，根结点的指针为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<bits/stdc++.h>
using namespace std;
typedef struct BiNode
{
    int data;
    BiNode *lchild,*rchild;
}BiNode,*BiTree;
 
void Insert(BiTree &bt,int k)
{
    if(bt==NULL)
    {
        bt=new BiNode;
        bt->data=k;
        bt->lchild=NULL;
        bt->rchild=NULL;
    }
    else
    {
        if(k<bt->data)
        {
            Insert(bt->lchild,k);
        }
        else
        {
            Insert(bt->rchild,k);
        }
    }
}
int flag;
void Find(BiTree bt,int x)
{
    if(bt)
    {
        Find(bt->lchild,x);
        if(bt->data>=x)
        {
            if(!flag)
            {
                cout<<bt->data;
                flag=1;
            }
            else
            {
                cout<<" "<<bt->data;
            }
        }
        Find(bt->rchild,x);
    }
}
int main()
{
    int n;
    while(cin>>n&&n!=0)
    {
        int k;
        BiTree bt=NULL;
        for(int i=0;i<n;i++)
        {
            cin>>k;
            Insert(bt,k);
        }
        int x;
        cin>>x;
        flag=0;
        Find(bt,x);
        cout<<endl;
    }
}

基于链地址法的散列表的插入

描述

请写出在散列表中插入关键字为k的一个记录的算法，设散列函数为H,H(key)=key%13，解决冲突的方法为链地址法。

输入

多组数据，每组三行，第一行为待输入的关键字的个数n，第二行为对应的n个关键字，第三行为需要插入的关键字k。当n=0时输入结束。

输出

每组数据输出用链地址法处理冲突的散列表。

输入样例 1 

5
1 4 2 3 5
6
4
2 5 8 15
18
0

输出样例 1

0
1 1
2 2
3 3
4 4
5 5
6 6
7
8
9
10
11
12
0
1
2 2 15
3
4
5 5 18
6
7
8 8
9
10
11
12

 

#include<bits/stdc++.h>
using namespace std;
typedef struct LNode
{
    int data;
    LNode *next;
}LNode,*LinkList;
 
LinkList H[13];
 
void Hash(int n)
{
    for(int i=0;i<13;i++)
    {
        H[i]=new LNode;
        H[i]->next=NULL;
    }
    int x;
    for(int i=0;i<n;i++)
    {
        cin>>x;
        LNode *p=H[x%13];
        while(p->next)
        {
            p=p->next;
        }
        LNode *s=new LNode;
        s->data=x;
        s->next=NULL;
        p->next=s;
    }
}
 
void Insert()
{
    int x;
    cin>>x;
    LNode *p=H[x%13];
    while(p->next)
    {
        p=p->next;
    }
    LNode *s=new LNode;
    s->data=x;
    s->next=NULL;
    p->next=s;
}
void Print()
{
    for(int i=0;i<13;i++)
    {
        cout<<i;
        LNode *p=H[i]->next;
        while(p)
        {
            cout<<" "<<p->data;
            p=p->next;
        }
        cout<<endl;
    }
}
int main()
{
    int n;
    while(cin>>n&&n!=0)
    {
        Hash(n);
        Insert();
        Print();
    }
}

基于链地址法的散列表的删除

描述

请写出在散列表中删除关键字为k的一个记录的算法，设散列函数为H，H(key)=key%13，解决冲突的方法为链地址法。

输入

多组数据，每组三行，第一行为待输入的关键字的个数n，第二行为对应的n个关键字，第三行为需要删除的关键字k。当n=0时输入结束。

输出

每组数据输出用链地址法处理冲突的散列表。

输入样例 1 

5
1 4 2 3 5
3
4
1 10 14 27
14
0

输出样例 1

0
1 1
2 2
3
4 4
5 5
6
7
8
9
10
11
12
0
1 1 27
2
3
4
5
6
7
8
9
10 10
11
12

 

#include<bits/stdc++.h>
using namespace std;
typedef struct LNode
{
    int data;
    LNode *next;
}LNode,*LinkList;
 
LinkList H[13];
 
void Hash(int n)
{
    for(int i=0;i<13;i++)
    {
        H[i]=new LNode;
        H[i]->next=NULL;
    }
    int x;
    for(int i=0;i<n;i++)
    {
        cin>>x;
        LNode *p=H[x%13];
        while(p->next)
        {
            p=p->next;
        }
        LNode *s=new LNode;
        s->data=x;
        s->next=NULL;
        p->next=s;
    }
}
 
void Delete()
{
    int x;
    cin>>x;
    LNode *p=H[x%13];
    while(p->next)
    {
        if(p->next->data==x)
        {
            p->next=p->next->next;
            break;
        }
        p=p->next;
    }
}
void Print()
{
    for(int i=0;i<13;i++)
    {
        cout<<i;
        LNode *p=H[i]->next;
        while(p)
        {
            cout<<" "<<p->data;
            p=p->next;
        }
        cout<<endl;
    }
}
int main()
{
    int n;
    while(cin>>n&&n!=0)
    {
        Hash(n);
        Delete();
        Print();
    }
}