1099. Build A Binary Search Tree (30)[bst二叉搜索树]

2023-12-02 15:58

本文主要是介绍1099. Build A Binary Search Tree (30)[bst二叉搜索树],希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

1. 原题: https://www.patest.cn/contests/pat-a-practise/1099

2. 思路:

题意:
给出二叉搜索树的结构及结点的值,求出层序序列。
思路:
首先我们要知道BST的中序是升序序列,这样的话,我们就知道了
BST的中序序列。
所以有多种方法。可以构建树,然后再中序遍历同时回填元素值。
也可以不用,因为已经知道了结构,可以用数组模拟二叉树的形式中序遍历,再回填值。
最后用队列层序输出。
这里用第二个简便些。
已AC。

3. 源码:

#include<iostream>
#include<vector>
#include<algorithm>//使用sort函数
#include<queue>
using namespace std;struct Node
{int val;//该结点的值int left, right;//分别为左右结点的编号
};
int N, index = 0;//分别为结点数,中序遍历时的索引
vector<Node> T;//数组表示二叉树
vector<int> inor;//存储中序遍历的序列void levelTraversal(int root);//层序遍历输出
void Inorder(int root);//中序遍历给结点赋值int main(void)
{//freopen("in.txt", "r", stdin);cin >> N;T.resize(N);//数组表示二叉树inor.resize(N);//存储中序遍历的序列for (int i = 0; i < N; i++)//读入数据cin >> T[i].left >> T[i].right;for (int i = 0; i < N; i++)cin >> inor[i];sort(inor.begin(), inor.end());//升序Inorder(0);//中序遍历给结点赋值levelTraversal(0);//层序遍历输出return 0;
}void Inorder(int root)//递归中序遍历给结点赋值
{if (root == -1)//递归结束条件return;Inorder(T[root].left);//遍历左结点T[root].val = inor[index++];//赋值Inorder(T[root].right);//遍历右结点return;
}void levelTraversal(int root)//层序遍历输出
{queue<int> Q;Q.push(root);cout << T[root].val;while (!Q.empty()){int id = Q.front();Q.pop();if (T[id].left != -1){Q.push(T[id].left);cout << ' ' << T[T[id].left].val;}if (T[id].right != -1){Q.push(T[id].right);cout << ' ' << T[T[id].right].val;}}cout << endl;return;
}


这篇关于1099. Build A Binary Search Tree (30)[bst二叉搜索树]的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/445929

相关文章

认识、理解、分类——acm之搜索

普通搜索方法有两种:1、广度优先搜索;2、深度优先搜索; 更多搜索方法: 3、双向广度优先搜索; 4、启发式搜索(包括A*算法等); 搜索通常会用到的知识点:状态压缩(位压缩,利用hash思想压缩)。

hdu1240、hdu1253(三维搜索题)

1、从后往前输入,(x,y,z); 2、从下往上输入,(y , z, x); 3、从左往右输入,(z,x,y); hdu1240代码如下: #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#inc

30常用 Maven 命令

Maven 是一个强大的项目管理和构建工具,它广泛用于 Java 项目的依赖管理、构建流程和插件集成。Maven 的命令行工具提供了大量的命令来帮助开发人员管理项目的生命周期、依赖和插件。以下是 常用 Maven 命令的使用场景及其详细解释。 1. mvn clean 使用场景:清理项目的生成目录,通常用于删除项目中自动生成的文件(如 target/ 目录)。共性规律:清理操作

uva 575 Skew Binary(位运算)

求第一个以(2^(k+1)-1)为进制的数。 数据不大,可以直接搞。 代码: #include <stdio.h>#include <string.h>const int maxn = 100 + 5;int main(){char num[maxn];while (scanf("%s", num) == 1){if (num[0] == '0')break;int len =

MCU7.keil中build产生的hex文件解读

1.hex文件大致解读 闲来无事,查看了MCU6.用keil新建项目的hex文件 用FlexHex打开 给我的第一印象是:经过软件的解释之后,发现这些数据排列地十分整齐 :02000F0080FE71:03000000020003F8:0C000300787FE4F6D8FD75810702000F3D:00000001FF 把解释后的数据当作十六进制来观察 1.每一行数据

2024网安周今日开幕,亚信安全亮相30城

2024年国家网络安全宣传周今天在广州拉开帷幕。今年网安周继续以“网络安全为人民,网络安全靠人民”为主题。2024年国家网络安全宣传周涵盖了1场开幕式、1场高峰论坛、5个重要活动、15场分论坛/座谈会/闭门会、6个主题日活动和网络安全“六进”活动。亚信安全出席2024年国家网络安全宣传周开幕式和主论坛,并将通过线下宣讲、创意科普、成果展示等多种形式,让广大民众看得懂、记得住安全知识,同时还

hdu 4517 floyd+记忆化搜索

题意: 有n(100)个景点,m(1000)条路,时间限制为t(300),起点s,终点e。 访问每个景点需要时间cost_i,每个景点的访问价值为value_i。 点与点之间行走需要花费的时间为g[ i ] [ j ] 。注意点间可能有多条边。 走到一个点时可以选择访问或者不访问,并且当前点的访问价值应该严格大于前一个访问的点。 现在求,从起点出发,到达终点,在时间限制内,能得到的最大

AI基础 L9 Local Search II 局部搜索

Local Beam search 对于当前的所有k个状态,生成它们的所有可能后继状态。 检查生成的后继状态中是否有任何状态是解决方案。 如果所有后继状态都不是解决方案,则从所有后继状态中选择k个最佳状态。 当达到预设的迭代次数或满足某个终止条件时,算法停止。 — Choose k successors randomly, biased towards good ones — Close

hdu4277搜索

给你n个有长度的线段,问如果用上所有的线段来拼1个三角形,最多能拼出多少种不同的? import java.io.BufferedInputStream;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStream;import java.io.InputStreamReader;

树(Tree)——《啊哈!算法》

树 什么是树?树是一种特殊的图,不包含回路的连通无向树。 正因为树有着“不包含回路”这个特点,所以树就被赋予了很多特性。 一棵树中的任意两个结点有且仅有唯一的一条路径连通。一棵树如果有n个结点,那么它一定恰好有n-1条边。在一棵树中加一条边将会构成一个回路。 一棵树有且只有一个根结点。 没有父结点的结点称为根结点(祖先)。没有子结点的结点称为叶结点。如果一个结点既不是根结点也不是叶