C++에서 수준별로 이진 트리 수준의 데이터 인쇄
- 큐를 사용하여 이진 트리의 데이터를 C++ 수준별로 인쇄하는 알고리즘 작성
- 연결 목록 노드를 사용하여 C++에서 수준별로 이진 트리 수준의 데이터 인쇄
- 해싱 기술을 사용하여 C++에서 수준별로 이진 트리 수준의 데이터 인쇄
이진 트리 수준별 순회는 Breadth-first 순회라고 합니다. 이 자습서에서는 C++에서 수준별로 이진 트리의 데이터를 인쇄하는 방법을 설명하고 이 작업을 수행하는 다양한 방법에 익숙해집니다.
대기열을 사용하는 것은 스택이 깊이 우선 순회를 위한 것이기 때문에 수준별로 이진 트리 수준에서 데이터를 인쇄하는 적절한 방법입니다. 그러나 이 목표를 달성하기 위한 세 가지 다른 방법이 있습니다. 대기열(또는 연결된 목록 노드)을 사용하여 고유한 알고리즘을 작성하거나 해싱 기술을 사용하는 것입니다.
큐를 사용하여 이진 트리의 데이터를 C++ 수준별로 인쇄하는 알고리즘 작성
C++에서는 #include<queue>를 포함하여 큐의 기능을 사용하여 이진 트리의 데이터를 레벨별로 정렬된 순서로 출력하는 알고리즘을 작성할 수 있습니다. 대기열이 FIFO(선입선출 원칙)를 따르므로 대기열을 초기화하고 루트를 푸시해야 합니다.
논리 알고리즘을 작성하고 입력 이진 트리에 적용하면 null 노드를 사용할 수 있습니다(newline으로 노드를 구분). null 노드와의 상호 작용은 방문하지 않은 노드가 현재 수준에 남아 있지 않음을 의미하며 newline을 인쇄할 수 있습니다.
각 이진 트리 수준의 끝에는 끝을 나타내는 null 노드가 있어야 합니다. 노드 유형의 데이터를 저장하기 위해 큐를 초기화하고 루트에 루트를 푸시하고 마지막으로 null 노드를 큐에 푸시하면 null 노드를 레벨에 삽입할 수 있습니다.
#include <iostream>
#include <queue>
using namespace std;
class binT_node {
public:
int nodeData;
// declare left and right nodes of the binary tree
binT_node* left;
binT_node* right;
binT_node(int data, binT_node* lef, binT_node* rig) {
nodeData = data;
left = lef;
right = rig;
}
};
void print_dataT(binT_node* root) {
queue<binT_node*> que;
que.push(root);
while (true) {
int orderLength = que.size();
if (orderLength == 0) {
break;
}
int i = 0;
while (i < orderLength) {
binT_node* nod = que.front();
cout << (nod->nodeData) << " ";
if (nod->left != NULL) {
que.push(nod->left);
}
if (nod->right != NULL) {
que.push(nod->right);
}
que.pop();
i++;
}
cout << endl;
}
}
int main() {
binT_node* rootNode;
rootNode = new binT_node(1, NULL, NULL);
rootNode->left = new binT_node(2, NULL, NULL);
rootNode->right = new binT_node(3, NULL, NULL);
rootNode->left->left = new binT_node(4, NULL, NULL);
rootNode->left->right = new binT_node(5, NULL, NULL);
rootNode->right->left = new binT_node(6, NULL, NULL);
rootNode->right->right = new binT_node(7, NULL, NULL);
print_dataT(rootNode);
return 0;
}
출력:
1
2 3
4 5 6 7
각 반복에서 하나의 노드를 인쇄하는 대신 한 반복에서 동일한 수준의 노드를 인쇄하는 것이 가능하며 이는 C++에서 유사한 알고리즘을 작성하는 또 다른 잘 알려진 접근 방식입니다.
이 접근 방식은 큐를 초기화하고 root 및 null 노드를 큐에 푸시하는 것을 포함하여 첫 번째 접근 방식과 약간 유사합니다.
또한 temp가 null이 아니면 노드 temp의 값을 인쇄하고 null이 아니면 temp.left를 대기열에 푸시하고 null이 아니면 temp.right를 대기열에 푸시하고 반복합니다. 대기열이 비어 있을 때까지의 단계.
연결 목록 노드를 사용하여 C++에서 수준별로 이진 트리 수준의 데이터 인쇄
노드를 방문하여 하위 노드를 FIFO 대기열에 넣는 것은 대기열을 연결된 목록으로 구현할 수도 있기 때문에 표준 접근 방식입니다. 그러나 C++의 함수를 사용하여 이진 트리의 현재 수준을 인쇄할 수 있습니다.
먼저 연결된 목록 노드의 ArrayList를 생성하여 이진 트리의 레벨 순회를 위해 queue(BFS)를 사용합니다. 변수는 대기열 크기를 저장할 수 있으며 각 이진 트리 수준에서 모든 노드를 검색하고 조작하는 데 유용합니다.
이제 대기열 크기를 저장하는 변수가 0보다 큰 동안 변수에 액세스하고 대기열에 자식을 추가하여 모든 노드를 검색, 인쇄 또는 조작합니다.
이 재귀 솔루션은 완벽하게 작동하지만 대기열이나 해싱 기술만큼 효과적이지는 않습니다.
#include <iostream>
using namespace std;
class listNode {
public:
int data;
listNode *left, *right;
};
void print_data(listNode* root_node, int level_order);
int lev_height(listNode* node);
listNode* updatedNode(int data);
void printData_LevelOrder(listNode* root_node) {
int heig = lev_height(root_node);
int init;
for (init = 1; init <= heig; init++) print_data(root_node, init);
}
void print_data(listNode* root_node, int level_order) {
// in case of a `null` or empty root
if (root_node == NULL) return;
// in case if root represents `1`
if (level_order == 1) cout << root_node->data << " ";
// in case the root is greater than `1`
else if (level_order > 1) {
print_data(root_node->left, level_order - 1);
print_data(root_node->right, level_order - 1);
}
}
int lev_height(listNode* node_linkedlist) {
// in case of empty or `NULL`
if (node_linkedlist == NULL)
return 0;
else {
int level_leftHeight = lev_height(node_linkedlist->left);
int level_rightHeight = lev_height(node_linkedlist->right);
// in case the left node is greater than the right node
if (level_leftHeight > level_rightHeight) {
return (level_leftHeight + 1);
}
// in case the right node is greater than the left node
else {
return (level_rightHeight + 1);
}
}
}
listNode* updatedNode(int _listdata) {
listNode* list_node = new listNode();
list_node->data = _listdata;
list_node->left = NULL;
list_node->right = NULL;
return (list_node);
}
int main() {
listNode* linkedlistNode = updatedNode(1);
linkedlistNode->left = updatedNode(2);
linkedlistNode->right = updatedNode(3);
linkedlistNode->left->left = updatedNode(4);
linkedlistNode->left->right = updatedNode(5);
cout << "Level by Level Data Insertion to a Binary Tree is Complete! \n";
printData_LevelOrder(linkedlistNode);
return 0;
}
출력:
Level by Level Data Insertion to a Binary Tree is Complete!
1 2 3 4 5
printLevelOrder 및 printCurrentLevel은 각각 주어진 수준의 모든 노드를 인쇄하거나 이진 트리의 수준 순회를 인쇄하는 이 접근 방식(연결된 목록을 사용하여 이진 트리의 데이터 인쇄)의 하위 기능입니다. .
또한 printLevelOrder 하위 기능은 printCurrentLevel 기능을 활용하여 이진 트리의 모든 수준에서 루트부터 시작하여 노드를 하나씩 인쇄할 수 있습니다.
Breath-First Search(BFS)의 시간 복잡도는 O(n^2)입니다. 여기서 n은 이진 트리 노드의 최대 수를 나타내고 O(h)는 필요한 보조 공간입니다. h가 이진 트리의 전체 높이를 나타내는 C++ 프로그램.
이 자습서에서 찾을 각 알고리즘은 다음을 포함하여 모든 유형의 이진 트리를 처리할 수 있습니다. 전체, 완전, 완전, 퇴화 또는 병리, 편향 및 균형 이진 트리.
해싱 기술을 사용하여 C++에서 수준별로 이진 트리 수준의 데이터 인쇄
해싱 기법의 일환으로 해시 테이블은 수준별로 이진 트리의 데이터를 인쇄할 수 있으며 평균적으로 해시 테이블의 조회 시간 O(1)을 차지하는 매우 유용한 데이터 구조임이 입증되었습니다.
시간 복잡성을 줄이기 위해 알고리즘 및 이진 데이터 구조와 관련된 여러 문제를 매우 효율적으로 해결할 수 있습니다.
해싱에는 단일 키를 여러 값에 매핑하고 이진 트리 노드와 해당 수준을 저장하는 데 사용하는 멀티맵이 포함됩니다.
해싱 기법은 변수에 저장된 이진 트리 레벨 번호를 키로 사용하여 부모 노드 또는 이진 트리의 첫 번째 레벨부터 각 레벨에 해당하는 모든 노드를 인쇄합니다.
#include <iostream>
// associative container that contains key-value pairs
// search, insert and remove elements in average constant-time complexity
#include <unordered_map>
#include <vector> // initialize the vector contents
using namespace std;
// data structure creation | fulfill the purpose of storing data in a binary
// table
struct _hashnode {
int key;
_hashnode *left, *right;
// `key` -> `_nodekey` will contain all the binary tree info to arrange the
// nodes
_hashnode(int _nodekey) {
this->key = _nodekey;
this->left = this->right = nullptr;
}
};
// enable nodes storage in a map (to traverse the tree in a pre_order fashion)
// corresponding to the node's level
void hash_preorder(_hashnode* hash_root, int level, auto& map) {
// initially: empty binary table
if (hash_root == nullptr) {
return;
}
// current node and its level insertion into the map
map[level].push_back(hash_root->key);
hash_preorder(hash_root->left, level + 1, map);
hash_preorder(hash_root->right, level + 1, map);
}
// recursive function | fulfill the purpose of printing binary tree's level
// order traversal
void traversal_throughHash(_hashnode* hash_root) {
// creation of a `null` or an empty map | to store nodes between the given
// levels of a binary tree
unordered_map<int, vector<int>> map;
/* level-wise insertion of nodes to the map after the tree traversal */
hash_preorder(hash_root, 1, map);
for (int init = 1; map[init].size() > 0; init++) {
cout << "[Binary Tree] Level " << init << ":- ";
for (int juan : map[init]) {
cout << juan << " ";
}
cout << endl;
}
}
int main() {
_hashnode* hash_Root = new _hashnode(15);
hash_Root->left = new _hashnode(10);
hash_Root->right = new _hashnode(20);
hash_Root->left->left = new _hashnode(8);
hash_Root->left->right = new _hashnode(12);
hash_Root->right->left = new _hashnode(16);
hash_Root->right->right = new _hashnode(25);
hash_Root->right->right->right = new _hashnode(30);
traversal_throughHash(hash_Root);
return 0;
}
출력:
[Binary Tree] Level 1:- 15
[Binary Tree] Level 2:- 10 20
[Binary Tree] Level 3:- 8 12 16 25
[Binary Tree] Level 4:- 30
일반적으로 이진 트리는 최상위 노드가 부모 또는 루트 노드이고 각 부모 노드가 한 쌍의 자식 노드를 나타내는 데이터 구조 역할을 합니다.
이진 트리 순회에는 네 가지 일반적인 방법이 있으며 수준별 순서 순회가 가장 효율적인 방법 중 하나입니다.
비교를 통한 정렬을 기반으로 하는 어떤 알고리즘도 n log n 성능보다 더 잘 수행할 수 없다는 것은 사실입니다. 이진 티의 각 노드는 하위 노드(ai ≤ aj) 간의 비교를 나타내며 n! 중 하나를 나타냅니다.
이진 트리에는 n = (2^h) - 1 노드가 포함됩니다. 여기서 h는 이진 트리의 높이를 나타내며 리프가 아닌 모든 노드에는 오른쪽 및 왼쪽 자식 노드가 모두 있습니다.
n!이 있는 트리에 대해 h = [log(n!)]를 계산하여 이진 트리의 높이를 결정할 수 있습니다. 리프 노드 및 h = log(n + 1) 높이.
Hassan is a Software Engineer with a well-developed set of programming skills. He uses his knowledge and writing capabilities to produce interesting-to-read technical articles.
GitHub