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

기울기 -1의 선 사이를 통과하는 노드를 고려합니다. 이진 트리의 대각 합은 이 기준선 사이에 있는 모든 노드 데이터의 합으로 계산됩니다.

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

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

다음으로 int 값을 취하여 새 노드를 만든 후 노드의 데이터 멤버에 할당하는 createNode(int 데이터) 함수를 만듭니다. 함수는 생성된 노드에 대한 포인터를 반환합니다.

Node * createNode(int data){
   Node * node = new Node;
   node->data = data;
   return node;
}

다음으로,diagonal_sum(Node *root, int depth, map &diagonalSum)은 루트 노드, 현재 깊이 및 대각선Sum 맵을 참조로 가져옵니다. 루트가 NULL이 아니면 현재 루트 데이터를 대각선합 맵의 현재 깊이 인덱스에 추가하여 요소의 합을 얻습니다. 그런 다음 트리에서 재귀적 중위 순회를 수행하고 다음으로 이동할 때마다 깊이에 1을 추가합니다. 왼쪽 아이.

void diagonal_sum(Node *root, int depth, map<int, int> &diagonalSum){
   if(root){
      diagonalSum[depth]+=root->data;
      diagonal_sum(root->leftChild, depth+1, diagonalSum);
      diagonal_sum(root->rightChild, depth, diagonalSum);
   }
}

메인 함수 내에서 createNode(data) 메소드를 사용하여 트리를 생성하고 SumMap 맵도 생성합니다. 루트 노드, 1인 현재 깊이 및 sumMap은 sumMap이 키-값 쌍으로 채워지는 대각선_sum으로 전송됩니다. 다음으로 sumMap 맵을 반복하기 위해 iterator를 생성합니다.

int main(){
   Node *root = createNode(1);
   root->rightChild = createNode(3);
   root->rightChild->leftChild = createNode(4);
   root->rightChild->leftChild->leftChild = createNode(12);
   root->rightChild->leftChild->rightChild = createNode(7);
   root->leftChild = createNode(2);
   root->leftChild->leftChild = createNode(9);
   root->leftChild->rightChild = createNode(6);
   root->leftChild->leftChild->rightChild = createNode(10);
   root->leftChild->rightChild->leftChild = createNode(11);
   root->rightChild->rightChild = createNode(5);
   map<int,int> sumMap;
   diagonal_sum(root, 1, sumMap);
   map<int,int>::iterator it;

마지막으로 for 루프 내에서 iterator를 사용하여 SumMap을 반복하고 대각선 합계를 인쇄합니다.

for(it=sumMap.begin(); it!=sumMap.end();++it){
   int value = it->second;
   cout<<value<<"\t";
}

예시

이진 트리의 대각 합을 찾는 다음 구현을 살펴보겠습니다.

#include<iostream>
#include<map>
using namespace std;
struct Node{
   int data;
   struct Node* leftChild, *rightChild;
};
Node * createNode(int data){
   Node * node = new Node;
   node->data = data;
   return node;
}
void diagonal_sum(Node *root, int depth, map<int, int> &diagonalSum){
   if(root){
      diagonalSum[depth]+=root->data;
      diagonal_sum(root->leftChild, depth+1, diagonalSum);
      diagonal_sum(root->rightChild, depth, diagonalSum);
   }
}
int main(){
   Node *root = createNode(1);
   root->rightChild = createNode(3);
   root->rightChild->leftChild = createNode(4);
   root->rightChild->leftChild->leftChild = createNode(12);
   root->rightChild->leftChild->rightChild = createNode(7);
   root->leftChild = createNode(2);
   root->leftChild->leftChild = createNode(9);
   root->leftChild->rightChild = createNode(6);
   root->leftChild->leftChild->rightChild = createNode(10);
   root->leftChild->rightChild->leftChild = createNode(11);
   root->rightChild->rightChild = createNode(5);
   map<int,int> sumMap;
   diagonal_sum(root, 1, sumMap);
   map<int,int>::iterator it;
   for(it=sumMap.begin(); it!=sumMap.end();++it){
      int value = it->second;
      cout<<value<<"\t";
   }
   return 0;
}

출력

위의 코드는 다음 출력을 생성합니다 -

91942