编辑代码

#include <iostream>  
#include <queue>  
#include <string>  
using namespace std;  
  
// 定义二叉树节点  
struct TreeNode {  
    char val;  
    TreeNode *left;  
    TreeNode *right;  
    TreeNode(char x) : val(x), left(nullptr), right(nullptr) {}  
};  
  
// 辅助函数，用于从扩展前序序列构建二叉树  
TreeNode* buildTree(const string& preorder) {  
    if (preorder.empty() || preorder[0] == '*') return nullptr;  
  
    TreeNode* root = new TreeNode(preorder[0]);  
    int i = 1;  
  
    // 构建左子树  
    root->left = buildTree(preorder.substr(i, preorder.find('*', i) - i));  
    i += preorder.find('*', i) - i + 1;  
  
    // 构建右子树  
    root->right = buildTree(preorder.substr(i));  
  
    return root;  
}  
  
// 前序遍历  
void preorderTraversal(TreeNode* root) {  
    if (!root) return;  
    cout << root->val << " ";  
    preorderTraversal(root->left);  
    preorderTraversal(root->right);  
}  
  
// 中序遍历  
void inorderTraversal(TreeNode* root) {  
    if (!root) return;  
    inorderTraversal(root->left);  
    cout << root->val << " ";  
    inorderTraversal(root->right);  
}  
  
// 后序遍历  
void postorderTraversal(TreeNode* root) {  
    if (!root) return;  
    postorderTraversal(root->left);  
    postorderTraversal(root->right);  
    cout << root->val << " ";  
}  
  
// 层次遍历  
void levelOrderTraversal(TreeNode* root) {  
    if (!root) return;  
    queue<TreeNode*> q;  
    q.push(root);  
    while (!q.empty()) {  
        TreeNode* node = q.front();  
        q.pop();  
        cout << node->val << " ";  
        if (node->left) q.push(node->left);  
        if (node->right) q.push(node->right);  
    }  
}  
  
// 释放二叉树内存  
void deleteTree(TreeNode* root) {  
    if (root) {  
        deleteTree(root->left);  
        deleteTree(root->right);  
        delete root;  
    }  
}  
  
int main() {  
    string preorder = "ABC**DE*G**F***";  
    TreeNode* root = buildTree(preorder);  
  
    cout << "Preorder traversal: ";  
    preorderTraversal(root);  
    cout << endl;  
  
    cout << "Inorder traversal: ";  
    inorderTraversal(root);  
    cout << endl;  
  
    cout << "Postorder traversal: ";  
    postorderTraversal(root);  
    cout << endl;  
  
    cout << "Level order traversal: ";  
    levelOrderTraversal(root);  
    cout << endl;  
  
    // 释放二叉树内存  
    deleteTree(root);  
  
    return 0;  
}