題目

輸入一個樹狀天平，根據力矩相等原則判斷是否平衡。如圖6-5所示，所謂力矩相等，就是WlDl=WrDr，其中Wl和Wr分別為左右兩邊砝碼的重量，D為距離。采用遞歸（先序）方式輸入：每個天平的格式為Wl，Dl，Wr，Dr，當Wl或Wr為0時，表示該“砝碼”實際是一個子天平，接下來會描述這個子天平。當Wl=Wr=0時，會先描述左子天平，然后是右子天平。

樣例輸入：

1
0 2 0 4
0 3 0 1
1 1 1 1
2 4 4 2
1 6 3 2

輸出
YES

分析與解答

劉汝佳說要完全理解這個程序，那我就把遞歸過程寫了一下

輸入采用先序，并且輸入順序剛好就是遞歸的順序，那就可以在輸入過程進行判斷
對每個結點判斷，如果有子節點，那么就要判斷左右子樹是否平衡，以及這個樹本身是否平衡，b1為true說明左子樹平衡，b2右子樹，w1是左邊子天平所有砝碼的總重量，w2右邊。（w1*d1==w2*d2）說明這個樹平衡。由于solv函數采用傳引用方式，所以，每次那一層的函數返回時，w1和w2都已經分別賦為那個子樹所有重量的和

#include<iostream> using namespace std;bool solve(int &w) {int w1,d1,w2,d2;bool b1=true,b2=true;cin>>w1>>d1>>w2>>d2;if(!w1) b1=solve(w1);if(!w2) b2=solve(w2);w=w1+w2;return b1&&b2&&(w1*d1==w2*d2); }int main(){int t,w;cin>>t;while(t--){if(solve(w)) cout<<"YES\n";else cout<<"NO\n";if(t) cout<<"\n";} }

總結

以上是生活随笔為你收集整理的(二叉树DFS)天平UVa 839的全部內容，希望文章能夠幫你解決所遇到的問題。

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