C++에서 이진 트리의 대각선 순회?

기울기 -1의 선 사이를 통과하는 노드를 고려합니다. 이진 트리의 대각선 순회는 이 선 사이에 있는 모든 노드를 순회하고 인쇄하는 것입니다.

먼저 데이터와 왼쪽 및 오른쪽 노드 자식을 포함하는 트리 노드를 나타내는 구조체를 정의하겠습니다. 이것이 생성될 첫 번째 노드이면 루트 노드이고 그렇지 않으면 자식 노드입니다.

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

다음으로 int 값을 취하여 노드의 데이터 멤버에 할당하는 createNode(int 데이터) 함수를 만듭니다. 함수는 생성된 구조체 노드에 대한 포인터를 반환합니다. 또한 새로 생성된 노드의 왼쪽과 오른쪽 자식은 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> &myMap) 함수는 루트 노드, 현재 깊이, int 값을 키로, int 벡터를 값으로 갖는 맵을 취합니다. 이 함수에 대한 참조로 myMap을 전달합니다. 그런 다음 이 함수는 루트가 null인지 여부를 확인하고 그렇지 않은 경우 중위 순회를 수행할 때 현재 깊이에서 벡터 데이터 구조의 뒤쪽에 있는 루트->데이터 요소를 푸시합니다.

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을 선언합니다. 그런 다음 이 맵은 루트 노드 및 현재 깊이와 함께 traverseDiagonal로 전달됩니다.

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

지도 myMap이 값으로 채워진 후 루프 기반 범위를 사용하여 반복하고 해당 대각선 값을 인쇄합니다.

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