数据结构OJ实验13-动态查找

A. DS二叉排序树之创建和插入

题目描述

给出一个数据序列，建立二叉排序树，并实现插入功能。

在建立和插入操作后，都输出二叉树的先序遍历结果i

输入

第1行输入n，表示序列包含n个数据

第2行输入n个数据，都是自然数且互不相同，数据之间用空格隔开

第3行输入m，表示要插入m个数据

输入m行，每行一个要插入的数据，都是自然数且和前面的数据不等

输出

第一行输出一开始构建的二叉排序树的先序遍历结果

从第二行起，输出m行，每行输出插入一个数据到二叉排序树后的先序遍历结果

每行输出的遍历结果中，每个数据后面都带一个空格，最后一个数据也带。

样例查看模式?

正常显示查看格式

输入样例1?

6\n
22?33?55?66?11?44\n
3\n
77\n
50\n
10\n

输出样例1

22?11?33?55?44?66?\n
22?11?33?55?44?66?77?\n
22?11?33?55?44?50?66?77?\n
22?11?10?33?55?44?50?66?77?\n

输入样例2?

6\n
33?55?22?66?11?44\n
3\n
25\n
88\n
50\n
\n

输出样例2

33?22?11?55?44?66?\n
33?22?11?25?55?44?66?\n
33?22?11?25?55?44?66?88?\n
33?22?11?25?55?44?50?66?88?\n

AC代码

#include<bits/stdc++.h>
using namespace std;
struct node
{
    int data;
    node *l;
    node *r;
    node(int d=0,node *ll=NULL,node *rr=NULL):
    data(d),l(ll),r(rr){}
};
class tree
{
    node *root;
    void insert_node(node *&root,int d)
    {
        if(!root)
        {
            root=new node(d);
            return;
        }
        if(root->data==d)
        {
            return;
        }
        else if(root->data>d)
        {
            insert_node(root->l,d);
        }
        else
        {
            insert_node(root->r,d);
        }
    }
    void delete_node(node*n)
    {
        if(!n)
        {
            return;
        }
        delete(n->l);
        delete(n->r);
        delete n;
    }
    void print(node*n)
    {
        if(!n)return;
        cout<<n->data<<" ";
        print(n->l);
        print(n->r);
    }
public:
    tree(){root=NULL;}
    ~tree(){delete_node(root);}
    void create(int x)
    {
        insert_node(root,x);
    }
    void printe()
    {
        print(root);
        cout<<endl;
    }
};
int main()
{
    int n;
    cin>>n;
    tree b;
    for(int i=0;i<n;i++)
    {
        int x;
        cin>>x;
        b.create(x);
    }
    b.printe();
    int m;
    cin>>m;
    for(int i=0;i<m;i++)
    {
        int x;
        cin>>x;
        b.create(x);
        b.printe();
    }
    return 0;
}

B. DS二叉排序树之查找

题目描述

给出一个数据序列，建立二叉排序树，并实现查找功能

输入

第1行输入n，表示首个序列包含n个数据

第2行输入n个数据，都是自然数且互不相同，数据之间用空格隔开

第3行输入m，表示要查找m个数据

接着输入m行，每行一个要查找的数据，都是自然数

以此类推输入下一个示例

输出

第一行输出有序的数据序列，对二叉排序树进行中序遍历可以得到

从第二行起，输出查找结果，如果查找成功输出查找次数，如果查找失败输出-1

样例查看模式?

正常显示查看格式

输入样例1?

6\n
22?33?55?66?11?44\n
7\n
11\n
22\n
33\n
44\n
55\n
66\n
77\n

输出样例1

11?22?33?44?55?66?\n
2\n
1\n
2\n
4\n
3\n
4\n
-1\n

输入样例2?

6\n
33?22?55?11?66?44\n
4\n
88\n
11\n
44\n
66\n

输出样例2

11?22?33?44?55?66?\n
-1\n
3\n
3\n
3\n

AC代码

