PTA

PTA 7-2 搜索树判断

搜索树判断

Posted by beansugar on October 24, 2023

前言

这题困扰了我三天啊，终究还是我太菜了。
总共一百多行。比网上其他人的多了点，但胜在好懂~

以下是正文

题目

对于二叉搜索树，我们规定任一结点的左子树仅包含严格小于该结点的键值，而其右子树包含大于或等于该结点的键值。如果我们交换每个节点的左子树和右子树，得到的树叫做镜像二叉搜索树。
现在我们给出一个整数键值序列，请编写程序判断该序列是否为某棵二叉搜索树或某镜像二叉搜索树的前序遍历序列，如果是，则输出对应二叉树的后序遍历序列。

输入格式

输入的第一行包含一个正整数N（≤1000），第二行包含N个整数，为给出的整数键值序列，数字间以空格分隔。

输出格式

输出的第一行首先给出判断结果，如果输入的序列是某棵二叉搜索树或某镜像二叉搜索树的前序遍历序列，则输出YES，否侧输出NO。如果判断结果是YES，下一行输出对应二叉树的后序遍历序列。数字间以空格分隔，但行尾不能有多余的空格

输入样例1:

7  
8 6 5 7 10 8 11

输出样例1:

YES
5 7 6 8 11 10 8

输入样例2:

7
8 6 8 5 10 9 11

输出样例2:

NO

思路

总思路很简单，因为是搜索树，左边结点小于根结点，右边大于，所以只需判断先序遍历是否只存在连续的小于根结点和大于根结点的序列。

实现过程

首先肯定是输入，第一行是结点数量，第二行是各个结点的值，中间用空格分开。先想到的是用一个数组或者堆栈来接受输入的值，我这边先用数组。
然后要根据先序遍历创建二叉树或镜像二叉树

int intarray[1005];//输入数组，作为对照组,全局变量

typedef struct TNode* Position;
typedef Position BinTree;

struct TNode {
    int Data;
    BinTree Left;
    BinTree Right;
};

int main() {
    BinTree b = NULL; // 二叉树
    int num; // 结点数
    scanf("%d", &num);

    for (int i = 0; i < num; i++) {
        int temp;
        scanf("%d", &temp);
        intarray[i] = temp;
        b = Insert(b, temp);
    }
}

然后就要生成二叉树和镜像二叉树了（函数Insert()）

//二叉树的构建
BinTree Insert(BinTree BST, int X) {
    if (!BST) {
        BST = (BinTree)malloc(sizeof(struct TNode));
        BST->Data = X;
        BST->Left = BST->Right = NULL;
    }
    else {
        if (X < BST->Data) {
            BST->Left = Insert(BST->Left, X);
        }
        else {
            BST->Right = Insert(BST->Right, X);
        }
    }
    return BST;
}

// 创建镜像二叉树
BinTree MirrorTree(BinTree BT) {
    if (BT) {
        BinTree temp = BT->Left;
        BT->Left = MirrorTree(BT->Right);
        BT->Right = MirrorTree(temp);
    }
    return BT;
}

随后就是检查该二叉树是否为先序遍历了,我这边创建了两个函数分别判断二叉树和镜像二叉树

// 检查是否是二叉搜索树前序遍历序列
int IsBSTPreorder(int* sequence, int len) {
    if (len <= 1) {
        return 1;
    }

    int root = sequence[0];//首元素
    int i;
    for (i = 1; i < len; i++) {
        if (sequence[i] >= root) {
            break;
        }
    }

    for (int j = i; j < len; j++) {
        if (sequence[j] < root) {
            return 0;
        }
    }

    return IsBSTPreorder(sequence + 1, i - 1) && IsBSTPreorder(sequence + i, len - i);
}

// 检查是否是镜像树前序遍历序列
int IsMirrorBSTPreorder(int* sequence, int len) {
    if (len <= 1) {
        return 1;
    }

    int root = sequence[0];
    int i;
    for (i = 1; i < len; i++) {
        if (sequence[i] < root) {
            break;
        }
    }

    for (int j = i; j < len; j++) {
        if (sequence[j] >= root) {
            return 0;
        }
    }

    return IsMirrorBSTPreorder(sequence + 1, i - 1) && IsMirrorBSTPreorder(sequence + i, len - i);
}

