数据结构与算法-7-4 是否同一棵二叉搜索树

给定一个插入序列就可以唯一确定一棵二叉搜索树。然而，一棵给定的二叉搜索树却可以由多种不同的插入序列得到。例如分别按照序列{2, 1, 3}和{2, 3, 1}插入初始为空的二叉搜索树，都得到一样的结果。于是对于输入的各种插入序列，你需要判断它们是否能生成一样的二叉搜索树。

输入格式:

输入包含若干组测试数据。每组数据的第1行给出两个正整数$N$ ($\le 10$)和$L$，分别是每个序列插入元素的个数和需要检查的序列个数。第2行给出$N$个以空格分隔的正整数，作为初始插入序列。最后$L$行，每行给出$N$个插入的元素，属于$L$个需要检查的序列。

简单起见，我们保证每个插入序列都是1到$N$的一个排列。当读到$N$为0时，标志输入结束，这组数据不要处理。

输出格式:

对每一组需要检查的序列，如果其生成的二叉搜索树跟对应的初始序列生成的一样，输出“Yes”，否则输出“No”。

输入样例:

4 2
3 1 4 2
3 4 1 2
3 2 4 1
2 1
2 1
1 2
0

输出样例:

Yes
No
No




二叉搜索树的插入操作看这里：https://www.mmuaa.com/post-190.html

判断两个二叉树是否完全相同，我们可以使用递归来判断，先如果两个二叉树的节点都是NULL，那么一定是相同的。如果其中一个是NULL，另一个不是NULL，则一定是不同的。如果两个左右子树不同，二叉树也一定是不同的。如果二叉树的顶点数字不同，二叉树也一定是不同的。如果以上情况都没有，二叉树一定是相同的。

写成程序语言就是：

bool bt_is_equal(node* root1, node* root2){
    if(root1 == NULL && root2 == NULL) 
        return true;
    if( (root1 == NULL && root2 != NULL) || (root2 == NULL && root1 != NULL) ) 
        return false;
    if(root1->root != root2->root)
        return false;
    if( !bt_is_equal(root1->lchild, root2->lchild) || \
        !bt_is_equal(root1->rchild, root2->rchild))
        return false;
    return true;
}

整个程序就是：

#include <iostream>
using namespace std;

typedef struct _node{
    _node *lchild, *rchild;
    int root;
} node;

void bst_insert(node* &root, int data){
    if(root == NULL){
        root = new node;
        root->root = data;
        root->lchild = NULL;
        root->rchild = NULL;
    }
    else{
        if(root->root > data)
            bst_insert(root->lchild, data);
        else if(root->root < data)
            bst_insert(root->rchild, data);
        else if(root->root == data)
            return;
    }
    return;
}

bool bt_is_equal(node* root1, node* root2){
    if(root1 == NULL && root2 == NULL) 
        return true;
    if( (root1 == NULL && root2 != NULL) || (root2 == NULL && root1 != NULL) ) 
        return false;
    if(root1->root != root2->root)
        return false;
    if( !bt_is_equal(root1->lchild, root2->lchild) || \
        !bt_is_equal(root1->rchild, root2->rchild))
        return false;
    return true;
}

int main(){
    while(1){
        int N, L;
        cin >> N;
        if(!N) return 0;
        cin >> L;
        //读取原二叉搜索树
        node* T = NULL;
        for(int i = 0; i < N; i++){
            int _;
            cin >> _;
            bst_insert(T, _);
        }
        //检查
        for(int j = 0; j < L; j++){
            //读取要进行检查的二叉搜索树
            node* _T = NULL;
            for(int i = 0; i < N; i++){
                int _;
                cin >> _;
                bst_insert(_T, _);
            }
            //进行检查
            if( bt_is_equal(T, _T) )
                cout << "Yes" << endl;
            else cout << "No" << endl;
        }
    }
    return 0;
}