Tổng đường chéo của một cây nhị phân trong C ++?

Để xem xét các nút đang đi qua giữa các đường có độ dốc -1. Tổng đường chéo của cây nhị phân sẽ được tính bằng tổng của tất cả dữ liệu nút có mặt giữa các dòng tham chiếu này.

Đầu tiên chúng ta hãy xác định cấu trúc đại diện cho một nút cây chứa dữ liệu và nút con trái và phải của nó. Nếu đây là nút đầu tiên được tạo thì đó là nút gốc, ngược lại là nút con.

Nút

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

Tiếp theo, chúng ta tạo hàm createNode (int data) của chúng ta, lấy một giá trị int và gán nó cho thành viên dữ liệu của nút sau khi tạo nút mới. Hàm trả về con trỏ đến nút đã tạo.

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

Tiếp theo, Diagonal_sum (Node * root, int depth, map &DiagonalSum) lấy nút gốc, độ sâu hiện tại và bản đồ DiagonalSum làm tham chiếu. Nếu gốc không phải là NULL thì chúng tôi thêm dữ liệu gốc hiện tại vào chỉ mục độ sâu hiện tại trong bản đồ DiagonalSum để lấy tổng các phần tử. con trái.

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);
   }
}

Bên trong chức năng chính của chúng tôi, chúng tôi tạo một cây bằng cách sử dụng phương thức createNode (dữ liệu) và cũng tạo một bản đồ SumMap. Nút gốc, độ sâu hiện tại là 1 và Bản đồ sumMap được gửi đến đường chéo_sum nơi Bản đồ tổng hợp chứa đầy cặp khóa-giá trị. Tiếp theo, chúng tôi tạo trình lặp của chúng tôi, nó để lặp qua bản đồ sumMap.

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;

Cuối cùng, chúng tôi lặp lại trên Bản đồ SumM của chúng tôi bằng cách sử dụng trình lặp nó bên trong vòng lặp for của chúng tôi và in các tổng theo đường chéo.

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

Ví dụ

Hãy để chúng tôi xem cách triển khai sau đây để tìm tổng đường chéo của cây nhị phân.

#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;
}

Đầu ra

Đoạn mã trên sẽ tạo ra kết quả sau -