การข้ามเส้นทแยงมุมของ Binary Tree ใน C ++?

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

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

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

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

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 เพื่ออ้างอิงถึงฟังก์ชันนี้ จากนั้นฟังก์ชันจะตรวจสอบว่ารูทเป็นโมฆะหรือไม่ และหากไม่ใช่ เราจะผลักองค์ประกอบรูท->ข้อมูลที่ด้านหลังโครงสร้างข้อมูลเวกเตอร์ของเราที่ระดับความลึกปัจจุบันในขณะที่เราทำการข้ามผ่านแบบไม่เรียงลำดับ

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

จากนั้นเราประกาศแผนที่ myMap ที่มี int เป็นคีย์และเวกเตอร์ของ int เป็นค่า แผนที่นี้จะถูกส่งต่อไปยัง 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