#include<bits/stdc++.h>
using namespace std;
struct node
{
    int data;
    node* l;
    node* r;
    node(int d = 0, node* ll = NULL, node* rr = NULL) :
        data(d), l(ll), r(rr) {}
};
class tree
{
    node* root;
    int cnt;
    void insert_node(node*& root, int d)
    {
        if (!root)
        {
            root = new node(d);
            return;
        }
        if (root->data == d)
        {
            return;
        }
        else if (root->data > d)
        {
            insert_node(root->l, d);
        }
        else
        {
            insert_node(root->r, d);
        }
    }
    void delete_node(node* n)
    {
        if (!n)
        {
            return;
        }
        delete(n->l);
        delete(n->r);
        delete n;
    }
    void print(node* n)
    {
        if (!n)return;
        print(n->l);
        cout << n->data << " ";
        print(n->r);
    }
public:
    tree() { root = NULL,cnt=0; }
    ~tree() { delete_node(root); }
    void create(int x)
    {
        insert_node(root, x);
    }
    void printe()
    {
        print(root);
        cout << endl;
    }
    int find(int d)
    {
        int cnt = 0;
        node* p = root;
        while (p)//用while
        {
            cnt++;
            if (p->data == d)
            {
                return cnt;
            }
            else if (p->data > d)
            {
                p = p->l;
            }
            else
            {
                p = p->r;
            }
        }
        return -1;
    }
};
int main()
{
    int n;
    cin >> n;
    tree b;
    for (int i = 0; i < n; i++)
    {
        int x;
        cin >> x;
        b.create(x);
    }
    b.printe();
    int m;
    cin >> m;
    for (int i = 0; i < m; i++)
    {
        int x;
        cin >> x;
        cout << b.find(x) << endl;
    }
    return 0;
}

C. DS二叉排序树之删除

题目描述

给出一个数据序列，建立二叉排序树，并实现删除功能

对二叉排序树进行中序遍历，可以得到有序的数据序列

输入

第一行输入t，表示有t个数据序列

第二行输入n，表示首个序列包含n个数据

第三行输入n个数据，都是自然数且互不相同，数据之间用空格隔开

第四行输入m，表示要删除m个数据

从第五行起，输入m行，每行一个要删除的数据，都是自然数

以此类推输入下一个示例

输出

第一行输出有序的数据序列，对二叉排序树进行中序遍历可以得到

从第二行起，输出删除第m个数据后的有序序列，输出m行

以此类推输出下一个示例的结果

样例查看模式?

正常显示查看格式

输入样例1?

1\n
6\n
22?33?55?66?11?44\n
3\n
66\n
22\n
77\n

输出样例1

11?22?33?44?55?66?\n
11?22?33?44?55?\n
11?33?44?55?\n
11?33?44?55?\n

提示

当删除数据不在序列中，那么删除操作等于不执行，所以输出序列不变化

AC代码

