1. 概念
引入一种线性化的方法,将二叉树也具有这种前驱找后继的性能
不管是先序还是后序,最重要的一点就是:要访问左右孩子的时候,无法通过指针NULL去判断它是否存在,只能通过
ltag、rtag
2.先序遍历对二叉树线索化
- 遍历二叉树中所有的结点,然后将每对前驱和后继结点进行判断;
- 如果前驱结点的右孩子为空,将右孩子指针指向后继结点;
- 如果后继结点的左孩子为空,将左孩子指向前驱结点。

// 先序遍历方法线索化二叉树 // 注意:前驱的指针传地址,防止丢失 void preOrderThread(ThreadBiTree T, ThreadBiTNode*& preNode) { if (T == NULL) return; // 左孩子为空,建立前驱线索 if (T->lchild == NULL) { T->ltag = 1; // 标记左孩子指针用于线索 T->lchild = preNode; // printf("%d %c %d\n", T->ltag, T->data, T->rtag); } // 右子树为空且前驱结点不为空,建立后继线索 if (preNode != NULL && preNode->rchild == NULL) { preNode->rtag = 1; preNode->rchild = T; // printf("%d %c %d\n", preNode->ltag, preNode->data, preNode->rtag); } preNode = T; // 注意: // 前面修改结点的指针域,不是使用T->lchild == NULL的方式判空 // 可以使用 T->ltag == 0 方式判断左孩子是否存在 if(T->ltag == 0) preOrderThread(T->lchild, preNode); if(T->rtag == 0) preOrderThread(T->rchild, preNode); } void preOrderCreateThreadTree(ThreadBiTree T) { ThreadBiTNode* preNode = NULL; preOrderThread(T, preNode); }
3. 遍历线索化二叉树(先序)
线索化后,就可以通过当前结点获得它的后继,之后即可将整个序列输出。(先序遍历)
- 根(前驱)→ 左孩子(左子树跟)(后继);
- 如果左子树不存在,它的后继就是右孩子(右子树根);
- 如果左右孩子都不存在,那么右孩子一定是线索,通过线索获得后继;
- 即左孩子不存在,后继一定是右孩子指针域指向的结点
// 遍历先序线索化二叉树 void preOrderThreadTree(ThreadBiTree T) { ThreadBiTNode* postNode = NULL; // 后继结点 ThreadBiTNode* preNode = T; // 前驱结点 // 先序遍历时,第一个前驱结点一定时根结点 // 先序遍历:根 -> 左孩子 -> 右孩子 while (preNode != NULL) { // 如果左孩子存在,一定是preNode的后继 if (preNode->ltag == 0) { postNode = preNode->lchild; } else { postNode = preNode->rchild; } printf("%c ", preNode->data); preNode = postNode; // 将后继更新为前驱 } }
递归遍历
void preOrderThreadTree2(ThreadBiTree T) { if (T == NULL) return; printf("%c ", T->data); if (T->ltag == 0) { preOrderThreadTree2(T->lchild); } else preOrderThreadTree2(T->rchild); }
4. 中序遍历线索化二叉树
关键过程与先序遍历线索化找后继有区别,但本质还是前驱带后继的规律。
- 左孩子为空,指向它中序遍历序列的前驱;右孩子为空,指向它中序遍历的后继。
- 生成中序遍历线索树的过程,无非就是使用中序遍历获得前驱与后继,然后再将这些以获得的信息当作线索存储到结点中。
- 最后,就能使用前驱带后继的方式来获得整个中序遍历序列。

// 中序遍历方法线索化二叉树 // 注意:前驱的指针传地址,防止丢失 void inOrderThread(ThreadBiTree T, ThreadBiTNode*& preNode) { if (T == NULL) return; inOrderThread(T->lchild, preNode); if (T->lchild == NULL) { T->ltag = 1; T->lchild = preNode; printf("%d %c %d\n", T->ltag, T->data, T->rtag); } if (preNode != NULL && preNode->rchild == NULL) { preNode->rtag = 1; preNode->rchild = T; printf("%d %c %d\n", preNode->ltag, preNode->data, preNode->rtag); } preNode = T; if (T->rtag == 0) inOrderThread(T->rchild, preNode); } void inOrderCreateThreadTree(ThreadBiTree T) { ThreadBiTNode* preNode = NULL; inOrderThread(T, preNode); }
4. 遍历线索化二叉树(中序)
- 在中序遍历中,访问完根之后,下一个访问根的后继节点,一定是在右子树中。
- 并且,不管是左子树还是右子树中,第一个访问的结点一定是最坐下的结点。
- 如果前驱结点的右孩子不存在,那么线索化完成之后,右孩子指针一定指向后继,可以通过右孩子指针获得后继。
获取中序线索树中第一个被访问的结点
// 寻找中序线索二叉树中第一个被中序遍历的结点 ThreadBiTNode* getFirstInOrderNode(ThreadBiTree T) { ThreadBiTNode* pNode = T; // 注意:访问最左下结点 // 左孩子存在的依据是 ltag 为 0 while (pNode->ltag == 0) { pNode = pNode->lchild; } return pNode; }
在中序线索树中寻找一个结点的后继
// 在中序线索二叉树中找到结点pNode的后继结点 // 在右子树的最坐下节点 ThreadBiTNode* getNextInOrderNode(ThreadBiTNode* pNode) { if (pNode->rtag == 0) // 若存在右子树 { // 后继结点为右子树第一个被访问的结点 return getFirstInOrderNode(pNode->rchild); } else // 若不存在右子树,rchild 指向的即为后继节点 return pNode->rchild; }
中序遍历线索二叉树
// 中序线索树找中序后继 void inOrderThreadTree(ThreadBiTree T) { ThreadBiTNode* preNode = NULL; // 指向前驱结点 preNode = getFirstInOrderNode(T); while (preNode != NULL) { printf("%c ", preNode->data); preNode = getNextInOrderNode(preNode); // 更新前驱 } }