目的

mark一下紫書上的例題與操作，以備復習。

---

內容

各種套路

UVa 122

#include <bits/stdc++.h> using namespace std; char s[1007]; struct Node {bool have_value; int v;Node *left,*right;Node():have_value(false),left(NULL),right(NULL){} }; bool failed; Node* root; Node* newnode() { return new Node();} void remove_tree(Node* u) {if(u == NULL) return;remove_tree(u->left);remove_tree(u->right);delete u; } void addnode(int v,char* s) {int n=strlen(s);Node* u=root; //根節點 for(int i=0;i<n;i++){if(s[i]=='L'){if(u->left==NULL) u->left=newnode();u=u->left; //向左走 }else if(s[i]=='R'){if(u->right==NULL) u->right=newnode();u=u->right;}}if(u->have_value) failed=true;u->v =v;u->have_value=true; } bool read_input() {failed=false;root=newnode();for(;;){if(scanf("%s",s) != 1) return false;if(!strcmp(s,"()")) break;int v;sscanf(&s[1],"%d",&v);addnode(v,strchr(s,',')+1); }return true; } bool bfs(vector<int>& ans) {queue<Node*> q;ans.clear();q.push(root);while(!q.empty()){Node* u=q.front(); q.pop();if(!u->have_value) return false;ans.push_back(u->v);if(u->left != NULL) q.push(u->left);if(u->right != NULL) q.push(u->right);}return true; } int main() {vector<int> ans;while(read_input()){if(!bfs(ans)) failed = 1;if(failed) printf("not complete\n");else {for(int i = 0; i < ans.size(); i++){if(i != 0) printf(" ");printf("%d", ans[i]);}puts("");}}return 0; }

---

UVa 548

#include <bits/stdc++.h> using namespace std; const int maxv=10009; int in_order[maxv],post_order[maxv],lch[maxv],rch[maxv],n; bool read_list(int* a) {string line;if(!getline(cin,line)) return false;stringstream ss(line);n=0;int x;while(ss>>x) a[n++]=x;return n>0; } //把in_order[L1,R1]和post_order[L2,R2]建成一顆二叉樹，返回樹根 int build(int L1,int R1,int L2,int R2) {if(L1>R1) return 0;int root=post_order[R2];int p=L1;while(in_order[p] != root) p++; int cnt=p-L1;lch[root]=build(L1,p-1,L2,L2+cnt-1);rch[root]=build(p+1,R1,L2+cnt,R2-1);return root; } long long best,best_sum; void dfs(int u,long long sum) {sum+=u;if(!lch[u] && !rch[u])if(sum<best_sum || (sum==best_sum && u<best)){best=u;best_sum=sum;}if(lch[u]) dfs(lch[u],sum);if(rch[u]) dfs(rch[u],sum); } int main() {while(read_list(in_order)){read_list(post_order);build(0,n-1,0,n-1);best_sum=1000000000000;dfs(post_order[n-1],0);cout<<best<<"\n";}return 0; }

---

UVa 839

#include <iostream> using namespace std; int solve(int& W) {int B1=1,B2=1,W1,W2,D1,D2;cin>>W1>>D1>>W2>>D2;if(!W1) B1=solve(W1);if(!W2) B2=solve(W2);W=W1+W2;if(B1&&B2&&W1*D1==W2*D2) return 1;return 0; } int main() {int T,W;cin>>T;while(T--){if(solve(W)) cout<<"YES\n";else cout<<"NO\n";if(T) cout<<"\n";}return 0; }

---

UVa 10562

#include <bits/stdc++.h> using namespace std; const int maxn=210; int n; char buf[maxn][maxn]; void dfs(int r,int c) {printf("%c(",buf[r][c]);if(r+1<n && buf[r+1][c]=='|'){int i=c;while(i-1>=0 && buf[r+2][i-1]=='-') i--;while(buf[r+2][i]=='-' && buf[r+3][i]!='\0'){if(!isspace(buf[r+3][i])) dfs(r+3,i);i++;}}printf(")"); } void solve() {n=0;for(;;){fgets(buf[n],maxn,stdin);if(buf[n][0]=='#') break;else n++;}printf("(");if(n){for(int i=0;i<strlen(buf[0]);i++)if(buf[0][i]!=' '){dfs(0,i); break;}}printf(")\n"); } int main() {int T;fgets(buf[0],maxn,stdin);sscanf(buf[0],"%d",&T);while(T--){solve();}return 0; }

轉載于:https://www.cnblogs.com/noblex/p/7978910.html

總結

以上是生活随笔為你收集整理的【学习笔记】树形结构基础的全部內容，希望文章能夠幫你解決所遇到的問題。

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