ในบทช่วยสอนนี้ เราจะพูดถึงโปรแกรมเพื่อพิมพ์โหนดทั้งหมดที่ปรากฏในมุมมองด้านบนของไบนารีทรีที่กำหนด
สำหรับไบนารีทรีเฉพาะ โหนดจะปรากฏในมุมมองด้านบน หากเป็นโหนดแรกที่ระยะห่างในแนวนอน ระยะทางแนวนอนสำหรับโหนดด้านซ้ายของโหนด x คือ x-1 และสำหรับโหนดด้านขวาของโหนด x คือ x+1
เพื่อแก้ปัญหานี้ เราจะทำการข้ามระดับเพื่อที่เราจะได้โหนดบนสุดสำหรับระดับใดระดับหนึ่ง ก่อนที่โหนดอื่นจะอยู่ที่ระดับนั้น นอกจากนี้ เราจะใช้การแฮชเพื่อตรวจสอบว่าโหนดที่เลือกนั้นมองเห็นได้ในมุมมองด้านบนหรือไม่
ตัวอย่าง
#include <iostream>
#include<queue>
#include<map>
using namespace std;
struct Node{
Node * left;
Node* right;
int h_dist;
int data;
};
Node* create_node(int key){
Node* node=new Node();
node->left = node->right = NULL;
node->data=key;
return node;
}
void print_topview(Node* root){
if(root==NULL)
return;
queue<Node*>q;
map<int,int> m;
int h_dist=0;
root->h_dist=h_dist;
q.push(root);
cout<< "Top View for the given tree:" << endl;
while(q.size()){
h_dist=root->h_dist;
if(m.count(h_dist)==0)
m[h_dist]=root->data;
if(root->left){
root->left->h_dist=h_dist-1;
q.push(root->left);
}
if(root->right){
root->right->h_dist=h_dist+1;
q.push(root->right);
}
q.pop();
root=q.front();
}
for(auto i=m.begin();i!=m.end();i++){
cout<<i->second<< " ";
}
}
int main(){
Node* root = create_node(11);
root->left = create_node(23);
root->right = create_node(35);
root->left->right = create_node(47);
root->left->right->right = create_node(59);
root->left->right->right->right = create_node(68);
print_topview(root);
return 0;
} ผลลัพธ์
Top View for the given tree: 23 11 35 68
