Mki's Blog

数据结构(四):判断是否为同一棵二叉搜索树

题目描述

题目要求

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

输入格式:

输入包含若干组测试数据。每组数据的第1行给出两个正整数N (≤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

思路

吼吼,深刻贯彻落实能偷懒就不好好写原则的我,由于留意到了何老讲的数字顺序判断是否为同一棵搜索二叉树的方法,于是瞬间产生了偷鸡的想法。。

原理.png

偷鸡代码

#include<stdio.h>
#include<stdlib.h>

typedef struct Node* Pnode;
struct Node {
    int value;
    Pnode   Next;
};
typedef Pnode List;

void Print(List p) {                  //打印链表
    List ans;
    ans = p;
    ans = ans->Next;
    while (ans->Next != NULL) {
        if(ans->value==1)
            printf("Yes\n");
        else
            printf("No\n");
        ans = ans->Next;
    }
    if (ans->value == 1)
        printf("Yes\n");
    else
        printf("No\n");

}

List Add(int num) {                    //往链表末尾添加一个节点
    List Node;
    Node = (List)malloc(sizeof(List));
    Node->Next = NULL;
    Node->value = num;
    return Node;
}

int Judge(List p1,List p2) {           //判断大小顺序是否一致
    List L1, L2;
    L1 = p1;
    L2 = p2;
    L1 = L1->Next;                    //习惯链表开头第一个是空节点,这里要比较值所以要转到next
    L2 = L2->Next;
    while ((L1!=NULL)||(L2!=NULL)){   
        if (L1->value != L2->value) {
            return 0;
        }
        else {
            L1 = L1->Next;
            L2 = L2->Next;
        }   
    }
    if ((L1 != NULL) && (L2 != NULL)) 
        return 0;
    return 1;
}


/*把原始比较数组和下一个比较数组按顺序拆分成比树节点大于等于的和小于的,然后比较对应两个数组的大小是不是一样*/

int Campare(List L1,List L2,int flag) {      //跟flag比较后的两个数组
    List L1_big, L1_small, L2_big, L2_small, b1, b2, s1, s2, List1, List2;
    List1 = L1; List2 = L2;
    L1_big = (List)malloc(sizeof(List));
    L1_big->Next = NULL;
    b1 = L1_big;

    L1_small = (List)malloc(sizeof(List));
    L1_small->Next = NULL;
    s1 = L1_small;

    L2_big = (List)malloc(sizeof(List));
    L2_big->Next = NULL;
    b2 = L2_big;

    L2_small = (List)malloc(sizeof(List));
    L2_small->Next = NULL;
    s2 = L2_small;

    List1 = List1->Next;      //因为第一个节点没有value
    List2 = List2->Next;

    while (List1 != NULL) {   //取我们拿来比较的第一个数组
        if (List1->value > flag) {
            L1_big->Next = Add(List1->value);
            L1_big = L1_big->Next;
        }
        else if (List1->value < flag){
            L1_small->Next = Add(List1->value);
            L1_small = L1_small->Next;
        }
        else {
            ;
        }
        List1 = List1->Next;
    }

    while (List2 != NULL) {
        if (List2->value > flag) {
            L2_big->Next = Add(List2->value);
            L2_big = L2_big->Next;
        }
        else if (List2->value < flag) {
            L2_small->Next = Add(List2->value);
            L2_small = L2_small->Next;
        }
        else {
            ;
        }
        List2 = List2->Next;
    }

    if (Judge(b1, b2)) {        //判断比flag大的是不是顺序一样
        if (Judge(s1, s2)) {    //判断比flag小的是不是顺序一样
            return 1;
        }
        else return 0;
    }

    return 0;
}


int main(void) {
    int start;
    int flag;
    List Ans, wer;
    Ans = (List)malloc(sizeof(List));
    Ans->Next = NULL;
    wer = Ans;
    while (scanf_s("%d", &start)) {   //获取每组树的元素个数
        if (start == 0) break;
        int group;
        scanf_s("%d", &group);        //获取比较组数

        List L1, st1, st2;
        L1 = (List)malloc(sizeof(List));
        L1->Next = NULL;
        st1 = L1;

        for (int j = 0; j < start; j++) {   //吃第一组比较数据
            int temp;
            scanf_s("%d", &temp);
            if (j == 0)
                flag = temp;
            L1->Next = Add(temp);
            L1 = L1->Next;
        }

        for (int i = 0; i < group; i++) {  //吃后续的数据 按组吃
            List L2;
            L2 = (List)malloc(sizeof(List));
            L2->Next = NULL;
            st2 = L2;
            for (int k = 0; k < start; k++) {
                int temp;
                scanf_s("%d", &temp);
                L2->Next = Add(temp);
                L2 = L2->Next;
            }

            if (flag != st2->Next->value) {  //根节点不一样
                Ans->Next = Add(0);
            }
            else {
                if (Campare(st1, st2, flag)) {
                    Ans->Next = Add(1);
                    //printf("Yes\n");
                }
                else {
                    Ans->Next = Add(0);
                    //printf("No\n");
                }
            }
            Ans = Ans->Next;
        }

    }
    Print(wer);
    system("pause");
    getchar();
    return 0;
}



//偷鸡成功啦哈哈哈哈哈哈

当然,积极找方法的心态是可取的,但是事实上这种方法是有问题的。反例就是下图 反例.png

(不过还是骗了oj好多分哈哈哈哈哈哈)

正规解答

#include<stdio.h>
#include<stdlib.h>


typedef struct TreeNode * Tree;
struct TreeNode {
    int v;
    Tree Left, Right;
    int flag;
};

Tree NewNode(int V) {
    Tree T = (Tree)malloc(sizeof(struct TreeNode));
    T->v = V;
    T->Left = T->Right = NULL;
    T->flag = 0;
    return T;
}



Tree Insert(Tree T, int V) {
    if (!T)
        T = NewNode(V);
    else {
        if (V > T->v)
            T->Right = Insert(T->Right, V);
        else
            T->Left = Insert(T->Left, V);
    }
    return T;
}


Tree MakeTree(int N) {
    Tree T;
    int i, V;

    scanf_s("%d", &V);
    T = NewNode(V);
    for (i = 1; i < N; i++) {
        scanf_s("%d", &V);
        T = Insert(T, V);
    }
    return T;
}

int check(Tree T, int V) {
    if (T->flag) {
        if (V < T->v)
            return check(T->Left, V);
        else if (V > T->v)
            return check(T->Right, V);
        else 
            return 0;
    }
    else {
        if (V == T->v) {
            T->flag = 1;
            return 1;
        }
        else 
            return 0;
    }
}

int Judge(Tree T, int N) {
    int i, V, flag = 0;
    scanf_s("%d", &V);
    if (V != T->v)
        flag = 1;
    else
        T->flag = 1;
    for (i = 1; i < N; i++) {
        scanf_s("%d", &V);
        if ((!flag) && (!check(T, V)))
            flag = 1;
    }
    if (flag)
        return 0;
    else 
        return 1;
}


void ResetT(Tree T) {
    if (T->Left)
        ResetT(T->Left);
    if (T->Right)
        ResetT(T->Right);
    T->flag = 0;
}

void FreeTree(Tree T) {
    if (T->Left)
        FreeTree(T->Left);
    if (T->Right)
        FreeTree(T->Right);
    free(T);
}



int main(void) {
    int N, L, i;
    Tree T;
    scanf_s("%d", &N);
    while (N) {
        scanf_s("%d", &L);
        T = MakeTree(N);
        for (i = 0; i < L; i++) {
            if (Judge(T, N))
                printf("Yes\n");
            else
                printf("No\n");
            ResetT(T);
        }
        FreeTree(T);
        scanf_s("%d", &N);
    }
    return 0;
}

写在最后

唔,虽说是偷鸡写法但是比正规解还要复杂好多,这个有缺陷的解法改进改进应该还能用(小声bb 这次找了个图床,传图片方便多了~