二叉排序树
[html]题目描述:输入一系列整数,建立二叉排序数,并进行前序,中序,后序遍历。输入:输入第一行包括一个整数n(1<=n<=100)。接下来的一行包括n个整数。输出:可能有多组测试数据,对于每组数据,将题目所给数据建立一个二叉排序树,并对二叉排序树进行前序、中序和后序遍历。每种遍历结果输出一行。每行最后一个数据之后有一个空格。样例输入:51 6 5 9 8样例输出:1 6 5 9 81 5 6 8 95 8 9 6 1提示:输入中可能有重复元素,但是输出的二叉树遍历序列中重复元素不用输出。AC代码[cpp]#include <stdio.h>#include <stdlib.h>#include <string.h>#define N 101struct btree{struct btree *lchild, *rchild;int data;};struct stack{struct btree* arr[N];int top;};struct btree* create_sortree(struct btree* t, int d);void pre_traverse(struct btree *t);void order_traverse(struct btree *t);void post_traverse(struct btree *t);void clean_tree(struct btree *t);int main(){int i, n, d;struct btree *t;while (scanf("%d", &n) != EOF) {//接收客户端输入,构建二叉排序树for (i = 0, t = NULL; i < n; i ++) {scanf("%d", &d);t = create_sortree(t, d);}// 前序遍历pre_traverse(t);// 中序遍历order_traverse(t);// 后序遍历post_traverse(t);// 清理clean_tree(t);}return 0;}struct btree* create_sortree(struct btree *t, int d){if (t == NULL) {t = (struct btree*)malloc(sizeof(struct btree) * 1);t->data = d;t->lchild = NULL;t->rchild = NULL;}else if(t->data > d) { // 插入到左子树t->lchild = create_sortree(t->lchild, d);}else if(t->data < d) { // 插入到右子树t->rchild = create_sortree(t->rchild, d);}else {// 相同元素不进行任何操作}return t;}void pre_traverse(struct btree *t){struct btree *p = t;struct stack *s = (struct stack*)malloc(sizeof(struct stack) * 1);s->top = 0;while (s->top || p) {if (p) {printf("%d ", p->data);s->arr[s->top ++] = p;p = p->lchild;}else {p = s->arr[-- s->top];p = p->rchild;}}printf("\n");}void order_traverse(struct btree *t){struct btree *p = t;struct stack *s = (struct stack*)malloc(sizeof(struct stack) * 1);s->top = 0;while (s->top || p) {if (p) {s->arr[s->top ++] = p;p = p->lchild;}else {p = s->arr[-- s->top];printf("%d ", p->data);p = p->rchild;}}printf("\n");}void post_traverse(struct btree *t){struct btree *p, *pre;struct stack *s = (struct stack*)malloc(sizeof(struct stack) * 1);s->top = 0;pre = NULL;p = t;while (p || s->top) {if (p) {s->arr[s->top ++] = p;p = p->lchild;}else {p = s->arr[-- s->top];if (p->rchild == NULL || p->rchild == pre) {printf("%d ", p->data);pre = p;p = NULL;}else {s->arr[s->top ++] = p;p = p->rchild;&n补充:软件开发 , C++ ,
上一个:Unicode和字符串处理
下一个:POJ 1201 Intervals
- 更多C/C++疑问解答:
- 关于c++的cout输出的问题。
- 在学校里学过C和C++,不过学的很一般,现在自学C#,会不会很难?
- 全国计算机二级C语言笔试题
- 已知某树有2个2度结点,3个3度结点,4个4度结点,问有几个叶子结点?
- c++数据结构内部排序问题,整数排序
- 2012九月计算机二级C语言全国题库,,急求急求
- 如果assert只有一个字符串作为参数,是什么意思呢?
- C语言中,哪些运算符具有左结合性,哪些具有右结合性,帮忙总结下,谢谢了!
- 为什么用结构体编写的程序输入是,0输不出来啊~~~
- 将IEEE—754的十六进制转化为十进制浮点类型,用C或C++都行,多谢各位大侠啊,非常感谢!
- 为什么这个程序求不出公式?
- 这个链表倒置的算法请大家分析下
- c语言函数库调用
- C语言unsigned int纠错
- C语言快排求解啊