参考王道《2023年数据结构考研复习指导》
注意：王道2023年数据结构讲解里，先序线索化二叉树代码有问题（如下图），线索化右子树也必须判断下是否已经建立线索
否则，如果二叉树是这样的结构：
若不对右子树判空，会造成死循环：
分析：走到pre=7那步后t没路了，然后回退到3进行3的第二个递归栈，因为没有对3的右标志判断，t走到6，此时pre还是7不变，然后就死循环了
如图，此时执行完PreThread(7, 6)，pre指向7，且3结点左子树已经建立了线索二叉树，返回去执行建立3结点右子树的线索二叉树，由于没有判断右子树标志（原本3结点没有右子树，由于建立了线索二叉树，此时3结点的右子树指向它的后继结点6），执行PreThread（6，7），由于pre指向7，结点7没有右子树，使得结点7的右子树指向6（图中未画出），这就导致对先序线索二叉树进行先序遍历（利用线索实现的非递归算法）时，由于7结点的右子树（后继结点）指向6，造成了死循环。
后序线索树王道的代码暂时没发现问题，不过，以防万一，我觉得还是判定下左右标志
完整代码：
#includetypedef int ElemType; // 线索二叉树（链式存储） typedef struct ThreadNode { ElemType data; struct ThreadNode* lchild, * rchild; int ltag, rtag; // 左右线索标志(有孩子结点时为0，有线索时为1) } ThreadNode, * ThreadTree; bool CreateTree(ThreadTree& T, ElemType* datagroup, int length); bool PreTree(ThreadTree& T, ElemType* datagroup, int length, int& i); void InThread(ThreadTree& T, ThreadNode*& pre); void CreateInThread(ThreadTree T); ThreadNode* FirstNode(ThreadNode* p); ThreadNode* NextNode(ThreadNode* p); void InOrder(ThreadNode* T); void visit(ThreadNode* p); ThreadNode* LastNode(ThreadNode* p); ThreadNode* PreNode(ThreadNode* p); void RevInOrder(ThreadNode* T); void PreThread(ThreadTree& T, ThreadNode*& pre); void CreatePreThread(ThreadTree T); ThreadNode* NextNode2(ThreadNode* p); void PreOrder(ThreadNode* T); void PostThread(ThreadTree& T, ThreadNode*& pre); void CreatePostThread(ThreadTree T); ThreadNode* PreNode2(ThreadNode* p); void PostOrder(ThreadNode* T); int main() { ThreadTree T1; ElemType datagroup[] = { 1, 2, 4, -1, -1, 5, -1, -1, 3, 6, -1, 7, -1, -1, -1 }; CreateTree(T1, datagroup, sizeof(datagroup) / sizeof(datagroup[0])); CreateInThread(T1); InOrder(T1); std::cout << std::endl; RevInOrder(T1); std::cout << std::endl; ThreadTree T2; CreateTree(T2, datagroup, sizeof(datagroup) / sizeof(datagroup[0])); CreatePreThread(T2); PreOrder(T2); std::cout << std::endl; ThreadTree T3; CreateTree(T3, datagroup, sizeof(datagroup) / sizeof(datagroup[0])); CreatePostThread(T3); PostOrder(T3); std::cout << std::endl; system("pause"); return 0; } // 创建二叉树 // datagroup数组的元素的值作为树中各个节点的数据，并规定如果某个元素的值为-1，表示对应的节点是NULL节点。 bool CreateTree(ThreadTree& T, ElemType* datagroup, int length) { int i = 0; // 数组指针 return PreTree(T, datagroup, length, i); } // 创建二叉树(按照先序遍历方式，组成一个棵树) bool PreTree(ThreadTree& T, ElemType* datagroup, int length, int& i) { if (i >= length || datagroup[i] == -1) { T = NULL; i++; return true; } T = (ThreadNode*)malloc(sizeof(ThreadNode)); if (T == NULL) return false; T->data = datagroup[i++]; T->ltag = 0; // 左右线索标志初始化为0 T->rtag = 0; return PreTree(T->lchild, datagroup, length, i) && PreTree(T->rchild, datagroup, length, i); } // 中序遍历对二叉树线索化 void InThread(ThreadTree& T, ThreadNode*& pre) { if (T != NULL) { if (T->ltag == 0) // 判断是否已经建立线索，以防万一 InThread(T->lchild, pre); // 递归，线索化左子树 if (T->lchild == NULL) { // 左子树为空，建立前驱线索 T->lchild = pre; T->ltag = 1; } if (pre != NULL && pre->rchild == NULL) { // 因为pre一开始为NULL pre->rchild = T; // 建立前驱结点的后继线索 pre->rtag = 1; } pre = T; // 标记当前结点成为刚刚访问过的结点 if (T->rtag == 0) // 判断是否已经建立线索，以防万一 InThread(T->rchild, pre); // 递归，线索化右子树 } } // 中序线索化二叉树T void CreateInThread(ThreadTree T) { ThreadNode* pre = NULL; if (T != NULL) { InThread(T, pre); pre->rchild = NULL; // 处理遍历的最后一个结点 pre->rtag = 1; } } // 中序线索二叉树正向中序序列（找中序后继） // 找到以p为根节点的子树中，第一个被中序遍历的结点 ThreadNode* FirstNode(ThreadNode* p) { while (p->ltag == 0) p = p->lchild; return p; } // 在中序线索二叉树中找到结点p的后继结点 ThreadNode* NextNode(ThreadNode* p) { if (p->rtag == 1) return p->rchild; else return FirstNode(p->rchild); // 返回右子树最左下结点（即p的后继节点） } // 对中序线索二叉树进行中序遍历（利用线索实现的非递归算法） void InOrder(ThreadNode* T) { for (ThreadNode* p = FirstNode(T); p != NULL; p = NextNode(p)) visit(p); } // 访问二叉树结点的操作 void visit(ThreadNode* p) { std::cout << p->data << " "; } // 中序线索二叉树逆向中序序列（找中序后继） // 找到以p为根节点的子树中，最后一个被中序遍历的结点 ThreadNode* LastNode(ThreadNode* p) { while (p->rtag == 0) p = p->rchild; return p; } // 在中序线索二叉树中找到结点p的前驱结点 ThreadNode* PreNode(ThreadNode* p) { if (p->ltag == 1) return p->lchild; else return LastNode(p->lchild); // 返回右子树最左下结点（即p的后继节点） } // 对中序线索二叉树进行逆向中序遍历（利用线索实现的非递归算法） void RevInOrder(ThreadNode* T) { for (ThreadNode* p = LastNode(T); p != NULL; p = PreNode(p)) visit(p); } // 先序遍历对二叉树线索化 void PreThread(ThreadTree& T, ThreadNode*& pre) { if (T != NULL) { if (T->lchild == NULL) { // 左子树为空，建立前驱线索 T->lchild = pre; T->ltag = 1; } if (pre != NULL && pre->rchild == NULL) { // 因为pre一开始为NULL pre->rchild = T; // 建立前驱结点的后继线索 pre->rtag = 1; } pre = T; // 标记当前结点成为刚刚访问过的结点 if (T->ltag == 0) { // 因为左结点在递归前建立可能已经前驱线索，避免造成死循环 PreThread(T->lchild, pre); // 递归，线索化左子树 } if (T->rtag == 0) { PreThread(T->rchild, pre); // 递归，线索化右子树 } } } // 先序线索化二叉树T void CreatePreThread(ThreadTree T) { ThreadNode* pre = NULL; if (T != NULL) { PreThread(T, pre); pre->rchild = NULL; // 处理遍历的最后一个结点 pre->rtag = 1; } } // 先序线索二叉树正向先序遍历（找后继结点） // 在先序线索二叉树中找到结点p的后继结点 ThreadNode* NextNode2(ThreadNode* p) { if (p->rtag == 1) return p->rchild; else { // 此时p必有右孩子 if (p->ltag == 0) // 有左孩子，左孩子为后继结点 return p->lchild; else // 无左孩子，右孩子为后继结点 return p->rchild; } } // 对先序线索二叉树进行先序遍历（利用线索实现的非递归算法） void PreOrder(ThreadNode* T) { for (ThreadNode* p = T; p != NULL; p = NextNode2(p)) visit(p); } // 后续遍历对二叉树线索化 void PostThread(ThreadTree& T, ThreadNode*& pre) { if (T != NULL) { if (T->ltag == 0) PostThread(T->lchild, pre); // 递归，线索化左子树 if (T->rtag == 0) PostThread(T->rchild, pre); // 递归，线索化右子树 if (T->lchild == NULL) { // 左子树为空，建立前驱线索 T->lchild = pre; T->ltag = 1; } if (pre != NULL && pre->rchild == NULL) { // 因为pre一开始为NULL pre->rchild = T; // 建立前驱结点的后继线索 pre->rtag = 1; } pre = T; // 标记当前结点成为刚刚访问过的结点 } } // 后序线索化二叉树T void CreatePostThread(ThreadTree T) { ThreadNode* pre = NULL; if (T != NULL) { PostThread(T, pre); if (pre->rchild == NULL) // 处理遍历的最后一个结点(最后遍历的是根结点，可能存在右孩子) pre->rtag = 1; } } // 后续线索二叉树逆向后序遍历（找前驱结点） // 在后序线索二叉树中找到结点p的前驱结点 ThreadNode* PreNode2(ThreadNode* p) { if (p->ltag == 1) return p->lchild; else { // 此时p必有左孩子 if (p->rtag == 0) // 有右孩子，右孩子为前驱结点 return p->rchild; else // 无右孩子，左孩子为前驱结点 return p->lchild; } } // 对后序线索二叉树进行逆向后序遍历（利用线索实现的非递归算法） void PostOrder(ThreadNode* T) { for (ThreadNode* p = T; p != NULL; p = PreNode2(p)) visit(p); }
