基于指针的树、二叉树以及遍历（V1.4）
2024-01-29 15:06:38
发布于：浙江
111阅读
0回复
0点赞
下集传送门：线段树
树的类：
class TreeNode { //定义树节点
public:
int name;
vector<TreeNode*> children;
TreeNode(const int& nodeName) : name(nodeName) {}
void addChild(TreeNode* child){
children.push_back(child);
}
};
二叉树变种：
class binary_TreeNode {
public:
int value;
binary_TreeNode* left;
binary_TreeNode* right;
binary_TreeNode(const int& nodeValue) : value(nodeValue), left(nullptr), right(nullptr) {}
};
输入树：
int n, j, k;
cin >> n;
vector<TreeNode*> nodes(n + 1); // 创建一个存储节点的 vector，索引从1开始
nodes[0] = new TreeNode(0); // 根节点
for (int i = 1; i <= n; i++) {
cin >> j;
nodes[i] = new TreeNode(j); // 将新节点添加到 vector
}
for (int i = 0; i < n; i++) {
cin >> j >> k;
nodes[j]->addChild(nodes[k]); // 根据索引添加子节点
}
先输入元素个数n，然后输入n个元素，后面n行每行输入两个正整数a、b表示输入的第b项是第a项的子节点。（根节点是第0项，不计入输入中）
例如:
0
/ \
1 2
/ \ \
3 4 5
输入为：
5
1 2 3 4 5
0 1
0 2
1 3
1 4
2 5
二叉树变种：
int n, j, parent, l_child, r_child;;
cin >> n;
vector<binary_TreeNode*> nodes(n + 1); // 创建一个存储节点的 vector，索引从1开始
nodes[0] = new binary_TreeNode(0); // 根节点
for (int i = 1; i <= n; i++) {
cin >> j;
nodes[i] = new binary_TreeNode(j); // 将新节点添加到 vector
}
for (int i = 1; i <= n; i++) {
cin >> parent >> j;
if (j == 0) {
cin >> l_child;
nodes[parent]->left = nodes[l_child]; // 设置左子节点
}
else {
cin >> r_child;
nodes[parent]->right = nodes[r_child]; // 设置右子节点
}
}
先输入元素个数n，然后输入n个元素，后面n行每行输入三个正整数a、j和b。
如果j为0，表示输入的第b项是第a项的左子节点，如果j为1，则表示输入的第b项是第a项的右子节点。（根节点是第0项，不计入输入中）
例如:
0
/ \
1 2
/ \ \
3 4 5
输入为：
5
1 2 3 4 5
0 0 1
0 1 2
1 0 3
1 1 4
2 1 5
展示树的结构：
void displayTree1(TreeNode* node, int depth = 0) {
if (node == nullptr)
return;
for (int i = 0; i < depth; ++i)
cout << "| ";
cout << "|_" << node->name << "\n";
for (TreeNode* child : node->children)
displayTree1(child, depth + 1);
}
二叉树变种：
void displayBinaryTree(binary_TreeNode* node, int depth = 0) {
if (node == nullptr)
return;
for (int i = 0; i < depth; ++i)
cout << "| ";
cout << "|_" << node->value << "\n";
displayBinaryTree(node->left, depth + 1);
displayBinaryTree(node->right, depth + 1);
}
例如:
0
/ \
1 2
/ \ \
3 4 5
输出为：
|_0
| |_1
| | |_3
| | |_4
| |_2
| | |_5
二叉树前序遍历：
void b_preorder_traversal(binary_TreeNode* node) {
if (node == nullptr)
return;
cout << node->value << " ";
b_preorder_traversal(node->left);
b_preorder_traversal(node->right);
}
例如:
0
/ \
1 2
/ \ \
3 4 5
输出为：
0 1 3 4 2 5
二叉树中序遍历：
void b_inorder_traversal(binary_TreeNode* node) {
if (node == nullptr)
return;
b_inorder_traversal(node->left);
cout << node->value << " ";
b_inorder_traversal(node->right);
}
例如:
0
/ \
1 2
/ \ \
3 4 5
输出为：
3 1 4 0 5 2
二叉树后序遍历：
void b_postorder_traversal(binary_TreeNode* node) {
if (node == nullptr)
return;
b_postorder_traversal(node->left);
b_postorder_traversal(node->right);
cout << node->value << " ";
}
例如:
0
/ \
1 2
/ \ \
3 4 5
输出为：
3 4 1 5 2 0
层次（BFS）遍历：
void level_order_traversal(TreeNode* root) {
if (root == nullptr)
return;
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
TreeNode* current = q.front();
q.pop();
cout << current->name << " ";
for (TreeNode* child : current->children)
q.push(child);
}
}
二叉树变种：
void b_level_order_traversal(binary_TreeNode* root) {
if (root == nullptr)
return;
queue<binary_TreeNode*> q;
q.push(root);
while (!q.empty()) {
binary_TreeNode* current = q.front();
q.pop();
cout << current->value << " ";
if (current->left)
q.push(current->left);
if (current->right)
q.push(current->right);
}
}
例如:
0
/ \
1 2
/ \ \
3 4 5
输出为：
0 1 2 3 4 5
叶节点遍历：
void leaf_node_traversal(TreeNode* node) {
if (node == nullptr)
return;
if (node->children.empty())
cout << node->name << " ";
else
for (TreeNode* child : node->children)
leaf_node_traversal(child);
}
例如:
0
/ \
1 2
/ \ \
3 4 5
输出为：
3 4 5
一个实例程序：
#include <bits/stdc++.h>
using namespace std;
class TreeNode { //定义树节点
public:
int name;
vector<TreeNode*> children;
TreeNode(const int& nodeName) : name(nodeName) {}
void addChild(TreeNode* child){
children.push_back(child);
}
};
// 展示树的结构
void displayTree1(TreeNode* node, int depth = 0) {
if (node == nullptr)
return;
for (int i = 0; i < depth; ++i)
cout << "| ";
cout << "|_" << node->name << "\n";
for (TreeNode* child : node->children)
displayTree1(child, depth + 1);
}
// DFS遍历
void DFS(TreeNode* node) {
if (node == nullptr)
return;
cout << node->name << " ";
for (TreeNode* child : node->children)
preorder_traversal(child);
}
// 层次遍历（BFS遍历）
void level_order_traversal(TreeNode* root) {
if (root == nullptr)
return;
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
TreeNode* current = q.front();
q.pop();
cout << current->name << " ";
for (TreeNode* child : current->children)
q.push(child);
}
}
// 叶节点遍历
void leaf_node_traversal(TreeNode* node) {
if (node == nullptr)
return;
if (node->children.empty())
cout << node->name << " ";
else
for (TreeNode* child : node->children)
leaf_node_traversal(child);
}
int main() {
int n, j, k;
cin >> n;
vector<TreeNode*> nodes(n + 1); // 创建一个存储节点的 vector，索引从1开始
nodes[0] = new TreeNode(0); // 根节点
for (int i = 1; i <= n; i++) {
cin >> j;
nodes[i] = new TreeNode(j); // 将新节点添加到 vector
}
for (int i = 0; i < n; i++) {
cin >> j >> k;
nodes[j]->addChild(nodes[k]); // 根据索引添加子节点
}
// 打印树的结构
displayTree1(nodes[0]);
cout << "\nDFS遍历: ";
DFS(nodes[0]);
cout << "\n层次（BFS）遍历: ";
level_order_traversal(nodes[0]);
cout << "\n叶节点遍历: ";
leaf_node_traversal(nodes[0]);
// 释放内存
for (TreeNode* node : nodes)
delete node;
return 0;
}
几组测试数据：
-
1
5
1 2 3 4 5
0 1
0 2
1 3
1 4
2 5
-
2
8
1 2 3 4 5 6 7 8
0 1
0 2
0 3
1 4
1 5
2 6
6 7
6 8
-
3
24
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
0 1
1 2
2 3
3 4
3 5
3 6
2 7
7 8
1 9
9 10
9 11
0 12
12 13
12 14
14 15
14 16
16 17
0 18
18 19
18 20
20 21
20 22
20 23
18 24
二叉树的实例程序放不下了，就自己写吧（doge
二叉树的测试数据：
-
1
5
1 2 3 4 5
0 0 1
0 1 2
1 0 3
1 1 4
2 1 5
-
2
10
1 2 3 4 5 6 7 8 9 10
0 0 1
0 1 2
1 0 3
1 1 4
3 0 7
3 1 8
2 0 5
2 1 6
5 0 9
6 1 10
-
3（有惊喜哦~）
6
1 2 1 3 4 5
0 0 1
0 1 2
1 0 3
1 1 4
2 0 5
2 1 6
有帮助，赞一个