二叉排序树：HDU3791-二叉搜索树（用指针建立二叉排序树）

二叉搜索树

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)

Problem Description

判断两序列是否为同一二叉搜索树序列

Input

开始一个数n，(1<=n<=20) 表示有n个需要判断，n= 0 的时候输入结束。

接下去一行是一个序列，序列长度小于10，包含(0~9)的数字，没有重复数字，根据这个序列可以构造出一颗二叉搜索树。

接下去的n行有n个序列，每个序列格式跟第一个序列一样，请判断这两个序列是否能组成同一颗二叉搜索树。

Output

如果序列相同则输出YES，否则输出NO

Sample Input

2

567432

543267

576342

0

Sample Output

YES

NO

解题心得：

这个题只要建立一个二叉排序树就可以了。这里使用的是一个指针建立二叉排序树。对指针的理解需要较高的要求，不懂的可以去看看紫书。
建立二叉排序树分为两个部分，插入部分和节点更新部分。插入部分就是找到这个数应该插到树的哪个位置。而更新部分则是将未插入的部分的子节点初始化为空。

#include<bits/stdc++.h>

using namespace std;

const int maxn = 20;

char s[maxn],s1[maxn];

struct node

{

    int num;

    node *l,*r;

}tree[20];

int n,index;

node* newnode(int v)//初始化根节点

{

    tree[index].num = v;

    tree[index].l = NULL;

    tree[index].r = NULL;

    return &tree[index++];

}

void insertBST(node*& root,int num)//root本身就是一个指针，这里传递过来改变的是指针的地址

{

    if(root == NULL)//当这个节点为空的时候可以插入，然后初始化他的根节点

    {

        root = newnode(num);

        return ;

    }

    if(root->num > num)//递归部分

        insertBST(root->l,num);

    else

        insertBST(root->r,num);

}

void buildtree(node*& root,char *s,int len)

{

    root = NULL;//根节点初始化为空

    for(int i=0; i<len; i++)

        insertBST(root,s[i]-'0');

}

bool isEquel(node *p,node *q)//比较两个树是否相同

{

    if(p == NULL)

        return q  == NULL;

    else if(q == NULL || p->num != q->num)

        return false;

    else return isEquel(q->l,p->l)&&isEquel(q->r,p->r);

}

int main()

{

    while(scanf("%d",&n) && n)

    {

        memset(tree,0,sizeof(tree));

        index = 0;

        scanf("%s",s);

        int len = strlen(s);

        node *p,*q;

        buildtree(p,s,len);

        while(n--)

        {

            scanf("%s",s1);

            if(strlen(s) != strlen(s1))

            {

                printf("NO\n");

                continue;

            }

            len = strlen(s1);

            index = len;

            buildtree(q,s1,len);

            if(isEquel(p,q))

                printf("YES\n");

            else

                printf("NO\n");

        }

    }

}

巴特西