基于指针的树、二叉树以及遍历（原创）

常规
1

树的类：

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 preorder_traversal(TreeNode* node) {
    if (node == nullptr)
        return;
    cout << node->name << " ";
    for (TreeNode* child : node->children)
        preorder_traversal(child);
}

二叉树变种：

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 inorder_traversal(TreeNode* node) {
    if (node == nullptr)
        return;
    if (node->children.size() > 0) {
        inorder_traversal(node->children[0]);
    }
    cout << node->name << " ";
    for (size_t i = 1; i < node->children.size(); ++i) {
        inorder_traversal(node->children[i]);
    }
}

二叉树变种：

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 postorder_traversal(TreeNode* node) {
    if (node == nullptr)
        return;
    for (TreeNode* child : node->children)
        postorder_traversal(child);
    cout << node->name << " ";
}

二叉树变种：

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

层次遍历：

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);
}
// 前序遍历
void preorder_traversal(TreeNode* node) {
    if (node == nullptr)
        return;
    cout << node->name << " ";
    for (TreeNode* child : node->children)
        preorder_traversal(child);
}
// 中序遍历
void inorder_traversal(TreeNode* node) {
    if (node == nullptr)
        return;
    if (node->children.size() > 0) {
        inorder_traversal(node->children[0]);
    }
    cout << node->name << " ";
    for (size_t i = 1; i < node->children.size(); ++i) {
        inorder_traversal(node->children[i]);
    }
}
// 后序遍历
void postorder_traversal(TreeNode* node) {
    if (node == nullptr)
        return;
    for (TreeNode* child : node->children)
        postorder_traversal(child);
    cout << node->name << " ";
}
// 层次遍历
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 << "\n前序遍历: ";
    preorder_traversal(nodes[0]);
    cout << "\n中序遍历: ";
    inorder_traversal(nodes[0]);
    cout << "\n后序遍历: ";
    postorder_traversal(nodes[0]);
    cout << "\n层次遍历: ";
    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
8 个赞
2

没人看吗……

5 个赞
3

有但没啥好发的

4 个赞
4

对于需要的人还是有用的

5 个赞
5

肯定得给你一个大大的赞

6

just like me