A Binary Search Tree (BST) is recursively defined as a binary tree which has the following properties:
If we swap the left and right subtrees of every node, then the resulting tree is called the Mirror Image of a BST.
Now given a sequence of integer keys, you are supposed to tell if it is the preorder traversal sequence of a BST or the mirror image of a BST.
Each input file contains one test case. For each case, the first line contains a positive integer N (≤). Then N integer keys are given in the next line. All the numbers in a line are separated by a space.
For each test case, first print in a line YES if the sequence is the preorder traversal sequence of a BST or the mirror image of a BST, or NO if not. Then if the answer is YES, print in the next line the postorder traversal sequence of that tree. All the numbers in a line must be separated by a space, and there must be no extra space at the end of the line.
7
8 6 5 7 10 8 11
YES
5 7 6 8 11 10 8
7
8 10 11 8 6 7 5
YES
11 8 10 7 5 6 8
7
8 6 8 5 10 9 11
NO
题目分析：树的插入 因为给的是先序遍历 所以每次插入时 如果插入的是左子树 那么它的父亲的右节点必然为空 不然就插入失败 对于对称的情况也是类似
因此 我们只需要知道在插入时 每个节点左右子树是否存在就可
1 #define _CRT_SECURE_NO_WARNINGS 2 #include <climits> 3 #include<iostream> 4 #include<vector> 5 #include<queue> 6 #include<map> 7 #include<set> 8 #include<stack> 9 #include<algorithm> 10 #include<string> 11 #include<cmath> 12 using namespace std; 13 typedef struct Node* PtrToNode; 14 vector<int> V; 15 struct Node{ 16 int data; 17 PtrToNode Left, Right; 18 bool LE, RI; 19 }; 20 bool Insert(PtrToNode&T,int Element) 21 { 22 if (!T){ 23 T = new Node; 24 T->data = Element; 25 T->Left = NULL; 26 T->Right = NULL; 27 T->LE = false; 28 T->RI = false; 29 } 30 else 31 if (Element < T->data){ 32 if (T->RI) 33 return false; 34 else{ 35 T->LE = true; 36 return Insert(T->Left, Element); 37 } 38 } 39 else{ 40 T->RI = true; 41 return Insert(T->Right, Element); 42 } 43 return true; 44 } 45 bool InsertR(PtrToNode& T, int Element) 46 { 47 if (!T) { 48 T = new Node; 49 T->data = Element; 50 T->Left = NULL; 51 T->Right = NULL; 52 T->LE = false; 53 T->RI = false; 54 } 55 else 56 if (Element >=T->data) { 57 if (T->RI) 58 return false; 59 else { 60 T->LE = true; 61 return InsertR(T->Left, Element); 62 } 63 } 64 else { 65 T->RI = true; 66 return InsertR(T->Right, Element); 67 } 68 return true; 69 } 70 void PostOrder(PtrToNode T) 71 { 72 if(T) 73 { 74 PostOrder(T->Left); 75 PostOrder(T->Right); 76 V.push_back(T->data); 77 } 78 } 79 int main() 80 { 81 int N; 82 cin >> N; 83 int num; 84 PtrToNode TL = NULL, TR = NULL; 85 bool flagL,flagR; 86 flagL = flagR = true; 87 for (int i = 0; i < N; i++) 88 { 89 cin >> num; 90 if(flagL)flagL = Insert(TL, num); 91 if(flagR)flagR = InsertR(TR, num); 92 if (!flagL&&!flagR) 93 break; 94 } 95 if (flagL||flagR) 96 { 97 cout << "YES"<<endl; 98 if (flagL) 99 PostOrder(TL); 100 else 101 PostOrder(TR); 102 for (auto it = V.begin(); it != (V.end() - 1); it++) 103 cout << *it << " "; 104 cout << *(V.end() - 1); 105 } 106 else 107 cout << "NO"; 108 109 }
1043 Is It a Binary Search Tree (25分)(树的插入)
原文：https://www.cnblogs.com/57one/p/12031038.html
