使用前序和中序遍历构建二叉树的C++实现

"二叉树的建立通过前序和中序遍历的结果" 在计算机科学中，二叉树是一种常用的数据结构，它由有限个节点组成，每个节点最多有两个子节点，分别称为左子节点和右子节点。二叉树的遍历方式有三种：前序遍历、中序遍历和后序遍历。每种遍历方法都会按照特定的顺序访问树的节点。当只有前序和中序遍历结果时，可以通过一定的规则重建出原始的二叉树。 前序遍历的顺序是：根节点 -> 左子树 -> 右子树。中序遍历的顺序是：左子树 -> 根节点 -> 右子树。利用这两个遍历序列，可以确定每个节点在树中的相对位置，从而构建出完整的二叉树。 给定的代码中，首先定义了一个`Node`结构体，用于表示二叉树的节点，包括数据域（`info`），父节点指针（`parent`）以及左右子节点指针（`lchild`和`rchild`）。此外，还定义了一个`Stack`结构体，用于辅助建立二叉树的过程，包含前序遍历结果的指针、中序遍历结果的指针、结点总数和父节点指针。 `myIndex`函数用于在中序遍历序列中找到指定字符的位置，如果找不到则返回-1。这是为了在后续的重建过程中定位父节点在中序遍历序列中的位置。 `createTree`函数是主要的重建二叉树的函数，它接收前序遍历序列、中序遍历序列、结点总数和父节点指针作为参数。它使用一个栈来辅助实现，栈中的元素包含了前序序列、中序序列的指针以及当前处理的节点的父节点。算法的核心思路是： 1. 当结点数不为0时，进入重建过程。 2. 找到前序遍历序列的第一个元素，即当前结点的值。 3. 在中序遍历序列中找到该元素的位置，确定左子树和右子树的分界。 4. 分别处理左子树和右子树，直到所有结点都被处理，即树完全建立。 在这个过程中，`createTree`函数会不断地将子问题压入栈中，然后根据栈顶元素的状态决定是创建新节点还是回溯到父节点。当树完全建立，栈为空且所有结点都被处理时，函数返回构建好的树的根节点。 重建二叉树的过程涉及递归或迭代的思想，本例使用了迭代的方法。这种算法的复杂度为O(n)，因为每个节点只被访问一次。通过这种方法，可以有效地从给定的两个遍历序列恢复出原始的二叉树结构。