数算二叉搜索树的层次遍历树-程序员宅基地

技术标签：数算

二叉搜索树的层次遍历
题目内容：二叉搜索树在动态查表中有特别的用处，一个无序序列可以通过构造一棵二叉搜索树变成一个有序序列，构造树的过程即为对无序序列进行排序的过程。每次插入的新的结点都是二叉搜索树上新的叶子结点，在进行插入操作时，不必移动其它结点，只需改动某个结点的指针，由空变为非空即可。
这里，我们想探究二叉树的建立和层次输出。

输入格式:
只有一行，包含若干个数字，中间用空格隔开。（数字可能会有重复，对于重复的数字，只计入一个）

输出格式：
输出一行，对输入数字建立二叉搜索树后进行按层次周游的结果。

输入样例：
51 45 59 86 45 4 15 76 60 20 61 77 62 30 2 37 13 82 19 74 2 79 79 97 33 90 11 7 29 14 50 1 96 59 91 39 34 6 72 7

输出样例：
51 45 59 4 50 86 2 15 76 97 1 13 20 60 77 90 11 14 19 30 61 82 96 7 29 37 62 79 91 6 33 39 74 34 72

#include <iostream>
#include <algorithm>
#include <deque>
using namespace std;

struct treepoint
{
 int info;
 treepoint* leftchild;
 treepoint* rightchild;
 treepoint()
 {
  leftchild = NULL;
  rightchild = NULL;
  info = 0;
 }
};

void insert(int n, treepoint* root)
{
 if (n > root->info)
 {
  if (root->rightchild == NULL)
  {
   root->rightchild = new treepoint;
   root->rightchild->info = n;
   return;
  }
  insert(n, root->rightchild);
 }
 else
 {
  if (root->leftchild == NULL)
  {
   root->leftchild = new treepoint;
   root->leftchild->info = n;
   return;
  }
  insert(n, root->leftchild);
 }
}

deque<treepoint*> s;
void my_print(treepoint* root)
{
 cout << root->info;
 if (root->leftchild != NULL)
  s.push_back(root->leftchild);
 if (root->rightchild != NULL)
  s.push_back(root->rightchild);
 if (!s.empty())
 {
  cout << " ";
  treepoint* next = s.front();
  s.pop_front();
  my_print(next);
 }
}

int visited[1000] = { 0 };

int main()
{
 int n;
 cin >> n;
 treepoint* root = new treepoint;
 root->info = n;
 visited[n] = 1;
 while (cin >> n)
 {
  if (visited[n] == 1)
   continue;
  visited[n] = 1;
  insert(n, root);
 }
 my_print(root);
 cout << endl;
 return 0;
}

本文链接：https://blog.csdn.net/weixin_41412558/article/details/84337924

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

flask-标准类视图及其使用场景_flask 类视图应用场景-程序员宅基地

文章浏览阅读1.3k次。继承自flask.view.View,返回基于Response或其自类的对象from flask import Flask,viewsapp = Flask(__name__)class Listview(views.View): def dispatch_request(self): return 'list view'app.add_url_rule('/l..._flask 类视图应用场景

cocos内存管理机制_cocos内存是怎么管理的-程序员宅基地

文章浏览阅读1.5k次，点赞2次，收藏7次。在cocos2dx-3.8中的自动内存管理机制是借助引用计数来实现的。对于老版本的cocos引用计数使用的是CCObject，但是这个类在后面就被弃用了，使用Ref来代替，cocos内几乎所有的类都是继承自Ref。 Ref基本的原理就是其内部存在一个引用计数_referenceCount，当这个引用计数为0的时候，就会被释放。引用计数通过retain，release来操作。Ref从创建到销毁的过_cocos内存是怎么管理的

使用LeanCloud服务做一站式Chrome插件开发——Favorite Image-程序员宅基地

文章浏览阅读68次。0. 目录要开发的是什么项目1.1 想法开端1.2 应该有什么功能?开发需要解决的核心问题具体解决方案3.1 帐号系统3.2 存储服务3.3 使用`LeanEngine`做反防盗链中转接口3.4 Chrome 插件实现对去后端化的看法1. 要开发的是什么项目?一个Chrome插件，用来保存浏览网页时看到...

为什么5000+企业放弃Sonatype，选择JFrog Artifactory_sonartype nexus jfrog-程序员宅基地

文章浏览阅读1.2k次。一、背景制品，artifact，也称为工件，是指在构建或持续集成过程中从源码创建而成的二进制包，而这些二进制包通常是通过赋予其的版本号来唯一定位和管理的。制品仓库，artifact repository，则是存储和管理这些版本化的二进制包，并对外提供检索和访问方法的应用程序。制品仓库通常分为中央仓库、企业仓库和本地仓库。中央仓库面向公众开放，存储和管理预先构建好的二进制包，通常提供软件开发..._sonartype nexus jfrog

米利型和摩尔型状态机-程序员宅基地

文章浏览阅读5.8k次，点赞3次，收藏7次。2019独角兽企业重金招聘Python工程师标准>>> ..._摩尔机和米利机

书籍《Python股票量化交易从入门到实践》学习进阶路线-程序员宅基地

文章浏览阅读2.1w次，点赞35次，收藏181次。#Python高阶# && #数据处理# #数据库# ------主题目录-------1 数据处理篇【含数据库、爬虫相关】：提取搭建系统过程中，出现的各种数据处理场景，讲解对应的解决方法。主题内容如下：【1-1 除权与复权走势的对比】【1-2 解决warning：A value is trying to be set on a copy of a slice from a DataFrame】【1-3 difference方法找出不重复的Dataframe】【1-4 使用pd.m_python股票量化交易从入门到实践