アルゴ式（beta版）の「さまざまなデータ構造 (#毎日アルゴ式)」9章:二分木 (二分探索木、ヒープ) からの出典です。
algo-method.com
アルゴ式とは...
>・プログラミングや情報科学をコツコツ学べる「教科書」
>・学んだ内容をゲーム感覚で大量に実践できる「練習問題」
>の２つで構成される、Web上で完結した学習コンテンツです。
C++による「さまざまなデータ構造 (#毎日アルゴ式)」9章:二分木 (二分探索木、ヒープ)
僕が作成、提出したコードは、以下のとおりです。
Q1. 二分木の通りがけ順
/* C++による「さまざまなデータ構造 (#毎日アルゴ式)」9章:二分木 (二分探索木、ヒープ) Q1. 二分木の通りがけ順 https://algo-method.com/tasks/913 提出コードの解答例 https://neguse-atama.hatenablog.com */ #include<bits/stdc++.h> using namespace std; using ll=long long; vector<ll> num; void f(ll v,vector<ll> &l,vector<ll> &r){ if(l[v]!=-1){ f(l[v],l,r); } num.push_back(v); if(r[v]!=-1){ f(r[v],l,r); } } int main(void){ ll n; cin>>n; vector<ll> l(n),r(n); for(ll i=0;i<n;i++){ cin>>l[i]>>r[i]; } f(0,l,r); for(ll i=0;i<n;i++){ cout<<num[i]<<(i==n-1 ? "\n" : " "); } return 0; }
Q3. 二分探索木への挿入 (2)
/* C++による「さまざまなデータ構造 (#毎日アルゴ式)」9章:二分木 (二分探索木、ヒープ) Q3. 二分探索木への挿入 (2) https://algo-method.com/tasks/918 提出コードの解答例 https://neguse-atama.hatenablog.com */ #include<bits/stdc++.h> using namespace std; using ll=long long; struct Node{ Node* parent; Node* left; Node* right; ll val; Node(const ll& val=0):val(val){ parent=nullptr; left=nullptr; right=nullptr; } }; Node* root=new Node(); void insert(Node* node_a){ ll a=node_a->val; Node* par,*next=root; while(next){ par=next; if(a<=par->val){ next=par->left; }else{ next=par->right; } } if(a<=par->val){ node_a->parent=par; par->left=node_a; }else{ node_a->parent=par; par->right=node_a; } } vector<ll> num; void f(Node* node){ num.push_back(node->val); if(node->left){ f(node->left); } if(node->right){ f(node->right); } } int main(void){ ll q; cin>>q; for(ll i=0;i<q;i++){ ll v; cin>>v; if(i==0){ root->val=v; continue; } Node *node_a=new Node(v); insert(node_a); } f(root); assert(num.size()==q); for(ll i=0;i<q;i++){ cout<<num[i]<<((i==q-1) ? "\n" : " "); } return 0; }
Q4. 二分探索木のキー検索
/* C++による「さまざまなデータ構造 (#毎日アルゴ式)」9章:二分木 (二分探索木、ヒープ) Q4. 二分探索木のキー検索 https://algo-method.com/tasks/919 提出コードの解答例 https://neguse-atama.hatenablog.com */ #include<bits/stdc++.h> using namespace std; using ll=long long; struct Node{ Node* parent; Node* left; Node* right; ll val; Node(const ll& val=0):val(val){ parent=nullptr; left=nullptr; right=nullptr; } }; Node *root=new Node(-1); void insert(Node *node_a){ ll a=node_a->val; Node* par,*next=root; while(next){ par=next; if(a<=par->val){ next=par->left; }else{ next=par->right; } } if(a<=par->val){ node_a->parent=par; par->left=node_a; }else{ node_a->parent=par; par->right=node_a; } } bool tf(ll v){ Node *now=root; while(now){ if(now->val==v){ return true; } if(v<=now->val){ now=now->left; }else{ now=now->right; } } return false; } int main(void){ ll q; cin>>q; for(ll i=0;i<q;i++){ ll num,v; cin>>num>>v; if(num==0){ Node *node_v=new Node(v); insert(node_v); }else{ if(tf(v)){ cout<<"Yes"<<endl; }else{ cout<<"No"<<endl; } } } return 0; }
Q7. 強平衡二分木の頂点数
/* C++による「さまざまなデータ構造 (#毎日アルゴ式)」9章:二分木 (二分探索木、ヒープ) Q7. 強平衡二分木の頂点数 https://algo-method.com/tasks/922 提出コードの解答例 https://neguse-atama.hatenablog.com */ #include<bits/stdc++.h> using namespace std; using ll=long long; int main(void){ ll h; cin>>h; ll mini=1; for(ll i=0;i<h;i++){ mini*=2; } ll maxi=2*mini-1; cout<<mini<<" "<<maxi<<endl; return 0; }
Q8. 完全二分木の頂点番号
/* C++による「さまざまなデータ構造 (#毎日アルゴ式)」9章:二分木 (二分探索木、ヒープ) Q8. 完全二分木の頂点番号 https://algo-method.com/tasks/923 提出コードの解答例 https://neguse-atama.hatenablog.com */ #include<bits/stdc++.h> using namespace std; using ll=long long; int main(void){ ll h; cin>>h; ll n=1; for(ll i=0;i<=h;i++){ n*=2; } n--; ll q; cin>>q; for(ll i=0;i<q;i++){ ll t,v; cin>>t>>v; ll ans=-1; if(t==0){ if(v!=0){ ans=(v-1)/2; } }else if(t==1){ ans=2*v+1; if(ans>=n){ ans=-1; } }else{ ans=2*(v+1); if(ans>=n){ ans=-1; } } cout<<ans<<endl; } return 0; }
Q9. ヒープかどうか
/* C++による「さまざまなデータ構造 (#毎日アルゴ式)」9章:二分木 (二分探索木、ヒープ) Q9. ヒープかどうか https://algo-method.com/tasks/924 提出コードの解答例 https://neguse-atama.hatenablog.com */ #include<bits/stdc++.h> using namespace std; using ll=long long; int main(void){ ll n; cin>>n; vector<ll> a(n); for(ll i=0;i<n;i++){ cin>>a[i]; } bool tf=true; for(ll i=1;i<n;i++){ ll j=(i-1)/2; if(a[j]<a[i]){ tf=false; } } cout<<(tf ? "Yes" : "No")<<endl; return 0; }
Q10. ヒープへの挿入
/* C++による「さまざまなデータ構造 (#毎日アルゴ式)」9章:二分木 (二分探索木、ヒープ) Q10. ヒープへの挿入 https://algo-method.com/tasks/925 提出コードの解答例 https://neguse-atama.hatenablog.com */ #include<bits/stdc++.h> using namespace std; using ll=long long; int main(void){ ll q; cin>>q; vector<ll> heap; for(ll i=0;i<q;i++){ ll v; cin>>v; heap.push_back(v); ll j=i; while(j>0){ ll par=(j-1)/2; if(heap[par]<heap[j]){ swap(heap[par],heap[j]); j=par; }else{ break; } } } for(ll i=0;i<heap.size();i++){ cout<<heap[i]<<((i==heap.size()-1) ? "\n" : " "); } return 0; }
Q11. ヒープからの削除
/* C++による「さまざまなデータ構造 (#毎日アルゴ式)」9章:二分木 (二分探索木、ヒープ) Q11. ヒープからの削除 https://algo-method.com/tasks/926 提出コードの解答例 https://neguse-atama.hatenablog.com */ #include<bits/stdc++.h> using namespace std; using ll=long long; int main(void){ ll q; cin>>q; vector<ll> heap; for(ll i=0;i<q;i++){ ll num; cin>>num; if(num==0){ ll v; cin>>v; heap.push_back(v); ll j=heap.size()-1; while(j>0){ ll par=(j-1)/2; if(heap[par]<heap[j]){ swap(heap[par],heap[j]); j=par; }else{ break; } } }else{ ll ans=heap[0]; cout<<ans<<endl; heap[0]=heap.back(); heap.pop_back(); ll j=heap.size(); ll k=0; while(k<j){ ll l=2*k+1,r=2*(k+1); ll tf=0; ll maxi=heap[k]; if(l<j && heap[l]>maxi){ maxi=heap[l]; tf=1; } if(r<j && heap[r]>maxi){ maxi=heap[r]; tf=2; } if(tf==0){ break; }else if(tf==1){ swap(heap[k],heap[l]); k=l; }else{ swap(heap[k],heap[r]); k=r; } } } } return 0; }
Q12. タスクリスト (3)
/* C++による「さまざまなデータ構造 (#毎日アルゴ式)」9章:二分木 (二分探索木、ヒープ) Q12. タスクリスト (3) https://algo-method.com/tasks/927 提出コードの解答例 https://neguse-atama.hatenablog.com */ #include<bits/stdc++.h> using namespace std; using ll=long long; using lls=tuple<ll,ll,string>; int main(void){ ll q; cin>>q; priority_queue<lls,vector<lls>,greater<lls>> pq; for(ll i=0;i<q;i++){ ll num; cin>>num; if(num==0){ ll d;string s; cin>>d>>s; pq.emplace(d,i,s); }else{ auto [d,j,s]=pq.top(); pq.pop(); cout<<s<<endl; } } return 0; }
設問の出典は、情報科学をコツコツ積み立てて学習できるサービス「アルゴ式（beta版）」です。
algo-method.com
