用C++编写算法建立一棵二叉树的二叉链表 输出二叉树的三种遍历序列，非递归算法的完整代码

在C++中，我们可以使用结构体表示节点，并通过指针链接形成二叉链表表示二叉树。以下是创建二叉树、插入节点以及三种遍历（前序、中序、后序）的非递归实现。这里假设有一个简单的`TreeNode`结构：

#include <iostream>

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

// 创建一个新的节点并插入到二叉树中
TreeNode* insertIntoTree(TreeNode* root, int val) {
    if (root == NULL) return new TreeNode(val);
    if (val < root->val) root->left = insertIntoTree(root->left, val);
    else root->right = insertIntoTree(root->right, val);
    return root;
}

// 非递归的三种遍历函数
void preOrderTraversal(TreeNode* node) {
    if (node != NULL) {
        std::cout << node->val << " ";
        preOrderTraversal(node->left);
        preOrderTraversal(node->right);
    }
}

void inOrderTraversal(TreeNode* node) {
    if (node != NULL) {
        inOrderTraversal(node->left);
        std::cout << node->val << " ";
        inOrderTraversal(node->right);
    }
}

void postOrderTraversal(TreeNode* node) {
    if (node != NULL) {
        postOrderTraversal(node->left);
        postOrderTraversal(node->right);
        std::cout << node->val << " ";
    }
}

int main() {
    // 创建初始空树
    TreeNode* root = nullptr;

    // 插入节点示例
    root = insertIntoTree(root, 50);
    insertIntoTree(root, 30);
    insertIntoTree(root, 20);
    insertIntoTree(root, 40);
    insertIntoTree(root, 70);
    insertIntoTree(root, 60);
    insertIntoTree(root, 80);

    // 打印三种遍历结果
    std::cout << "Preorder Traversal: ";
    preOrderTraversal(root);
    std::cout << "\nInorder Traversal: ";
    inOrderTraversal(root);
    std::cout << "\nPostorder Traversal: ";
    postOrderTraversal(root);
    
    return 0;
}