文档章节

二叉排序树 创建和 遍历

 阿豪boy
发布于 2017/02/24 17:34
字数 402
阅读 11
收藏 0
点赞 0
评论 0

题目描述

https://www.nowcoder.com/questionTerminal/b42cfd38923c4b72bde19b795e78bcb3

输入一系列整数,建立二叉排序数,并进行前序,中序,后序遍历。 

输入描述:

输入第一行包括一个整数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 <iostream>
#include <cstdio> 
using namespace std;

//节点 
struct Node {
	int val;
	Node *left, *right;
	Node(int v) {
		val = v;
		left = NULL;
		right = NULL;
	}
};

//向根节点 root 的 数中 插入 节点权值为v 的节点 
void insert(Node* &root, int v) {
	//如果节点为空,表示已经找到插入位置 
	if (root == NULL) {
		root = new Node(v);
		return;
	}

	
	if (root->val == v) return;	//去重


	if (root->val > v) insert(root->left, v);
	else insert(root->right, v);
}

void inOrder(Node* root) {
	if (!root) return;
	inOrder(root->left);
	printf("%d ", root->val);
	inOrder(root->right);
}

void preOrder(Node *root) {
	if (!root) return;
	printf("%d ", root->val);
	preOrder(root->left);
	preOrder(root->right);
}

void postOrder(Node *root) {
	if (!root) return;
	postOrder(root->left);
	postOrder(root->right);
	printf("%d ", root->val);
}
int main(int argc, char *argv[]) {
	int n;
	Node *root;
	while (scanf("%d", &n) != EOF) {
		root = NULL;
		while (n--) {
			int t;
			scanf("%d", &t);
			insert(root, t);
		}
		preOrder(root);
		printf("\n");
		inOrder(root);
		printf("\n");
		postOrder(root);
		printf("\n");
	}
	return 0;
}

 

© 著作权归作者所有

共有 人打赏支持
粉丝 21
博文 877
码字总数 630930
作品 0
西安
二叉树知识点回忆以及整理

二叉树 在计算机科学中,二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”和“右子树”,左子树和右子树同时也是二叉树。二叉树的子树有左右之分,并且次序不能任意颠倒。...

静默加载 ⋅ 2017/10/19 ⋅ 0

深入学习二叉树(四) 二叉排序树

1 前言 数据结构中,线性表分为无序线性表和有序线性表。 无序线性表的数据是杂乱无序的,所以在插入和删除时,没有什么必须遵守的规则,可以插入在数据尾部或者删除在数据尾部。但是在查找的...

进击的Hello_World ⋅ 05/14 ⋅ 0

JavaScript 二叉搜索树以及实现翻转二叉树

