PAT A1064 Complete Binary Search Tree [完全二叉搜索树]

「爱情、让人受尽委屈。」 2021-10-23 09:51 219阅读 0赞

## 题目描述 ##

[链接][Link 1]  
给一串构成树的序列，已知该树是完全二叉搜索树，求它的层序遍历的序列

## 分析 ##

*  二叉搜索树的性质：左子树<根<右子树，而中序遍历是LDR，所以：**中序遍历二叉搜索树得到的序列是从小到大排列的**
 *  完全二叉树的性质：**在数组中的存储顺序是层序遍历完全二叉树的顺序**
 *  混淆概念：要唯一确定一棵二叉树，一般需要先后序中一个和中序一起。不存在什么中序遍历建立二叉树。根本就不唯一好吧。但是在这里，由于限定了完全二叉搜索树，则可以借助中序遍历来对数组赋值。
 *  将题目所给序列进行排序，得到中序遍历顺序。而中序遍历，实质是按照LDR访问根结点。我们可以把访问这个操作改成赋值\\(nodes\[root\]=a\[len++\]\\) ，从而得到数组中的存储顺序。最后进行输出该顺序，即为层序遍历顺序。
 *  总结：排序-->改造中序遍历程序，将访问变成赋值-->得到数组存储顺序-->得到层序遍历顺序
 *  完全二叉树：结点为空：\\(i>n\\) 结点为叶子：\\(2i>n\\)

#include<bits/stdc++.h> using namespace std; const int maxn = 1e4+10; int nodes[maxn]; int n,len; int a[maxn]; void inorder(int root){ if(root > n) return; inorder(2*root); nodes[root] = a[len++]; //将访问改成赋值 inorder(2*root+1); } int main(){ cin>>n; for(int i=0;i<n;i++) cin>>a[i]; sort(a,a+n); inorder(1); for(int i=1;i<=n;i++){ if(i==1) cout<<nodes[i]; else cout<<" "<<nodes[i]; } cout<<endl; }

转载于:https://www.cnblogs.com/doragd/p/11280181.html

[Link 1]: https://pintia.cn/problem-sets/994805342720868352/problems/994805407749357568