实现二叉树的创建及线索化，要求如下: 1.创建二叉树 2.中序递归和非递归遍历 3.中序线索化二叉树 4.利用中序线索化二叉树实现二叉树的中序遍历 5.菜单提示操作

在计算机科学中，创建二叉树通常涉及定义一个节点结构，包含两个子节点和一个值。以下是简单的步骤：

1. **创建二叉树**:
创建二叉树的类或结构体，例如在 C++ 中：

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

通过递归或迭代的方式构造二叉树，如插入节点、从数组或序列构建等。

2. **中序遍历**:
- **递归实现**:
对于每个节点，先访问左子树（`left->visit()`），然后访问自身（`visit()`），最后访问右子树（`right->visit()`）。
- **非递归实现**（也称为 Morris 遍历）:
使用两个指针 `cur` 和 `pre`，在当前节点的左子树空时，将 `pre` 移动到当前节点并更新 `cur`，然后访问当前节点。完成后回溯到 `pre`。

3. **中序线索化二叉树**:
在中序遍历时，在每个节点处添加线索，指向其前驱节点（对于左线索，如果当前节点为左孩子，前驱为父节点；否则为空），以便后续无需递归跟踪即可完成遍历。

4. **利用中序线索化二叉树实现中序遍历**:
- 从根节点开始，如果当前节点不为空，找到其左线索（可能为NULL）。
- 递归或迭代地遍历左子树，直到左子树为空或遇到非空节点的前驱。
- 访问当前节点，并移动到右子树，如果右子树存在，则继续遍历，否则返回上一个节点的右线索（表示回溯到父节点）。

5. **菜单提示操作**:
- 插入节点：用户输入节点值，系统在相应位置插入新节点。
- 中序遍历：提示用户输入“中序遍历”，系统按照线索顺序输出节点值。
- 删除节点：用户选择节点进行删除。
- 查找节点：用户输入值，系统返回是否存在。
- 修改节点值：用户选择节点并输入新值。