给出C语言在中序线索二叉树左子树中插入节点的完整代码

### C语言实现中序线索二叉树左子树插入节点 以下是基于中序线索二叉树特性的完整代码示例，用于在左子树中插入新节点。此代码实现了创建中序线索二叉树的功能，并提供了插入节点的具体逻辑。 #### 1. 数据结构定义 为了支持中序线索化的特性，需要扩展标准的二叉树节点结构，增加两个布尔标志位 `ltag` 和 `rtag` 来区分指针是指向孩子还是指向前驱/后继节点[^3]。 ```c #include <stdio.h> #include <stdlib.h> typedef char ElementType; // 定义二叉树节点结构体 typedef struct BiTNode { ElementType data; struct BiTNode *lchild, *rchild; int ltag, rtag; // ltag=0 表示指向前驱；rtag=0 表示指向后继 } BiTNode, *BiTree; ``` --- #### 2. 创建并初始化二叉树 通过递归方式构建一棵简单的二叉树作为测试数据。 ```c void CreateBiTree(BiTree *T) { ElementType ch; scanf(" %c", &ch); if (ch == '#') { // 如果输入为'#'表示该位置为空 *T = NULL; } else { *T = (BiTNode *)malloc(sizeof(BiTNode)); (*T)->data = ch; (*T)->ltag = 0; (*T)->rtag = 0; CreateBiTree(&((*T)->lchild)); // 构建左子树 CreateBiTree(&((*T)->rchild)); // 构建右子树 } } ``` --- #### 3. 实现中序线索化 利用递归方法完成对整个二叉树的中序线索化处理。 ```c void InThread(BiTree p, BiTree *pre) { if (p != NULL) { // 遍历左子树 InThread(p->lchild, pre); // 处理当前节点 if (p->lchild == NULL) { // 若无左孩子，则将其设为前驱线索 p->lchild = *pre; p->ltag = 1; } if (*pre && (*pre)->rchild == NULL) { // 前一节点若有右孩子则置为后继线索 (*pre)->rchild = p; (*pre)->rtag = 1; } // 更新前驱节点 *pre = p; // 遍历右子树 InThread(p->rchild, pre); } } void CreateInThread(BiTree T) { BiTree pre = NULL; if (T != NULL) { InThread(T, &pre); // 对整棵树进行中序线索化 if (pre->rchild == NULL) { // 最后一个节点应设置其后继为NULL pre->rtag = 1; pre->rchild = NULL; } } } ``` --- #### 4. 插入节点到左子树 提供一种通用的方法，在指定父节点的左子树中插入新的节点[^1]。 ```c int InsertLeftChild(BiTree parent, ElementType value) { if (parent == NULL || parent->lchild != NULL) { return 0; // 返回失败状态码 } // 动态分配内存给新节点 BiTree newNode = (BiTNode *)malloc(sizeof(BiTNode)); newNode->data = value; newNode->lchild = NULL; newNode->rchild = NULL; newNode->ltag = 0; newNode->rtag = 0; // 将新节点连接至父节点左侧 parent->lchild = newNode; parent->ltag = 0; return 1; // 成功返回1 } ``` --- #### 5. 测试程序入口 最后编写主函数来验证以上功能模块是否正常工作。 ```c int main() { BiTree T = NULL; printf("请输入二叉树(按先序序列,#代表空): "); CreateBiTree(&T); // 进行中序线索化 CreateInThread(T); // 执行插入操作 BiTree parentNode = T->lchild; // 假定根节点存在且有左子树 if (!parentNode) { printf("无法找到有效的父节点。\n"); exit(EXIT_FAILURE); } if (InsertLeftChild(parentNode, 'X')) { printf("成功插入字符 X 到目标节点左边\n"); } else { printf("插入失败!\n"); } return EXIT_SUCCESS; } ``` --- ###