04-树4 是否同一棵二叉搜索树

　课上例题，重点和难点是 标记变量(flag) 使用。

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

typedef struct TreeNode *BinTree;
struct TreeNode {
    int Data;
    BinTree Left, Right;
    int flag;
};

BinTree BuildTree(int N);
BinTree NewNode(int num);
BinTree Insert(BinTree T, int num);
int check(BinTree T, int num);
int Judge(BinTree T, int N);
void Reset(BinTree);
void FreeTree(BinTree T);

int main() 
{
    int N, L, i;
    BinTree T;
    
    scanf("%d", &N);
    
    while ( N ) {
        scanf("%d", &L);
        T = BuildTree(N);
        for ( i = 0; i < L; i++ ) {
            if ( Judge(T, N) )    printf("Yes
");
            else                 printf("No
");
            
            Reset(T);  /* 清除 T 中 的标记 flag */
        }
        FreeTree(T);
        
        scanf("%d", &N);
    }
    
    return 0; 
} 

int Judge(BinTree T, int N)
{
    int tag = 1; /* tag: 1 代表目前还一致，0 代表目前不一致 */ 
    int digit, i;
    scanf("%d", &digit);
    
    if ( digit == T->Data ) T->flag = 1;
    else tag = 0;
    
    for ( i = 1; i < N; i++ ) {
        scanf("%d", &digit);
        if ( tag && !check(T, digit) ) tag = 0;
    }
    
    return tag;
}

int check(BinTree T, int num)
{
    if ( T->flag ) {
        if ( num < T->Data )    
            return check(T->Left, num);
        else if ( num > T->Data )
            return check(T->Right, num);
        else return 0;
    }  
    else {
        if ( num == T->Data ) {
            T->flag = 1;
            return 1;
        }
        else return 0;
    }
}

BinTree BuildTree(int N)
{
    int i, num;
    scanf("%d", &num);
    
    BinTree T = NewNode(num);
    
    for ( i = 1; i < N; i++ ) {
        scanf("%d", &num);
        T = Insert(T, num);
    }
    
    return T;
}

BinTree Insert(BinTree T, int num)
{
    if ( !T )    T = NewNode(num);
    else {
        if ( num < T->Data ) {
            T->Left = Insert(T->Left, num);
        }
        else if ( num > T->Data ) {
            T->Right = Insert(T->Right, num);
        }
    }
    
    return T;
}

BinTree NewNode(num)
{
    BinTree T = (BinTree)malloc(sizeof(struct TreeNode));
    T->Left = T->Right = NULL;
    T->Data = num;
    T->flag = 0;
    
    return T;
}

void Reset(BinTree T)  /* 清除 T 中各节点的 flag 标记 */ 
{
    if ( T->Left )    Reset(T->Left);
    if ( T->Right )    Reset(T->Right);
    T->flag = 0;
}

void FreeTree(BinTree T) /* 释放 T 的空间 */
{
    if ( T->Left ) FreeTree(T->Left);
    if ( T->Right ) FreeTree(T->Right);
    free(T);
}