二叉树遍历程序故障求助：中序与后序输出结果异常

问题现象 #

按顺序插入1 2 3 4 5时，遍历结果不符合预期：

• 前序遍历输出1 2 3 4 5（符合预期）
• 中序遍历输出1 2 3 4 5（与前序一致，不符合预期）
• 后序遍历输出5 4 3 2 1（为输入逆序，不符合预期）

问题根源 #

你的insertNode函数实现的是**二叉搜索树（BST）**的插入规则：

• 若新节点值小于当前节点值，插入左子树
• 否则插入右子树

当按递增顺序插入1 2 3 4 5时，每个新节点都会被插到当前树的最右侧，最终二叉树退化成一条右斜单链表：

1
 \
  2
   \
    3
     \
      4
       \
        5

这种结构下：

• 前序遍历：根→左（空）→右，结果为1 2 3 4 5
• 中序遍历：左（空）→根→右，结果与前序完全一致
• 后序遍历：左（空）→右→根，结果为输入的逆序5 4 3 2 1

修复方案 #

如果你想创建普通二叉树（而非二叉搜索树），可以修改插入逻辑为层次遍历顺序插入（填满左子树再填右子树），示例如下：

1. 首先添加队列头文件：

#include <queue>

2. 替换原insertNode函数：

void insertNode(Node* &root, int data) {
    Node* newNode = createNode(data);
    if (root == NULL) {
        root = newNode;
        return;
    }
    // 用队列实现层次遍历，找到第一个有空子节点的位置
    queue<Node*> q;
    q.push(root);
    while (!q.empty()) {
        Node* current = q.front();
        q.pop();
        // 优先插入左子树
        if (current->left == NULL) {
            current->left = newNode;
            return;
        } else {
            q.push(current->left);
        }
        // 左子树已满则插入右子树
        if (current->right == NULL) {
            current->right = newNode;
            return;
        } else {
            q.push(current->right);
        }
    }
}

验证结果 #

插入1 2 3 4 5后，二叉树结构变为：

1
    /   \
   2     3
  / \
 4   5

此时各遍历结果：

• 前序遍历：1 2 4 5 3
• 中序遍历：4 2 5 1 3
• 后序遍历：4 5 2 3 1
  完全符合普通二叉树的遍历预期。

补充说明 #

如果你原本就是想实现二叉搜索树，那当前的中序遍历结果1 2 3 4 5其实是符合BST特性的（BST中序遍历必然为升序序列）。但递增插入导致的链表化会让BST操作效率从O(logn)降到O(n)，可以通过平衡二叉树（如AVL树、红黑树）优化。

内容的提问来源于stack exchange，提问作者jamie