#include<bits/stdc++.h>
using namespace std;
struct node
{
    int data;
    node *l;
    node *r;
    node(int d=0,node *ll=NULL,node *rr=NULL):
    data(d),l(ll),r(rr){}
};
class tree
{
    node *root;
    void insert_node(node *&root,int d)
    {
        if(!root)
        {
            root=new node(d);
            return;
        }
        if(root->data==d)
        {
            return;
        }
        else if(root->data>d)
        {
            insert_node(root->l,d);
        }
        else
        {
            insert_node(root->r,d);
        }
    }
    void delete_node(node*n)
    {
        if(!n)
        {
            return;
        }
        delete(n->l);
        delete(n->r);
        delete n;
    }
    void print(node*n)
    {
        if(!n)return;
        print(n->l);
        cout<<n->data<<" ";
        print(n->r);
    }
    void cut(node *&n,int x)
    {
        if(!n)
        {
           return;
        }
        if(n->data>x)
        {
            cut(n->l,x);
            return;
        }
        if(n->data<x)
        {
            cut(n->r,x);
            return;
        }
        //n->data==x;
        if(n->r&&n->l)
        {
            node *p=n->l;
            while(p->r)
            {
                p=p->r;
            }
            n->data=p->data;//n的数据为最右最下那个数据
            cut(n->l,p->data);
            return;
        }
        node *p=n;
        if(n->l==NULL)
        {
            n=n->r;
        }
        else if(n->r==NULL)
        {
            n=n->l;
        }
        delete p;
    }
public:
    tree(){root=NULL;}
    ~tree(){delete_node(root);}
    void create(int x)
    {
        insert_node(root,x);
    }
    void printe()
    {
        print(root);
        cout<<endl;
    }
    int find(int d)
    {
        int cnt=0;
        node *p=root;
        while(p)
        {
            cnt++;
            if(p->data==d)
            {
                return cnt;
            }
            else if(p->data>d)
            {
                p=p->l;
            }
            else
            {
                p=p->r;
            }
        }
        return -1;
    }
    void del(int x)
    {
        cut(root,x);
    }
};
int main()
{
    int t;
    cin>>t;
    while(t--){
        int n;
    cin>>n;
    tree b;
    for(int i=0;i<n;i++)
    {
        int x;
        cin>>x;
        b.create(x);
    }
    b.printe();
    int m;
    cin>>m;
    for(int i=0;i<m;i++)
    {
        int x;
        cin>>x;
        b.del(x);
        b.printe();
    }
    }
    return 0;
}

D. DS查找—二叉树平衡因子

题目描述

二叉树用数组存储，将二叉树的结点数据依次自上而下,自左至右存储到数组中，一般二叉树与完全二叉树对比，比完全二叉树缺少的结点在数组中用0来表示。

计算二叉树每个结点的平衡因子，并按后序遍历的顺序输出结点的平衡因子。

输入

测试次数t

每组测试数据一行，数组元素个数n，后跟n个字符，二叉树的数组存储。

输出

对每组测试数据，按后序遍历的顺序输出树中结点的平衡因子（测试数据没有空树）

样例查看模式?

正常显示查看格式

输入样例1

2\n
6?ABC00D\n
24?ABCD0EF0000H00000000000I\n
\n
\n

输出样例1

B?0\n
D?0\n
C?1\n
A?-1\n
D?0\n
B?1\n
I?0\n
H?1\n
E?2\n
F?0\n
C?2\n
A?-2\n

AC代码

#include<bits/stdc++.h>
using namespace std;
int geth(string &tree,int idx)
{
    if(tree[idx]=='0')
    return 0;
    return max(geth(tree,2*idx+1),geth(tree,2*idx+2))+1;
}
int getbalance(string &tree,int idx)
{
    return geth(tree,2*idx+1)-geth(tree,2*idx+2);
}
void show(string &tree,int idx)
{
    if(tree[idx]=='0')
    return;
    show(tree,idx*2+1);
    show(tree,2*idx+2);
    cout<<tree[idx]<<" "<<getbalance(tree,idx)<<endl;
}
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        string tree;
        cin>>n>>tree;
        tree.append(2*n,'0');
        show(tree,0);
    }
    return 0;
}

E. 搜索树判断

题目描述

对于二叉搜索树，我们规定任一结点的左子树仅包含严格小于该结点的键值，而其右子树包含大于或等于该结点的键值。如果我们交换每个节点的左子树和右子树，得到的树叫做镜像二叉搜索树。

现在我们给出一个整数键值序列，请编写程序判断该序列是否为某棵二叉搜索树或某镜像二叉搜索树的前序遍历序列，如果是，则输出对应二叉树的后序遍历序列。

输入

输入的第一行包含一个正整数N（≤1000），第二行包含N个整数，为给出的整数键值序列，数字间以空格分隔。

输出

输出的第一行首先给出判断结果，如果输入的序列是某棵二叉搜索树或某镜像二叉搜索树的前序遍历序列，则输出YES，否侧输出NO。如果判断结果是YES，下一行输出对应二叉树的后序遍历序列。数字间以空格分隔，但行尾不能有多余的空格。

