7-2 线索二叉树的建立和遍历 分数 10 作者 张瑞霞 单位 桂林电子科技大学 本题要求实现对建立中序线索二叉树和中序遍历中序线索二叉树。 图片1.png 输入格式: 输入为先序序列 输出格式: 输出为中序遍历线索树的结点值以及结点的左右指针信

线索二叉树是一种在二叉树中添加额外信息的数据结构，主要用于方便地进行中序遍历。在7-2题中，你需要构建的是一个中序线索二叉树，这是通过给每个节点加上左、右线索，使得从根节点开始能够通过线索按中序顺序访问所有节点。

**建立过程**:
1. 先序遍历输入数据，遇到节点时，记录当前节点并继续搜索其左孩子。当找到左孩子的右兄弟节点（即下一个中序节点），设置该节点的右线索指向当前节点。
2. 如果没有左孩子，那么将当前节点作为根节点，并直接设置它的左线索为空，因为中序遍历时它将是第一个访问的节点。

**中序遍历过程**:
1. 从根节点开始，如果节点有左线索，就沿着左线索向下查找；如果没有左线索，则访问该节点并检查右线索，然后递归处理右子树。
2. 记录访问过的节点，更新当前节点为它的右兄弟节点，直到遍历完整棵树。

对于输入的先序遍历序列，例如 `[A, B, D, E, C]`（假设 A 是根），建立后的中序线索树可能会是这样的结构：

        A
      /   \
     B     C
    / \   / \
   D   E NULL NULL
       \
        F
         |
         NULL

其中 `F` 是 `E` 的右兄弟，但由于 `B` 没有左孩子，所以 `B` 的左线索是空。

**输出格式**:
输出将包括每个节点的值（比如 A, B, D, E, C 和 F），以及每个节点的左（L）和右（R）指针指示的方向。例如，输出可以表示为：`A L->B R->NULL`, `B L->NULL R->C` 等等。