C语言实现二叉树构建与前序遍历 节点5、7位置错位问题求解

问题现象 #

• 输入数字序列：61207895
• 期望构建的二叉树结构：

6
        / \
       /   \
      /     \
     1       7
    / \     / \
   0   2   5   8
                \
                 9

• 期望前序遍历结果：6 1 0 2 7 5 8 9
• 实际运行输出：6 1 0 2 5 7 8 9，节点5和7的输出顺序颠倒

问题根因 #

你的代码逻辑和预期目标存在本质不匹配：

1. 你实现的insertNode是标准**二叉搜索树（BST）**插入逻辑：新节点从根开始逐层和当前节点比较值大小，值更小就进左子树，值更大/相等就进右子树，直到找到空位置挂载，最终整棵树满足「任意节点的左子树所有节点值都小于该节点，右子树所有节点值都大于该节点」的性质。
2. 你手绘的目标树根本不符合BST的基本规则：树中5是7的左孩子，属于根节点6的右子树范围，但5<6，这种结构不可能通过BST插入逻辑生成。
3. 按照你的输入顺序，插入最后一个元素5时的比较路径为：
   • 从根节点6开始：5<6，进入左子树
   • 到左子树节点1：5>1，进入右子树
   • 到节点2：5>2，此时2的右子树为空，直接把5挂在2的右孩子位置
     最终5的位置在节点2的右侧，前序遍历访问完2之后就会直接访问5，再回溯到根节点访问右子树的7，自然就得到了6 1 0 2 5 7 8 9的输出，这个输出是你当前BST逻辑下的正确结果。

另外你的代码还有一个小隐患：malloc申请了9字节空间刚好存8位数字加字符串结束符，但scanf("%s")没有加长度限制，一旦用户输入过长就会出现缓冲区溢出，建议修改为scanf("%8s", digits)。

修复方向 #

• 如果你确实需要构建你手绘的那棵固定结构的树，不能用BST比较插入的逻辑，需要手动指定每个节点的挂载位置，因为这棵树不是BST，无法通过大小比较规则自动生成。
• 如果你本来的目标就是构建BST，那么你手绘的树结构和预期遍历结果是错的，当前代码输出的才是序列61207895对应BST的合法前序遍历结果。

逻辑验证说明 #

你的前序遍历函数preorderTraversal逻辑完全正确，没有问题。main函数除了scanf的安全隐患外，流程也没有错误，问题完全出在「插入逻辑和你预期的树结构不匹配」上。

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