样例查看模式?

正常显示查看格式

输入样例1?

7\n
8?6?5?7?10?8?11

输出样例1

YES\n
5?7?6?8?11?10?8

AC代码

#include<bits/stdc++.h>
using namespace std;
struct node
{
    int data;
    node *l;
    node *r;
    node(int d=0,node *ll=NULL,node *rr=NULL):
    data(d),l(ll),r(rr){}
};
class tree
{
    node *root;
    vector<int>b;
    void insert_node(node *&root,int d)
    {
        if(!root)
        {
            root=new node(d);
            return;
        }
        else if(root->data>d)
        {
            insert_node(root->l,d);
        }
        else
        {
            insert_node(root->r,d);
        }
    }
    void delete_node(node*n)
    {
        if(!n)
        {
            return;
        }
        delete(n->l);
        delete(n->r);
        delete n;
    }
    void print(node*n)
    {
        if(!n)return;
        b.push_back(n->data);
        print(n->l);
        print(n->r);
    }
    void post(node *n)
    {
        if(!n)return;
        post(n->l);
        post(n->r);
        b.push_back(n->data);//b放后序列
    }
    void cut(node *&n,int x)
    {
        if(!n)
        {
           return;
        }
        if(n->data>x)
        {
            cut(n->l,x);
            return;
        }
        if(n->data<x)
        {
            cut(n->r,x);
            return;
        }
        //n->data==x;
        if(n->r&&n->l)
        {
            node *p=n->l;
            while(p->r)
            {
                p=p->r;
            }
            n->data=p->data;//n的数据为最右最下那个数据
            cut(n->l,p->data);
            return;
        }
        node *p=n;
        if(n->l==NULL)
        {
            n=n->r;
        }
        else if(n->r==NULL)
        {
            n=n->l;
        }
        delete p;
    }
public:
    tree(){root=NULL;}
    ~tree(){delete_node(root),b.clear();}
    void create(int x)
    {
        insert_node(root,x);
    }
    void printe()
    {
        print(root);
    }
    int find(int d)
    {
        int cnt=0;
        node *p=root;
        while(p)
        {
            cnt++;
            if(p->data==d)
            {
                return cnt;
            }
            else if(p->data>d)
            {
                p=p->l;
            }
            else
            {
                p=p->r;
            }
        }
        return -1;
    }
    void del(int x)
    {
        cut(root,x);
    }
    bool check(vector<int> a)
    {
        if(a.size()!=b.size())return 0;
        for(int i=0;i<b.size()&&i<a.size();i++)
        {
             if(a[i]!=b[i])return 0;
        }
        return 1;
    }
    void postshow()
    {
        b.clear();
        post(root);
        for(int i=0;i<b.size();i++)
        {
            if(i)
            cout<<" "<<b[i];
            else cout<<b[i];
        }
        cout<<endl;
    }
};
int main()
{
    int n;
    cin>>n;
    tree b;
    vector<int>a;
    for(int i=0;i<n;i++)
    {
        int x;
        cin>>x;
        b.create(x);
        a.push_back(x);
    }
    b.printe();
    if(b.check(a)==1)
    {
        cout<<"YES"<<endl;
        b.postshow();
    }
    else
    {
        cout<<"NO"<<endl;
    }
    return 0;
}

F. 二叉搜索树的最近公共祖先

题目描述

给定一棵二叉搜索树的先序遍历序列，要求你找出任意两结点的最近公共祖先结点（简称 LCA）。

输入

输入的第一行给出两个正整数：待查询的结点对数 M（≤?1 000）和二叉搜索树中结点个数 N（≤?10 000）。随后一行给出 N 个不同的整数，为二叉搜索树的先序遍历序列。最后 M 行，每行给出一对整数键值 U 和 V。所有键值都在整型int范围内。

输出