本文包括:二叉搜索树(创建、遍历、搜索、插入等)、JavaScript 实现翻转二叉树 欢迎关注我的:个人博客、Github。 什么是二叉树? 二叉树的定义:二叉树的每个结点至多只有二棵子树(不存在...

CaiJinyc ⋅ 06/10 ⋅ 0

【6】判断整数序列是不是二元查找树的后序遍历结果

/* 判断整数序列是不是二元查找树的后序遍历结果 题目:输入一个整数数组,判断该数组是不是某二元查找树的后序遍历的结果。 如果是返回true,否则返回false。 例如输入5、7、6、9、11、10、...

SibylY ⋅ 2016/07/31 ⋅ 0

小蚂蚁学习数据结构(32)——二叉排序树的概念

二叉排序树,定义: 1,若左子树非空,则左子树上所有节点的关键字均小于根节点关键字。 2,若右子树非空,则右子树上所有节点的关键字均大于根节点关键字。 3,左右子树本身又是一颗二叉树。...

嗜学如命的小蚂蚁 ⋅ 2016/02/07 ⋅ 0

面试算法知识梳理(13) - 二叉树算法第三部分

面试算法代码知识梳理系列 面试算法知识梳理(1) - 排序算法 插入排序 希尔排序 选择排序 冒泡排序 计数排序 基数排序 归并排序 快速排序 双向扫描的快速排序 堆排序 面试算法知识梳理(2) - 字...

泽毛 ⋅ 2017/12/22 ⋅ 0

【判断两棵二叉排序树是否相同】数据结构实验之查找一:二叉排序树

Think: 1知识点:判断两棵二叉排序树是否相同 2判断依据: (1):根节点相同 (2):(rt1的左子树 == rt2的左子树 且 rt1的右子树 == rt2的右子树) || (rt1的左子树 == rt2的右子树 且 rt1的...

blessingxry ⋅ 2017/12/13 ⋅ 0

检查是否为BST(二叉查找树(或二叉排序树、二叉搜索树))

1、题目内容 题目描述 请实现一个函数,检查一棵二叉树是否为二叉查找树。 给定树的根结点指针TreeNode root,请返回一个bool,代表该树是否为二叉查找树。 2、题目解析 方法1:因为二叉查找...

笨拙的小Q ⋅ 2016/04/20 ⋅ 0

算法知识梳理(10) - 二叉查找树

面试算法代码知识梳理系列 算法知识梳理(1) - 排序算法 算法知识梳理(2) - 字符串算法第一部分 算法知识梳理(3) - 字符串算法第二部分 算法知识梳理(4) - 数组第一部分 算法知识梳理(5) - 数...

泽毛 ⋅ 2017/12/18 ⋅ 0

数据结构-二叉搜索树的实现

定义 二叉搜索树(Binary Search Tree,BST),也称为二叉排序树或二叉查找树。 相较于普通的二叉树,非空的二叉搜索树有如下性质: 非空左子树的所有键值小于其根结点的键值; 非空右子树的所有...

IAM四十二 ⋅ 2017/10/27 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

mysql in action / alter table

change character set ALTER SCHEMA `employees` DEFAULT CHARACTER SET utf8mb4 DEFAULT COLLATE utf8mb4_general_ci ;ALTER TABLE `employees`.`t2` CHARACTER SET = utf8mb4 , COLLAT......

qwfys ⋅ 今天 ⋅ 0

Java 开发者不容错过的 12 种高效工具

Java 开发者常常都会想办法如何更快地编写 Java 代码,让编程变得更加轻松。目前,市面上涌现出越来越多的高效编程工具。所以,以下总结了一系列工具列表,其中包含了大多数开发人员已经使用...

jason_kiss ⋅ 昨天 ⋅ 0

Linux下php访问远程ms sqlserver

1、安装freetds(略,安装在/opt/local/freetds 下) 2、cd /path/to/php-5.6.36/ 进入PHP源码目录 3、cd ext/mssql进入MSSQL模块源码目录 4、/opt/php/bin/phpize生成编译配置文件 5、 . ./...

wangxuwei ⋅ 昨天 ⋅ 0

如何成为技术专家

文章来源于 -- 时间的朋友 拥有良好的心态。首先要有空杯心态,用欣赏的眼光发现并学习别人的长处,包括但不限于工具的使用,工作方法,解决问题以及规划未来的能力等。向别人学习的同时要注...

长安一梦 ⋅ 昨天 ⋅ 0

Linux vmstat命令实战详解

vmstat命令是最常见的Linux/Unix监控工具,可以展现给定时间间隔的服务器的状态值,包括服务器的CPU使用率,内存使用,虚拟内存交换情况,IO读写情况。这个命令是我查看Linux/Unix最喜爱的命令...

刘祖鹏 ⋅ 昨天 ⋅ 0

MySQL

查看表相关命令 - 查看表结构    desc 表名- 查看生成表的SQL    show create table 表名- 查看索引    show index from  表名 使用索引和不使用索引 由于索引是专门用于加...

stars永恒 ⋅ 昨天 ⋅ 0

easyui学习笔记

EasyUI常用控件禁用方法 combobox $("#id").combobox({ disabled: true }); ----- $("#id").combobox({ disabled: false}); validatebox $("#id").attr("readonly", true); ----- $("#id").r......

miaojiangmin ⋅ 昨天 ⋅ 0

金山WPS发布了Linux WPS Office

导读 近日,金山WPS发布了Linux WPS Office中文社区版新版本,支持大部分主流Linux系统,功能更加完善,兼容性、稳定性大幅度提升。本次更新WPS将首次在Linux提供专业办公文件云存储服务,实...

问题终结者 ⋅ 昨天 ⋅ 0

springboot2输出metrics到influxdb

序 本文主要研究一下如何将springboot2的metrics输出到influxdb maven <dependency> <groupId>org.springframework.boot</groupId> <artifactId>spring-bo......

go4it ⋅ 昨天 ⋅ 0

微信小程序 - 选择图片显示操作菜单

之前我分享过选择图片这个文章,但是我在实际开发测试使用中发现一个问题在使用 wx.chooseImage 选择照片显示出第一格是拍照,后面是相册里的图片。这种实现之前说过了,效果如下。 但是你从...

hello_hp ⋅ 昨天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部