小白专场:是否同一棵二叉搜索树- C实现(3小节共22:41)


#include <iostream>
#include <cstdlib>

using namespace std;

typedef struct _node {int v;_node* left;_node* right;int flag;} Node;
Node* newNode(int v);
Node* insert(Node* p, int v);
Node* maketree(int n);
void freetree(Node* p);
void reset(Node* p);
int judge(Node* tree, int n);
int check(Node* p, int v);

int main()
{
    int n, l;
    cin >> n;
    Node* tree;
    while ( n ) {
        cin >> l;
        tree = maketree(n);
        for ( int i=0; i<l; i++ ) {
            //cout << tree->v ;
            if ( judge(tree,n) ) cout << "Yes\n";
            else cout << "No\n";
            reset(tree); 
        }
        freetree(tree);
        cin >> n;
    } 
    return 0;
}

void freetree(Node* p)
{
    if ( p->left ) freetree(p->left);
    if ( p->right ) freetree(p->right);
    free(p);
}

void reset(Node* p)
{
    if ( p->left ) reset(p->left);
    if ( p->right ) reset(p->right);
    p->flag = 0;
}

int judge(Node* tree, int n)
{
    int v, flag = 0;
    cin >> v;
    if ( v==tree->v ) tree->flag = 1;
    else flag = 1;
    for ( int i=1; i<n; i++ ) {
        cin >> v;
        if ( !flag && !check(tree,v) ) flag = 1;
    }
    if ( flag ) return 0;
    else return 1;
}

int check(Node* p, int v)
{
    static int cnt = 1, cmt = -1;
    if( p->flag ) {
        //cout << cnt++;
        if ( p->v>v ) return check(p->left,v);
        else if ( p->v<v ) return check(p->right,v);
        else return 0;
    } else {
        //cout << cmt--;
        if ( p->v == v ) {
            p->flag = 1;
            return 1;
        } else return 0;
    }
}

Node* maketree(int n)
{
    int v;
    cin >> v;
    Node* tree = newNode(v);
    for ( int i=1; i<n; i++ ) {
        cin >> v;
        tree = insert(tree,v);
    }
    
    return tree;
}

Node* insert(Node* p, int v)
{
    static int m = 0;
    //cout << m++;
    if ( !p ) p = newNode(v);
    else {
        if ( p->v>v ) p->left = insert(p->left,v);
        else p->right = insert(p->right,v);
    }
    return p;
}

Node* newNode(int v)
{
    Node* p = (Node*)malloc(sizeof(Node));
    p->left = p->right = NULL;
    p->flag = 0;
    p->v = v;
    return p;
}
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容