对每一对给定的 U 和 V，如果找到?A?是它们的最近公共祖先结点的键值，则在一行中输出?LCA of U and V is A.。但如果 U 和 V 中的一个结点是另一个结点的祖先，则在一行中输出?X is an ancestor of Y.，其中?X?是那个祖先结点的键值，Y?是另一个键值。如果 二叉搜索树中找不到以 U 或 V 为键值的结点，则输出?ERROR: U is not found.?或者?ERROR: V is not found.，或者?ERROR: U and V are not found.。

样例查看模式?

正常显示查看格式

输入样例1

6?8\n
6?3?1?2?5?4?8?7\n
2?5\n
8?7\n
1?9\n
12?-3\n
0?8\n
99?99

输出样例1

LCA?of?2?and?5?is?3.\n
8?is?an?ancestor?of?7.\n
ERROR:?9?is?not?found.\n
ERROR:?12?and?-3?are?not?found.\n
ERROR:?0?is?not?found.\n
ERROR:?99?and?99?are?not?found.

AC代码

#include<bits/stdc++.h>
using namespace std;
struct node
{
    int data;
    node *l;
    node *r;
    node(int d=0,node *ll=NULL,node *rr=NULL):
    data(d),l(ll),r(rr){}
};
class tree
{
    node *root;
    string ss;
    void insert_node(node *&root,int d)
    {
        if(!root)
        {
            root=new node(d);
            return;
        }
        if(root->data==d)
        {
            return;
        }
        else if(root->data>d)
        {
            insert_node(root->l,d);
        }
        else
        {
            insert_node(root->r,d);
        }
    }
    void delete_node(node*n)
    {
        if(!n)
        {
            return;
        }
        delete(n->l);
        delete(n->r);
        delete n;
    }
    node* find(int d)
    {
        int cnt=0;
        node *p=root;
        while(p)
        {
            cnt++;
            if(p->data==d)
            {
                return p;
            }
            else if(p->data>d)
            {
                p=p->l;
            }
            else
            {
                p=p->r;
            }
        }
        return NULL;
    }
public:
    tree(){root=NULL;}
    ~tree(){delete_node(root);}
    void create(int x)
    {
        insert_node(root,x);
    }
    int check(int d)
    {
        node *p=find(d);
        if(p==NULL)return -1;
        return 1;
    }
    node* lca(node* root, node* p, node* q) 
    {
        if(!root) return NULL;
        if(root->data > p->data && root->data > q->data)
        {
            return lca(root->l, p, q);
        }
        else if(root->data < p->data && root->data < q->data)
        {
            return lca(root->r, p, q);
        }
        return root;
    }
    int pp(int x,int y)
    {
        node *p=find(x);
        node *q=find(y);
        if((p->l&&p->l->data==y)||(p->r&&p->r->data==y))
        {
            printf("%d is an ancestor of %d.\n",x,y);
            return -2;
        }
        if((q->l&&q->l->data==x)||(q->r&&q->r->data==x))
        {
            printf("%d is an ancestor of %d.\n",y,x);
            return -2;
        }
        int res=lca(root,p,q)->data;
        return res;
    }
};
int main()
{
    int m,n;
    cin>>m>>n;
    tree b;
    for(int i=0;i<n;i++)
    {
        int x;
        cin>>x;
        b.create(x);
    }
    for(int i=0;i<m;i++)
    {
        int x,y;
        cin>>x>>y;
        int idxa=b.check(x);
        int idxb=b.check(y);
        if(idxa==-1&&idxb==-1)
        {
            printf("ERROR: %d and %d are not found.\n",x,y);
        }
        else if(idxa==-1)
        {
            printf("ERROR: %d is not found.\n",x);
        }
        else if(idxb==-1)
        {
            printf("ERROR: %d is not found.\n",y);
        }
        else
        {
            int kk=b.pp(x,y);
            if(kk!=-2)
            printf("LCA of %d and %d is %d.\n",x,y,kk);
        }
    }
    return 0;
}