C++を使用してバイナリツリーの上面図にノードを印刷するプログラム

このチュートリアルでは、特定の二分木の上面図に表示されるすべてのノードを印刷するプログラムについて説明します。

特定の二分木では、ノードが水平距離の最初のノードである場合、そのノードが上面図に表示されます。ノード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