九度oj 题目1201:二叉排序树
2024-09-29 02:56:38
- 题目描述:
-
输入一系列整数,建立二叉排序数,并进行前序,中序,后序遍历。
- 输入:
-
输入第一行包括一个整数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
- 提示:
-
输入中可能有重复元素,但是输出的二叉树遍历序列中重复元素不用输出。
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#define N 109 struct Node
{
int key;
int left;
int right;
}; int tree[N];
Node treeNode[N]; void pre(int gen) {
if(gen == -) {
return;
}
printf("%d ",treeNode[gen].key);
pre(treeNode[gen].left);
pre(treeNode[gen].right); } void middle(int gen) {
if(gen == -) {
return;
}
middle(treeNode[gen].left);
printf("%d ",treeNode[gen].key);
middle(treeNode[gen].right); } void hou(int gen) {
if(gen == -) {
return;
}
hou(treeNode[gen].left);
hou(treeNode[gen].right);
printf("%d ",treeNode[gen].key);
}
int main(int argc, char const *argv[])
{
int n;
while(scanf("%d",&n) != EOF) {
for(int i = ; i < n; i++) {
scanf("%d",&tree[i]);
}
treeNode[].key = tree[];
treeNode[].left = -;
treeNode[].right = -;
for(int i = ; i < n; i++) {
treeNode[i].key = tree[i];
treeNode[i].left = -;
treeNode[i].right = -;
int lastTemp = -;
int temp = ;
bool dir = false;
bool isEqual = false;
while(temp != -) {
if(tree[i] < treeNode[temp].key) {
lastTemp = temp;
temp = treeNode[temp].left;
dir = false;
}
else if(tree[i] > treeNode[temp].key){
lastTemp = temp;
temp = treeNode[temp].right;
dir = true;
}
else {
isEqual = true;
break;
}
}
if(isEqual) {
continue;
}
if(dir == false) {
treeNode[lastTemp].left = i;
}
else {
treeNode[lastTemp].right = i;
} }
pre();
printf("\n");
middle();
printf("\n");
hou();
printf("\n");
}
return ;
}
最新文章
- 消除a标签点击后产生的虚线框
- 【python】GTK 例子
- [书目20160526]Brain Rules 让大脑自由:释放天赋的12条定律
- C# 定制 Attribute 简单使用
- 单例模式(oc)
- CentOS学习笔记--账号管理与权限配置
- 第八讲:HTML5中canvas实现小球击打小方块游戏
- Winform- IrisSkin.dll轻松实现窗体换肤功能
- 安卓SDK Manager自动管理各种包
- juce中的引用计数
- BZOJ 1010: [HNOI2008]玩具包装toy
- 拥抱.NET Core系列:Logging (1)
- python generator(生成器)
- Spark官方2 ---------Spark 编程指南(1.5.0)
- cookie大小
- PyCharm导入tensorflow包
- 从Paxos到Zookeeper分布式一致性原理与实践 读书笔记之(一) 分布式架构
- luffy项目的接口开发
- Django中CBV(Class Base Views)模型源码分析
- java利用反射获取对象前后修改的内容(用于日志记录)