think： 1建立排序二叉树时 注意重复元素 sdut原题链接 树结构练习——排序二叉树的中序遍历 Time Limit: 1000MS Memory Limit: 65536KB
PRoblem Description 在树结构中，有一种特殊的二叉树叫做排序二叉树，直观的理解就是——(1).每个节点中包含有一个关键值 (2).任意一个节点的左子树（如果存在的话）的关键值小于该节点的关键值 (3).任意一个节点的右子树（如果存在的话）的关键值大于该节点的关键值。现给定一组数据，请你对这组数据按给定顺序建立一棵排序二叉树，并输出其中序遍历的结果。
Input 输入包含多组数据，每组数据格式如下。 第一行包含一个整数n，为关键值的个数，关键值用整数表示。(n<=1000) 第二行包含n个整数，保证每个整数在int范围之内。
Output 为给定的数据建立排序二叉树，并输出其中序遍历结果，每个输出占一行。
Example Input 1 2 2 1 20
Example Output 2 1 20
Hint 1 注意重复元素 Author 赵利强
以下为accepted代码
#include <stdio.h>#include <string.h>#include <stdlib.h>typedef struct node{ int date; struct node *left; struct node *right;} BinTree;int flag, n, a[1400];BinTree * Insert(BinTree *rt, int x)//二叉搜索树的建立算法{ if(!rt) /* 若原树为空，生成并返回一个结点的二叉搜索树*/ { rt = (BinTree *)malloc(sizeof(BinTree)); rt->date = x; rt->left = rt->right = NULL; } else /* 开始找要插入元素的位置*/ { if(x < rt->date) rt->left = Insert(rt->left, x);//递归插入左子树 ///else if(x > rt->date)/*wrong answer*/ else rt->right = Insert(rt->right, x);//递归插入右子树 } return rt;}void mid_put(BinTree *rt)//中序遍历算法{ if(rt) { mid_put(rt->left);//左子树递归 a[flag++] = rt->date; mid_put(rt->right);//右子树递归 }}int main(){ int i, x; while(scanf("%d", &n) != EOF) { if(n > 0) { BinTree *root = NULL; flag = 0; for(i = 0; i < n; i++) { scanf("%d", &x); root = Insert(root, x); } mid_put(root); for(i = 0; i < flag; i++) { printf("%d%c", a[i], i == flag-1? '/n': ' '); } } } return 0;}/***************************************************User name: jk160630Result: AcceptedTake time: 0msTake Memory: 128KBSubmit time: 2017-02-08 17:07:08****************************************************/新闻热点
疑难解答
