代码网站模板怎么做,企业门户网站开发,网站域名是什么东西,网页游戏开发需要学什么【题目来源】https://www.acwing.com/problem/content/1552/【题目描述】二叉搜索树 (BST) 递归定义为具有以下属性的二叉树#xff1a; #xff08;1#xff09;若它的左子树不空#xff0c;则左子树上所有结点的值均小于它的根结点的值 #xff08;2#xff09;若它的右…【题目来源】https://www.acwing.com/problem/content/1552/【题目描述】二叉搜索树 (BST) 递归定义为具有以下属性的二叉树 1若它的左子树不空则左子树上所有结点的值均小于它的根结点的值 2若它的右子树不空则右子树上所有结点的值均大于或等于它的根结点的值 3它的左、右子树也分别为二叉搜索树完全二叉树 (CBT) 定义为除最深层外的其他层的结点数都达到最大个数最深层的所有结点都连续集中在最左边的二叉树。 现在给定 N 个不同非负整数表示 N 个结点的权值用这 N 个结点可以构成唯一的完全二叉搜索树。 请你输出该完全二叉搜索树的层序遍历。【输入格式】 第一行包含整数 N表示结点个数。 第二行包含 N 个不同非负整数表示每个结点的权值。【输出格式】 共一行输出给定完全二叉搜索树的层序遍历序列。【数据范围】 1≤N≤1000, 结点权值不超过 2000。【输入样例】 10 1 2 3 4 5 6 7 8 9 0【输出样例】 6 3 8 1 5 7 9 0 2 4【算法分析】 ● 二叉搜索树BSTBinary Search Tree 二叉搜索树的形态与给定的序列值及顺序相关。也就是说即便序列的值相同但依据“左小右大”的原则不同的次序也会生成不同形态的二叉搜索树。 452453123793 122437455393
● 完全二叉树 如果在一棵具有n个结点的二叉树中它的逻辑结构与满二叉树的前n个结点的逻辑结构相同则称这样的二叉树为完全二叉树。显然在完全二叉树中结点 u 的左孩子为 2*u右孩子为 2*u1。 ● 二叉搜索树具有一个重要的性质即它的中序遍历序列是递增的。那又如何据此性质输出二叉搜索树的层序遍历序列呢 对二叉搜索树的结点值进行递增排序然后执行类似于中序遍历的 dfs 操作并在 dfs 过程中将对应的二叉搜索树结点值存入一个中序数组中之后输出中序数组便可得到所求的二叉搜索树的层序遍历序列。【算法代码】
#include bits/stdc.h
using namespace std;const int maxn1010;
int a[maxn],in[maxn];
int n,idx;void dfs(int u) { //inorderif(u*2n) dfs(u*2);in[u]a[idx];if(u*21n) dfs(u*21);
}int main() {cinn;for(int i0; in; i) cina[i];sort(a,an);dfs(1); //is 1,not 0. Otherwise,dfs cant run.for(int i1; in; i) coutin[i] ;return 0;
}/*
in:
10
1 2 3 4 5 6 7 8 9 0out:
6 3 8 1 5 7 9 0 2 4
*/【参考文献】https://blog.csdn.net/justinzengTM/article/details/81459482https://www.acwing.com/solution/content/11649/https://www.acwing.com/solution/content/97469/
