พิมพ์ Binary Tree ใน 2 มิติใน C++

ในปัญหานี้ เราได้รับไบนารีทรี และเราต้องพิมพ์ระนาบสองมิติออกมา

Binary Tree เป็นต้นไม้พิเศษที่ทุกโหนดมีโหนดย่อยสูงสุดสองโหนด ดังนั้น ทุกโหนดจึงเป็นโหนดปลายสุดหรือมีโหนดย่อยหนึ่งหรือสองโหนด

ตัวอย่าง

มาดูตัวอย่างเพื่อทำความเข้าใจหัวข้อกันดีกว่า −

พิมพ์ Binary Tree ใน 2 มิติใน C++

ผลลัพธ์ -

ดังที่เราได้เห็นในตัวอย่างแล้ว โหนดของต้นไม้ถูกพิมพ์ในหน้าจอเอาต์พุต 2 มิติในแนวนอน

ที่นี่เราพลิกต้นไม้ไปประมาณ 90o

เรามาดูกันว่าต้นไม้แนวนอนใหม่ประกอบด้วยอะไร

โครงสร้างข้อมูลต้นไม้ถูกจัดเก็บในลักษณะแนวนอนซึ่งรวมถึง
- รากที่ตำแหน่งที่ 1 ในมุมมองแนวนอน n เส้นใต้เส้นเริ่มต้น นั่นคือ root จะอยู่ที่จุดเริ่มต้นของบรรทัดที่ n
- ระดับใหม่ของต้นไม้อยู่ในบรรทัด n+i และ n-i และที่ i เว้นวรรคห่างจากจุดเริ่มต้นของบรรทัด
- และโหนดใบขวาสุดของต้นไม้จะถูกพิมพ์ในบรรทัดแรก โดยที่โหนดซ้ายสุดของต้นไม้จะพิมพ์อยู่ที่บรรทัดสุดท้าย

ตัวอย่าง

มาสร้างโปรแกรมตามตรรกะนี้กันเถอะ -

#include<bits/stdc++.h>
#include<iostream>
using namespace std;
#define COUNT 10
class Node{
   public:
      int data;
      Node* left, *right;
      Node(int data){
         this->data = data;
         this->left = NULL;
         this->right = NULL;
      }
};
void printTree(Node *root, int space){
   if (root == NULL)
      return;
   space += COUNT;
   printTree(root->right, space);
   for (int i = COUNT; i < space; i++)
      cout<<"\t";
   cout<<root->data<<"\n";
   printTree(root->left, space);
}
int main(){
   Node *root = new Node(43);
   root->left = new Node(25);
   root->right = new Node(67);
   root->left->left = new Node(14);
   root->left->right = new Node(51);
   root->right->left = new Node(26);
   root->right->right = new Node(97);
   root->left->left->left = new Node(81);
   root->left->left->right = new Node(49);
   root->left->right->left = new Node(07);
   root->left->right->right = new Node(31);
   root->right->left->left = new Node(29);
   root->right->left->right = new Node(13);
   root->right->right->left = new Node(59);
   root->right->right->right = new Node(16);
   printTree(root, 0);
   return 0;
}

ผลลัพธ์