文章目錄

• • 題目分析
  • 題目鏈接

題目分析

題意重述：給定一棵二叉樹的結構，和待填的數值，請將數據填到二叉樹中的結點中，使之滿足二叉搜索樹的性質。 然后按照層序遍歷輸出數值。

分析：
本題分兩步。

第一步是按照二叉搜索樹來建樹；二叉搜索樹有個很好的性質，就是它的中序遍歷是從小到大有序的，所有這就是我們的切入點！ 我們就 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的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。