题目1201：二叉排序树
时间限制：1 秒
内存限制：32 兆
特殊判题：否
提交：7024
解决：2983
- 题目描述：
-
输入一系列整数，建立二叉排序数，并进行前序，中序，后序遍历。
- 输入：
-
输入第一行包括一个整数n(1<=n<=100)。
接下来的一行包括n个整数。
- 输出：
-
可能有多组测试数据，对于每组数据，将题目所给数据建立一个二叉排序树，并对二叉排序树进行前序、中序和后序遍历。
每种遍历结果输出一行。每行最后一个数据之后有一个空格。
- 样例输入：
-
5 1 6 5 9 8
- 样例输出：
-
1 6 5 9 8 1 5 6 8 9 5 8 9 6 1
- 提示：
-
输入中可能有重复元素，但是输出的二叉树遍历序列中重复元素不用输出。
分析：重复元素不用输出，那么重复元素就不要放入二叉排序树中！否则输出的时候会很麻烦。
代码一：将中序遍历的元素放入一个容器中，最后在输出。可以控制格式(每行最后一个数据后没有空格）
1 #include <iostream> 2 #include <cstdlib> 3 #include <vector> 4 #include <cstdio> 5 using namespace std; 6 7 typedef struct node{ 8 int val; 9 struct node *left; 10 struct node *right; 11 } TreeNode, *Tree; 12 13 void insert(TreeNode *&root, int num){ 14 if(root == NULL){ 15 root = (TreeNode *)malloc(sizeof(TreeNode)); 16 //TreeNode *root = (TreeNode *)malloc(sizeof(TreeNode));这样写错误 17 root->val = num; 18 root->left = NULL; 19 root->right = NULL; 20 return; 21 } 22 if(root->val == num) 23 return; 24 if(root->val > num) 25 insert(root->left, num); 26 else 27 insert(root->right, num); 28 } 29 30 void PreTraversal(Tree root, vector<int> &v){ 31 if(root == NULL) 32 return; 33 //cout << root->val << " "; 34 v.push_back(root->val); 35 PreTraversal(root->left, v); 36 PreTraversal(root->right, v); 37 } 38 39 void InTraversal(Tree root, vector<int> &v){ 40 if(root == NULL) 41 return; 42 InTraversal(root->left, v); 43 //cout << root->val << " "; 44 v.push_back(root->val); 45 InTraversal(root->right, v); 46 } 47 48 void PostTraversal(Tree root, vector<int> &v){ 49 if(root == NULL) 50 return; 51 PostTraversal(root->left, v); 52 PostTraversal(root->right, v); 53 //cout << root->val << " "; 54 v.push_back(root->val); 55 } 56 57 void print(vector<int> v){ 58 int size = v.size(); 59 for(int i = 0; i < size; i++) 60 printf("%d ", v[i]); 61 printf(" "); 62 } 63 64 int main(){ 65 vector<int> pre_v, in_v, post_v; 66 int n, num; 67 while(scanf("%d", &n) != EOF){ 68 pre_v.clear(); 69 in_v.clear(); 70 post_v.clear(); 71 Tree root = NULL; 72 for(int i = 0; i < n; i++){ 73 scanf("%d", &num); 74 insert(root, num); 75 } 76 PreTraversal(root, pre_v); 77 InTraversal(root, in_v); 78 PostTraversal(root, post_v); 79 print(pre_v); 80 print(in_v); 81 print(post_v); 82 } 83 return 0; 84 }
代码二：直接遍历输出：
1 #include <iostream> 2 #include <cstdlib> 3 #include <cstdio> 4 using namespace std; 5 6 typedef struct node{ 7 int val; 8 struct node *left; 9 struct node *right; 10 } TreeNode, *Tree; 11 12 void insert(TreeNode *&root, int num){ 13 if(root == NULL){ 14 root = (TreeNode *)malloc(sizeof(TreeNode)); 15 //TreeNode *root = (TreeNode *)malloc(sizeof(TreeNode));这样写错误 16 root->val = num; 17 root->left = NULL; 18 root->right = NULL; 19 return; 20 } 21 if(root->val == num) 22 return; 23 if(root->val > num) 24 insert(root->left, num); 25 else 26 insert(root->right, num); 27 } 28 29 void PreTraversal(Tree root){ 30 if(root == NULL) 31 return; 32 printf("%d ", root->val); 33 PreTraversal(root->left); 34 PreTraversal(root->right); 35 } 36 37 void InTraversal(Tree root){ 38 if(root == NULL) 39 return; 40 InTraversal(root->left); 41 printf("%d ", root->val); 42 InTraversal(root->right); 43 } 44 45 void PostTraversal(Tree root){ 46 if(root == NULL) 47 return; 48 PostTraversal(root->left); 49 PostTraversal(root->right); 50 printf("%d ", root->val); 51 } 52 53 int main(){ 54 int n, num; 55 while(scanf("%d", &n) != EOF){ 56 Tree root = NULL; 57 for(int i = 0; i < n; i++){ 58 scanf("%d", &num); 59 insert(root, num); 60 } 61 PreTraversal(root); 62 printf(" "); 63 InTraversal(root); 64 printf(" "); 65 PostTraversal(root); 66 printf(" "); 67 } 68 return 0; 69 }