blob: 61f8bb159444cc140934074b5dfdf40930336ab6 (
plain) (
blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
|
#include <iostream>
#include <queue>
#include <algorithm>
template <typename T>
struct TreeNode {
T data;
TreeNode* left;
TreeNode* right;
TreeNode(const T& val) : data(val), left(nullptr), right(nullptr) {}
};
// Preorder обхождане (корен, ляво, дясно)
template <typename T>
void preorderTraversal(TreeNode<T>* root) {
if (!root) return;
std::cout << root->data << " ";
preorderTraversal(root->left);
preorderTraversal(root->right);
}
// Inorder обхождане (ляво, корен, дясно)
template <typename T>
void inorderTraversal(TreeNode<T>* root) {
if (!root) return;
inorderTraversal(root->left);
std::cout << root->data << " ";
inorderTraversal(root->right);
}
// Postorder обхождане (ляво, дясно, корен)
template <typename T>
void postorderTraversal(TreeNode<T>* root) {
if (!root) return;
postorderTraversal(root->left);
postorderTraversal(root->right);
std::cout << root->data << " ";
}
// Обхождане в широчина
template <typename T>
void bfs(TreeNode<T>* root) {
if (!root) return;
std::queue<TreeNode<T>*> q;
q.push(root);
while (!q.empty()) {
TreeNode<T>* current = q.front();
q.pop();
std::cout << current->data << " ";
if (current->left) q.push(current->left);
if (current->right) q.push(current->right);
}
}
int main() {
// Създаване на двоично дърво от цели числа
TreeNode<int>* root = new TreeNode<int>(1);
root->left = new TreeNode<int>(2);
root->right = new TreeNode<int>(3);
root->left->left = new TreeNode<int>(4);
root->left->right = new TreeNode<int>(5);
root->right->left = new TreeNode<int>(6);
root->right->right = new TreeNode<int>(7);
// Как изглежда дървото:
// 1
// / \
// 2 3
// / \ / \
// 4 5 6 7
// Preorder обхождане
std::cout << "Preorder traversal: ";
preorderTraversal(root); // 1 2 4 5 3 6 7
std::cout << std::endl;
// Inorder обхождане
std::cout << "Inorder traversal: ";
inorderTraversal(root); // 4 2 5 1 6 3 7
std::cout << std::endl;
// Postorder обхождане
std::cout << "Postorder traversal: ";
postorderTraversal(root); // 4 5 2 6 7 3 1
std::cout << std::endl;
// Обхождане в широчина
std::cout << "BFS traversal: ";
bfs(root); // 1 2 3 4 5 6 7
std::cout << std::endl;
return 0;
}
|
