C++で二分木の対角走査（ダイアゴナル・トラバーサル）を実装する方法

二分木の対角走査とは

二分木の対角走査（Diagonal Traversal）は、傾き-1の直線を基準に考えます。同じ直線上に位置するノード同士をひとつのグループとして捉え、これらの対角線ごとにノードをたどりながらすべて出力していくのが対角走査です。

まず、データと左右の子ノードへのポインタを持つツリーノードを表す構造体を定義します。最初に作成されたノードはルートノードとなり、それ以降に作成されるノードは子ノードとして扱われます。

struct Node {
   int data;
   struct Node *leftChild, *rightChild;
};

次に、createNode(int data)関数を作成します。この関数はint型の値を受け取り、ノードのdataメンバに代入します。戻り値として作成したNode構造体へのポインタを返し、新しく生成されたノードの左の子と右の子はNULLに設定されます。

struct Node* newNode(int data){
   struct Node* node = new Node();
   node->data = data;
   node->leftChild = node->rightChild = NULL;
   return node;
}

traverseDiagonal(Node* root, int depth, map<int, vector<int>> &myMap)関数は、ルートノード、現在の深さ、そして「キーがint値・値がint型ベクトル」であるマップを受け取ります。myMapは参照渡しされる点に注意してください。関数内部では、rootがNULLかどうかを判定し、NULLでない場合は中順走査（inorder traversal）を行いながら、現在の深さに対応するベクトルの末尾へroot->dataを追加していきます。

void traverseDiagonal(Node* root, int depth, map<int, vector<int>> &m){
   if(root){
      m[depth].push_back(root->data);

その後、対角距離を追跡しながら木を再帰的に中順走査します。左の子をたどる際には深さに1を加算し、右の子をたどる際には深さを変更しません。これにより、同じ対角線上にあるノードが同じ深さ（キー）にまとめられます。

traverseDiagonal(root->leftChild, depth+1, myMap);
traverseDiagonal(root->rightChild, depth, myMap);

続いて、main関数の中でcreateNode(data)関数を使って二分木を構築します。

Node *root = createNode(10);
   root->leftChild = createNode(5);
   root->rightChild = createNode(15);
   root->leftChild->leftChild = createNode(4);
   root->leftChild->rightChild = createNode(6);
   root->rightChild->rightChild = createNode(17);
   root->rightChild->rightChild->leftChild = createNode(16);

次に、キーとしてint、値としてint型ベクトルを持つマップmyMapを宣言します。このマップは、ルートノードと初期深度0とともにtraverseDiagonalへ渡されます。

map<int, vector<int>> myMap;
traverseDiagonal(root, 0, myMap);

マップmyMapへの格納が完了したら、範囲ベースforループで反復処理を行い、対角線ごとの値を出力します。

for(auto k: myMap){
   for(auto Nodes: k.second)
      cout<<Nodes<<" ";
      cout<<endl;
}

サンプルコード

以下に、二分木の対角走査を実行する完全な実装例を示します。

#include <iostream>
#include <map>
#include <vector>
using namespace std;
struct Node{
   int data;
   Node *leftChild, *rightChild;
};
Node* createNode(int data){
   Node* node = new Node();
   node->data = data;
   node->leftChild = node->rightChild = NULL;
   return node;
}
void traverseDiagonal(Node* root, int depth, map<int, vector<int>> &myMap){
   if(root){
      myMap[depth].push_back(root->data);
      traverseDiagonal(root->leftChild, depth+1, myMap);
      traverseDiagonal(root->rightChild, depth, myMap);
   }
}
int main(){
   Node *root = createNode(10);
   root->leftChild = createNode(5);
   root->rightChild = createNode(15);
   root->leftChild->leftChild = createNode(4);
   root->leftChild->rightChild = createNode(6);
   root->rightChild->rightChild = createNode(17);
   root->rightChild->rightChild->leftChild = createNode(16);
   map<int, vector<int>> myMap;
   traverseDiagonal(root, 0, myMap);
   for(auto k: myMap){
      for(auto Nodes: k.second)
         cout<<Nodes<<" ";
      cout<<endl;
   }
}

出力結果

上記のコードを実行すると、次の出力が得られます。

10 15 17
5 6 16
4