若为真，则输出后序遍历我这边也用了个函数,为此需要一对数组和下标来储存后序遍历的顺序

int postorder[1005];//生成数组
int postIndex = 0;//数组索引

void SavePostOrder(BinTree BT) {
    if (BT) {
        SavePostOrder(BT->Left);
        SavePostOrder(BT->Right);
        postorder[postIndex++] = BT->Data;
    }
}

最后只需要调用函数进行判断和输出就可以了

以下是完整代码

完整代码

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

int intarray[1005];//输入数组，作为对照组
int postorder[1005];//生成数组
int postIndex = 0;//数组索引

typedef struct TNode* Position;
typedef Position BinTree;

struct TNode {
    int Data;
    BinTree Left;
    BinTree Right;
};
//二叉树的构建
BinTree Insert(BinTree BST, int X) {
    if (!BST) {
        BST = (BinTree)malloc(sizeof(struct TNode));
        BST->Data = X;
        BST->Left = BST->Right = NULL;
    }
    else {
        if (X < BST->Data) {
            BST->Left = Insert(BST->Left, X);
        }
        else {
            BST->Right = Insert(BST->Right, X);
        }
    }
    return BST;
}

// 创建镜像二叉树
BinTree MirrorTree(BinTree BT) {
    if (BT) {
        BinTree temp = BT->Left;
        BT->Left = MirrorTree(BT->Right);
        BT->Right = MirrorTree(temp);
    }
    return BT;
}

// 检查是否是二叉搜索树前序遍历序列
int IsBSTPreorder(int* sequence, int len) {
    if (len <= 1) {
        return 1;
    }

    int root = sequence[0];//首元素
    int i;
    for (i = 1; i < len; i++) {
        if (sequence[i] >= root) {
            break;
        }
    }

    for (int j = i; j < len; j++) {
        if (sequence[j] < root) {
            return 0;
        }
    }

    return IsBSTPreorder(sequence + 1, i - 1) && IsBSTPreorder(sequence + i, len - i);
}

// 检查是否是镜像树前序遍历序列
int IsMirrorBSTPreorder(int* sequence, int len) {
    if (len <= 1) {
        return 1;
    }

    int root = sequence[0];
    int i;
    for (i = 1; i < len; i++) {
        if (sequence[i] < root) {
            break;
        }
    }

    for (int j = i; j < len; j++) {
        if (sequence[j] >= root) {
            return 0;
        }
    }

    return IsMirrorBSTPreorder(sequence + 1, i - 1) && IsMirrorBSTPreorder(sequence + i, len - i);
}

// 保存后序遍历结果到数组
void SavePostOrder(BinTree BT) {
    if (BT) {
        SavePostOrder(BT->Left);
        SavePostOrder(BT->Right);
        postorder[postIndex++] = BT->Data;
    }
}

int main() {
    BinTree b = NULL; // 二叉树
    int num; // 结点数
    scanf("%d", &num);

    for (int i = 0; i < num; i++) {
        int temp;
        scanf("%d", &temp);
        intarray[i] = temp;
        b = Insert(b, temp);
    }

    if (IsBSTPreorder(intarray, num)) {
        postIndex = 0; // 重置序号
        SavePostOrder(b);

        printf("YES\n");
        for (int i = 0; i < num; i++) {//输出后序遍历
            printf("%d", postorder[i]);
            if (i < num - 1) {//除了最后一个后面不用跟空格，题目要求
                printf(" ");
            }
        }
    }
    else if (IsMirrorBSTPreorder(intarray, num))
    {
        b = MirrorTree(b);
        postIndex = 0; // 重置序号
        SavePostOrder(b);

        printf("YES\n");
        for (int i = 0; i < num; i++) {//输出后序遍历
            printf("%d", postorder[i]);
            if (i < num - 1) {//除了最后一个后面不用跟空格，题目要求
                printf(" ");
            }
        }
    }
    else {
        printf("NO");
    }
    return 0;
}
CATALOG
    FEATURED TAGS
    Data Structure