ผลรวมในแนวทแยงของไบนารีทรีใน C ++?

พิจารณาโหนดที่ผ่านระหว่างเส้นความชัน -1 ผลรวมในแนวทแยงของไบนารีทรีจะคำนวณโดยผลรวมของข้อมูลโหนดทั้งหมดที่มีอยู่ระหว่างบรรทัดอ้างอิงเหล่านี้

ให้เรากำหนดโครงสร้างที่จะเป็นตัวแทนของโหนดต้นไม้ที่มีข้อมูลและโหนดลูกของโหนดซ้ายและขวา หากนี่เป็นโหนดแรกที่สร้างขึ้น แสดงว่าเป็นโหนดรูท มิฉะนั้นจะเป็นโหนดย่อย

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

ต่อไป เราสร้างฟังก์ชัน createNode(int data) ที่ใช้ค่า int และกำหนดให้กับสมาชิกข้อมูลของโหนดหลังจากสร้างโหนดใหม่ ฟังก์ชันจะส่งกลับตัวชี้ไปยังโหนดที่สร้างขึ้น

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

ถัดไป diagonal_sum(โหนด *root, int depth, map &diagonalSum) รับโหนดรูท ความลึกปัจจุบัน และแผนที่ diagonalSum โดยการอ้างอิง หากรูทไม่ใช่ค่า NULL เราจะเพิ่มข้อมูลรูทปัจจุบันไปยังดัชนีความลึกปัจจุบันในแผนที่ diagonalSum เพื่อรับผลรวมขององค์ประกอบ จากนั้นเราจะทำการข้ามผ่านแบบไม่เรียงลำดับแบบเรียกซ้ำบนทรี และเพิ่ม 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 จะถูกส่งไปยัง diagonal_sum โดยที่ sumMap เต็มไปด้วยคู่คีย์-ค่า ต่อไป เราสร้าง iterator เพื่อวนซ้ำบนแผนที่ 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;

สุดท้ายเราวนซ้ำบน SumMap โดยใช้ตัววนซ้ำภายใน for ของเราและพิมพ์ผลรวมในแนวทแยง

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