二叉树搜索 C++ 🧐66

Question

这该怎么做？给点思路，解法
（判断若干个序列是否为同一个二叉树序列）

Answer 1

#include <iostream>
#include <cstring>

using namespace std;
struct node {
    node *left;
    node *right;
    int num;
}tree[105];                //静态数组

char str1[30], str2[30];//x表示原始的中后序编历，y表示后来的中后序编历
int cnt;            //静态数组中要使用的元素
int num;            //字符数组中要使用的元素

node *creat()        //申请新结点
{
    tree[cnt].left = tree[cnt].right = NULL;
    return &tree[cnt++];
}

node *build(int x, node*t)            
{
    if (t == NULL)
    {
        t = creat();
        t->num = x;
    }
    else if (x < t->num) 
    {
        t->left = build(x, t->left);
    }
    else if (x > t->num) 
    {
        t->right = build(x, t->right);
    }
    return t;
}

void in_order(node *root) {//中序遍历
    if (root == NULL) return;
    in_order(root->left);
    str2[num++] = root->num + '0';
    in_order(root->right);
}

void port_order(node *root)            //后序编历
{
    if (root == NULL)return;
    port_order(root ->left);
    port_order(root->right);
    str2[num++] = root->num + '0';
}
int main()
{
    int n;
    while (cin>> n&&n!=0)
    {
        scanf("%s", str1);                        
        int len = strlen(str1);                //用strlen求x数组的长度
        cnt = 0; num = 0;
        node *t = NULL;
        for (int i = 0; i < len; i++)        //建立最开始的二叉排序树即二叉搜索树
        {
            t = build(str1[i] - '0',t);
        }
        in_order(t);
        port_order(t);                    //开始编历
        for (int i = 0; i < num; i++)
        {
            str1[i] = str2[i];
        }
        while (n--)                            //循环至输入n之后结束
        {
            cnt = 0; num = 0;
            cin>>str2;
            int len = strlen(str2);
            node *tt = NULL;
            for (int i = 0; i < len; i++)    //建立用于比较的二叉搜索树
            {
                tt = build(str2[i] - '0', tt);
            }
            in_order(tt);                    //进行编历
            port_order(tt);
            int i;
            for (i = 0; i < num; i++)
            {
                if (str1[i] != str2[i])
                {
                    break;
                }
            }
            if (i == num)
            {
                cout << "YES" << endl;                                    //可输出比较结果进行判断是否正确
                /*cout << "编历结果如下：" << endl;
                cout << "原先的中后序编历结果：";
                for (int i = 0; i < num; i++)
                    cout << str1[i];
                cout << endl;
                cout << "被比较的序列中后序编历结果:";
                for (int i = 0; i < num; i++)
                    cout << str2[i];*/
            }
            else cout << "NO" << endl;
        }
    }
    return 0;
}