PAT甲级1099 Build A Binary Search Tree (30分)：[C++题解]建立二叉搜索树、dfs和bfs

本文主要是介绍PAT甲级1099 Build A Binary Search Tree (30分)：[C++题解]建立二叉搜索树、dfs和bfs，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目分析

题意重述：给定一棵二叉树的结构，和待填的数值，请将数据填到二叉树中的结点中，使之满足二叉搜索树的性质。 然后按照层序遍历输出数值。

分析：
本题分两步。

第一步是按照二叉搜索树来建树；二叉搜索树有个很好的性质，就是它的中序遍历是从小到大有序的，所有这就是我们的切入点！ 我们就 dfs按照树的中序遍历来往里填数，这样构造出来的就是二叉搜索树。

第二步是层序遍历。二叉树的层序遍历就是bfs。

具体操作的时候，这里用到了 l 和r两个数组，从根结点开始一路存下来每个结点的左儿子和右儿子。便于dfs和bfs。
ac代码

#include<bits/stdc++.h>
using namespace std;const int N = 110;int n;
int l[N] ,r[N]; //左儿子数组，右儿子数组。
int q[N]; //数组模拟队列，用于bfs()
int a[N] ,w[N];  //a存储读入的数值， w存储每个结点实际存的哪个数void dfs(int u, int& k){if(u == -1) return;dfs(l[u], k);w[u] = a[k++];//中序遍历，每个结点得到权值dfs(r[u], k);
}//层序遍历，就是广度优先搜索
void bfs(){int hh =0 ,tt =0;q[0] =0;while(hh <= tt){int t = q[hh++];if(l[t] != -1)  q[++tt] =l[t];if(r[t] != -1) q[++tt] = r[t];}//输出层序遍历cout<<w[q[0]];for(int i=1; i<n; i++) cout<<" "<<w[q[i]];
}int main(){cin>> n;for( int i = 0 ;i< n; i++) cin>> l[i] >> r[i];for(int i =0; i< n; i++) cin>> a[i];sort(a, a + n ); //二叉排序树的中序遍历序列，从小到大int k = 0;dfs(0, k); //dfs 按照中序遍历的顺序，往里填数据bfs(); //层序遍历}

题目链接

PAT甲级1099 Build A Binary Search Tree (30分)

这篇关于PAT甲级1099 Build A Binary Search Tree (30分)：[C++题解]建立二叉搜索树、dfs和bfs的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---