Trong bài toán này, chúng ta được đưa ra một cây nhị phân và chúng ta phải in nó ra mặt phẳng hai chiều.
Cây nhị phân là một cây đặc biệt mà mỗi nút có tối đa hai nút con. Vì vậy, mọi nút đều là nút lá hoặc có một hoặc hai nút con.
Ví dụ,
Hãy lấy một ví dụ để hiểu rõ hơn về chủ đề -
Đầu ra -
7 4 5 1 3 8
Bây giờ như chúng ta đã thấy trong ví dụ, các nút của cây được in trong màn hình xuất 2-D theo chiều ngang.
Ở đây, chúng tôi đã lật cây 90o.
Hãy xem cây ngang mới được tạo thành như thế nào,
-
Cấu trúc dữ liệu cây được lưu trữ theo chiều ngang bao gồm
-
Gốc ở vị trí đầu tiên trong chế độ xem ngang n dòng bên dưới dòng bắt đầu. tức là thư mục gốc sẽ ở đầu dòng thứ n.
-
Các cấp độ mới của cây nằm ở dòng n + i và n-i. Và ở tab tôi khoảng cách từ đầu dòng.
-
Và nút lá ngoài cùng bên phải của cây được in ở dòng đầu tiên. Trong khi nút ngoài cùng bên trái của cây được in ở dòng cuối cùng.
-
Ví dụ
Hãy tạo một chương trình dựa trên logic này -
#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;
} Đầu ra
16 97 59 67 13 26 29 43 31 51 7 25 49 14 81