C++ 二叉树算法实现：创建、遍历和示例

本文介绍了如何使用 C++ 实现二叉树的基本操作算法，包括创建二叉树的二叉链式存储结构以及前序、中序、后序和层序遍历二叉树。示例代码展示了如何根据二叉树字符串创建二叉树，并输出不同遍历方式的结果。

代码实现

#include <iostream>
#include <stack>
#include <queue>
using namespace std;

// 二叉树结点的定义
struct TreeNode {
    char data;
    TreeNode* left;
    TreeNode* right;
    TreeNode(char val) : data(val), left(nullptr), right(nullptr) {}
};

// 根据二叉树字符串创建二叉树的函数
TreeNode* createBinaryTree(string str) {
    if (str.empty()) {
        return nullptr;
    }

    stack<TreeNode*> st;
    TreeNode* root = nullptr;
    TreeNode* curr = nullptr;
    bool isLeftChild = true;

    for (char c : str) {
        if (c == '(') {
            st.push(curr);
            isLeftChild = true;
        }
        else if (c >= 'A' && c <= 'Z') {
            curr = new TreeNode(c);
            if (root == nullptr) {
                root = curr;
            }
            else if (isLeftChild) {
                st.top()->left = curr;
            }
            else {
                st.top()->right = curr;
            }
            isLeftChild = false;
        }
        else if (c == ')') {
            st.pop();
        }
    }

    return root;
}

// 前序遍历二叉树（递归）
void preorderTraversal(TreeNode* root) {
    if (root == nullptr) {
        return;
    }

    cout << root->data << ' '; // 注意空格
    preorderTraversal(root->left);
    preorderTraversal(root->right);
}

// 中序遍历二叉树（递归）
void inorderTraversal(TreeNode* root) {
    if (root == nullptr) {
        return;
    }

    inorderTraversal(root->left);
    cout << root->data << ' '; // 注意空格
    inorderTraversal(root->right);
}

// 后序遍历二叉树（递归）
void postorderTraversal(TreeNode* root) {
    if (root == nullptr) {
        return;
    }

    postorderTraversal(root->left);
    postorderTraversal(root->right);
    cout << root->data << ' '; // 注意空格
}

// 层序遍历二叉树
void levelorderTraversal(TreeNode* root) {
    if (root == nullptr) {
        return;
    }

    queue<TreeNode*> q;
    q.push(root);

    while (!q.empty()) {
        TreeNode* curr = q.front();
        q.pop();
        cout << curr->data << ' '; // 注意空格

        if (curr->left != nullptr) {
            q.push(curr->left);
        }

        if (curr->right != nullptr) {
            q.push(curr->right);
        }
    }
}

int main() {
    string str = 'A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))';
    TreeNode* root = createBinaryTree(str);

    cout << "Preorder traversal: ";
    preorderTraversal(root);
    cout << endl;

    cout << "Inorder traversal: ";
    inorderTraversal(root);
    cout << endl;

    cout << "Postorder traversal: ";
    postorderTraversal(root);
    cout << endl;

    cout << "Levelorder traversal: ";
    levelorderTraversal(root);
    cout << endl;

    return 0;
}

输出结果

Preorder traversal: A B D E H J K L M N C F G I 
Inorder traversal: D B J H K L M N E A F C G I 
Postorder traversal: D J H K L M N E B F I G C A 
Levelorder traversal: A B C D E F G H I J K L M N

代码说明

1. 创建二叉树的二叉链式存储结构:

   • 使用 createBinaryTree 函数根据二叉树字符串创建二叉树。
   • 使用栈存储当前节点的父节点，方便在创建子节点时连接到父节点。
   • 通过 isLeftChild 变量判断当前创建的节点是父节点的左子节点还是右子节点。

2. 遍历二叉树:

   • 实现了四种遍历方式: 前序、中序、后序和层序遍历。
   • 前序、中序、后序遍历使用递归实现。
   • 层序遍历使用队列实现，按照层次从左到右遍历二叉树。

总结

本文介绍了如何使用 C++ 实现二叉树的基本操作算法，包括创建二叉树的二叉链式存储结构以及四种遍历方式。希望本文可以帮助你更好地理解和应用二叉树算法。