C++中序遍历线索化二叉树代码

以下是C++中序遍历线索化二叉树的代码：\n\```++\stru ThrN {\ i ;\ ThrN *hi, *rhi;\ i g, rg;\};\n\voi IThr(ThrN *p, ThrN *&pr) {\ if (p != NULL) {\ IThr(p->hi, pr);\ if (p->hi == NULL) {\ p->hi = pr;\ p->g = 1;\ }\ if (pr != NULL && pr->rhi == NULL) {\ pr->rhi = p;\ pr->rg = 1;\ }\ pr = p;\ IThr(p->rhi, pr);\ }\}\n\voi CrIThr(ThrN *r) {\ ThrN *pr = NULL; if (r != NULL) {\ IThr(r, pr);\ pr->rhi = NULL;\ pr->rg = 1;\ }\}\```\n\

相关问题

C++中序遍历线索化二叉树的代码

以下是C++中序遍历线索化二叉树的代码：

typedef struct ThreadNode{
    ElemType data;
    struct ThreadNode *lchild, *rchild;
    int ltag, rtag;
}ThreadNode, *ThreadTree;

ThreadNode *pre = NULL; //全局变量，始终指向刚刚访问过的结点

void InThread(ThreadTree &p){
    if(p != NULL){
        InThread(p->lchild); //递归左子树线索化
        if(p->lchild == NULL){ //建立当前结点的前驱线索
            p->lchild = pre;            p->ltag = 1;
        }
        if(pre != NULL && pre->rchild == NULL){ //建立当前结点的后继线索
            pre->rchild = p;
            pre->rtag = 1;
        }
        pre = p; //保持pre指向p的前驱
        InThread(p->rchild); //递归右子树线索化
    }
}

void CreateInThread(ThreadTree &T){
    if(T != NULL){
        InThread(T);
        if(pre->rchild == NULL){ //处理遍历的最后一个结点
            pre->rchild = NULL;
            pre->rtag = 1;
        }
    }
}

实现二叉树的创建及线索化，要求如下: 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. **菜单提示操作**:
- 插入节点：用户输入节点值，系统在相应位置插入新节点。
- 中序遍历：提示用户输入“中序遍历”，系统按照线索顺序输出节点值。
- 删除节点：用户选择节点进行删除。
- 查找节点：用户输入值，系统返回是否存在。
- 修改节点值：用户选择节点并输入新值。