修改下面后序遍历线索化二叉树的程序 #include <stdio.h> #include <stdlib.h> typedef char Elemtype; typedef struct TreeNode { Elemtype data; struct TreeNode* lchild; struct TreeNode* rchild; int ltag; // 0: 孩子, 1: 前驱 int rtag; // 0: 孩子, 1: 后继 } TreeNode; typedef TreeNode* threadTree; char str[] = "ABDH##I##EJ###CF##G##"; int idx = 0; void creatTree(threadTree* T) { Elemtype ch = str[idx++]; if (ch == '#') { *T = NULL; } else { *T = (threadTree)malloc(sizeof(TreeNode)); (*T)->data = ch; (*T)->lchild = NULL; // 显式初始化 (*T)->rchild = NULL; // 显式初始化 creatTree(&(*T)->lchild); (*T)->ltag = ((*T)->lchild != NULL) ? 0 : 1; creatTree(&(*T)->rchild); (*T)->rtag = ((*T)->rchild != NULL) ? 0 : 1; } } threadTree prev; // 全局前驱指针 void threading(threadTree T) { if (T != NULL) { threading(T->lchild); threading(T->rchild); // 设置当前节点的前驱线索 if (T->lchild == NULL) { T->ltag = 1; T->lchild = prev; } // 设置前驱节点的后继线索 if (prev != NULL && prev->rchild == NULL) { prev->rtag = 1; prev->rchild = T; } prev = T; } } void postOrderThreading(threadTree* head, threadTree T) { *head = (threadTree)malloc(sizeof(TreeNode)); (*head)->ltag = 0; (*head)->rtag = 1; (*head)->rchild = *head; if (T == NULL) { (*head)->lchild = *head; } else { (*head)->lchild = T; prev = *head; threading(T); // 处理最后一个节点的线索 if (prev != *head) { prev->rtag = 1; prev->rchild = *head; } (*head)->rchild = prev; // 头结点的右指针指向最后一个节点 } } threadTree findParent(threadTree root, threadTree target) { if (root == NULL || root == target) return NULL; threadTree stack[100]; int top = -1; stack[++top] = root; while (top >= 0) { threadTree current = stack[top--]; if (current->ltag == 0 && current->lchild == target) return current; if (current->rtag == 0 && current->rchild == target) return current; if (current->rtag == 0) stack[++top] = current->rchild; if (current->ltag == 0) stack[++top] = current->lchild; } return NULL; } // 关键修改点1: 正确找到后序第一个节点 threadTree postOrderFirst(threadTree root) { threadTree p = root; while (1) { if (p->ltag == 0) { p = p->lchild; } else if (p->rtag == 0) { p = p->rchild; } else { break; } } return p; } // 关键修改点2: 修正后继查找逻辑 threadTree postOrderNext(threadTree node, threadTree head) { if (node->rtag == 1) return node->rchild; threadTree parent = findParent(head->lchild, node); if (parent == NULL) return head; // 情况1: 当前节点是右孩子 或 父节点没有右子树 if (parent->rchild == node || parent->rtag == 1) return parent; // 情况2: 当前节点是左孩子且父节点有右子树 return postOrderFirst(parent->rchild); } void postOrder(threadTree head) { threadTree p = postOrderFirst(head->lchild); while (p != head) { printf("%c ", p->data); p = postOrderNext(p, head); } printf("\n"); } int main() { threadTree head, T; creatTree(&T); postOrderThreading(&head, T); printf("后序遍历结果: "); postOrder(head); return 0; }