C ++での二分木の対角トラバーサル？

勾配-1の線の間を通過するノードを検討します。二分木の対角トラバーサルは、これらの線の間に存在するすべてのノードをトラバースして印刷することです。

まず、データとその左右のノードの子を含むツリーノードを表す構造体を定義しましょう。これが最初に作成されるノードの場合はルートノード、それ以外の場合は子ノードです。

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

次に、int値を取得してノードのデータメンバーに割り当てるcreateNode（int data）関数を作成します。この関数は、作成された構造体ノードへのポインターを返します。また、新しく作成されたノードの左右の子はnullに設定されます。

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

traverseDiagonal（Node * root、intdepth、map >＆myMap）関数は、ルートノード、現在の深度、およびint値をキーとして、intのベクトルを値として持つマップを取得します。この関数への参照としてmyMapを渡します。次に、この関数はルートがnullかどうかをチェックし、nullでない場合は、要素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);

次に、メイン関数で、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を宣言します。次に、このマップは、ルートノードと現在の深度とともに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){
      m[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