二叉树-详解二叉排序树

旧城等待， 2022-05-17 01:18 262阅读 0赞

二叉搜索树

首先二叉排序树也是一棵二叉树，所谓二叉树，就是“任何节点最多只允许两个子节点”，这两个子节点称为左右子节点。如下便是一个二叉树。

![这里写图片描述][20161012223249365]

### **1、二叉排序树性质：** ###

1、就是若它的左子树不空，则左子树上所有节点的值均小于它的根节点的值；  
2、若它的右子树不空，则右子树上所有节点的值均大于其根节点的值。  
3、换句话说就是：任何节点的键值一定大于其左子树中的每一个节点的键值，并小于其右子树中的每一个节点的键值。  
如下便是一颗二叉排序树：

![这里写图片描述][20161119134611348]

eg：[https://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Contest/contestproblem/cid/2563/pid/3373][https_acm.sdut.edu.cn_onlinejudge2_index.php_Home_Contest_contestproblem_cid_2563_pid_3373]

#include<bits/stdc++.h>
    using namespace std;
    typedef struct tree
    {
        int data;
        tree *lc,*rc;
    }*bitree;
    void create(bitree &root,int n)
    {
        if(!root)
        {
            root=new tree;
            root->data=n;
            root->lc=root->rc=NULL;
        }
        else
        {
            if(n>root->data)
                create(root->rc,n);
            else
                create(root->lc,n);
        }
    }
    int compare(bitree &r1,bitree &r2)
    {
        if(!r1&&!r2)
            return 1;
        else if(r1&&r2)
        {
            if(r1->data==r2->data)
                return (compare(r1->lc,r2->lc)&&compare(r1->rc,r2->rc));
        }
        return 0;
    }
    int main()
    {
        int m,t,k,n,f;
        while(cin>>m>>t)
        {
            if(m==0)
                break;
            bitree root=NULL;
            k=m;
            while(k--)
            {
                cin>>n;
                create(root,n);
            }
            while(t--)
            {
                bitree r=NULL;
                k=m;
                while(k--)
                {
                    cin>>n;
                    create(r,n);
                }
                if(compare(root,r))
                    cout<<"Yes"<<endl;
                else
                    cout<<"No"<<endl;
            }
        }
        return 0;

[20161012223249365]: /images/20220517/681fbf7d43564742837653c5ece12fa7.png
[20161119134611348]: /images/20220517/98d0760a30e34240beca2f9ebcc4a775.png
[https_acm.sdut.edu.cn_onlinejudge2_index.php_Home_Contest_contestproblem_cid_2563_pid_3373]: https://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Contest/contestproblem/cid/2563/pid/3373