PTA数据结构与算法题目集(中文) 7-28

7-28 搜索树判断 (25 分)

对于二叉搜索树，我们规定任一结点的左子树仅包含严格小于该结点的键值，而其右子树包含大于或等于该结点的键值。如果我们交换每个节点的左子树和右子树，得到的树叫做镜像二叉搜索树。

现在我们给出一个整数键值序列，请编写程序判断该序列是否为某棵二叉搜索树或某镜像二叉搜索树的前序遍历序列，如果是，则输出对应二叉树的后序遍历序列。

输入格式:

输入的第一行包含一个正整数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
题目分析:一道利用树的基础题 将数据读入后 再按先序遍历输出 比较 注意因为有镜像二叉搜索树 所以先序遍历要检查从左边开始以及从右边开始 最后输出后序遍历时 二叉搜索树从左边 镜像二叉搜索从右边

  1 #define _CRT_SECURE_NO_WARNINGS
  2 #include<stdio.h>
  3 #include<string.h>
  4 #include<malloc.h>
  5
  6 typedef struct TreeNode* PtrToTreeNode;
  7 typedef PtrToTreeNode BTree;
  8 struct TreeNode
  9 {
 10     int Data;
 11     PtrToTreeNode Lc;
 12     PtrToTreeNode Rc;
 13 };
 14
 15 PtrToTreeNode Insert(int Data, BTree BT)
 16 {
 17     if (!BT)
 18     {
 19         BT = (BTree)malloc(sizeof(struct TreeNode));
 20         BT->Data = Data;
 21         BT->Lc = NULL;
 22         BT->Rc = NULL;
 23     }
 24     else
 25     {
 26         if (Data < BT->Data)
 27             BT->Lc = Insert(Data, BT->Lc);
 28         else
 29             BT->Rc = Insert(Data, BT->Rc);
 30     }
 31     return BT;
 32 }
 33
 34 int Pre[1000];
 35 int Size;
 36 void PreOrder(BTree Bt)
 37 {
 38     if (Bt)
 39     {
 40         Pre[Size++] = Bt->Data;
 41         PreOrder(Bt->Lc);
 42         PreOrder(Bt->Rc);
 43     }
 44 }
 45 void PreOrderRight(BTree Bt)
 46 {
 47     if (Bt)
 48     {
 49         Pre[Size++] = Bt->Data;
 50         PreOrderRight(Bt->Rc);
 51         PreOrderRight(Bt->Lc);
 52     }
 53 }
 54
 55 int Last[1000];
 56 int Size2;
 57 void LastOrder(BTree Bt)
 58 {
 59     if (Bt)
 60     {
 61         LastOrder(Bt->Lc);
 62         LastOrder(Bt->Rc);
 63         Last[Size2++] = Bt->Data;
 64     }
 65 }
 66 void LastOrderRight(BTree Bt)
 67 {
 68     if (Bt)
 69     {
 70         LastOrderRight(Bt->Rc);
 71         LastOrderRight(Bt->Lc);
 72         Last[Size2++] = Bt->Data;
 73     }
 74 }
 75
 76 int main()
 77 {
 78     int N;
 79     scanf("%d", &N);
 80     BTree Bt = NULL;
 81     int Num[1000] = { 0 };
 82     for (int i = 0; i < N; i++)
 83     {
 84         scanf("%d", &Num[i]);
 85         Bt = Insert(Num[i], Bt);
 86     }
 87     PreOrder(Bt);
 88     int flag = 1;
 89     int Left = 1;
 90     for (int i = 0; i < N; i++)
 91     {
 92         if (Num[i] != Pre[i])
 93         {
 94             flag = 0;
 95             break;
 96         }
 97     }
 98     if (!flag)
 99     {
100         Size = 0;
101         flag = 1;
102         Left = 0;
103         PreOrderRight(Bt);
104         for (int i = 0; i < N; i++)
105         {
106             if (Num[i] != Pre[i])
107             {
108                 flag = 0;
109                 break;
110             }
111         }
112     }
113     if (!flag)
114         printf("NO\n");
115     else
116     {
117         printf("YES\n");
118         if (Left)
119         {
120             LastOrder(Bt);
121             for (int i = 0; i < N - 1; i++)
122                 printf("%d ", Last[i]);
123         }
124         else
125         {
126             LastOrderRight(Bt);
127             for (int i = 0; i < N - 1; i++)
128                 printf("%d ", Last[i]);
129         }
130         printf("%d", Last[N - 1]);
131     }
132     return 0;
133 }

View Code