数据结构之线索二叉树-平芜编程栈

一文读懂线索二叉树的原理与用法

前言须知

先了解以下概念，再来学习线索二叉树⬇️

前驱结点：二叉树里的前驱结点，是某一种遍历顺序下，上一个被遍历的结点。不同的遍历顺序（中序、前序、后序），同一个节点的前驱节点可能完全不同。
后继结点：二叉树里的前驱结点，是某一种遍历顺序下，下一个被遍历的结点。不同的遍历顺序（中序、前序、后序），同一个节点的前驱节点可能完全不同。

而所谓的中序前驱和中序后继，只不过是按照中序遍历的顺序，上一个被访问的结点和下一个被访问的结点，后序前驱和后序后继，以及先序前驱和先序后继也是一样的，按照先序/后序的遍历顺序，上一个被访问的结点和下一个被访问的结点。
注：本文只会用到一个二叉树结构，以下图所示⬇️

此二叉树的中序序列是：D(1) -> G(2) -> B(3) -> E(4) -> A(5) -> F(6) -> C(7)

括号内的数字表示遍历顺序，D(1)：表示D结点是第一个遍历的结点

结点B的中序前驱就是G ，中序后继就是E，可以发现除了第一个被遍历的结点没有前驱结点，和最后一个被遍历的结点没有后继结点外，其他结点都有且只有一个前驱和后继结点。

思考两个问题

问题1：找到q结点的中序前驱和中序后继？

算法实现：

找中序前驱：从根结点出发，中序递归遍历该二叉树，若当前访问的结点p如果与q相等，pre就是G的中序前驱，反之不相等，pre = p让pre 指向正在访问的结点p。

找中序后继：从根结点出发，中序递归该二叉树，若pre == q，则p就是q的中序后继，反之，pre = p,让pre 指向正在访问的结点p。
代码实现：

voidfind_pre_in_order(BinaryTree p,BinaryTreeNode*q,BinaryTreeNode*&pre,BinaryTreeNode*&final){if(p!=NULL){find_pre_in_order(p->lchild,q,pre,final);if(p==q)// 若当前访问的p结点与目标结点相等final=pre;// final 指向 q 的前驱elsepre=p;// pre 指向当前结点 p的前驱find_pre_in_order(p->rchlid,q,pre,final);}}// 对外接口：找指定节点q的中序前驱BinaryTreeNode*FindPreNode(BinaryTree T,BinaryTreeNode*q){/* T : 查找范围是T这棵二叉树 q : 目标结点 */BinaryTreeNode*final=NULL;BinaryTreeNode*pre=NULL;find_pre_in_order(T,q,pre,final);returnfinal;}voidfind_post_in_order(BinaryTree p,BinaryTreeNode*q,BinaryTreeNode*&pre,BinaryTreeNode*&final){if(p!=NULL){find_post_in_order(p->lchild,q,pre,final);if(pre==q)// 若当前访问的p结点与目标结点相等final=p;// final 指向 q 的后继\ elsepre=p;// pre 指向当前结点 p的前驱find_post_in_order(p->rchlid,q,pre,final);}}// 对外接口：找指定节点q的中序后继BinaryTreeNode*FindPostNode(BinaryTree T,BinaryTreeNode*q){/* T : 查找范围是T这棵二叉树 q : 目标结点 */intflag=1;BinaryTreeNode*final=NULL;BinaryTreeNode*pre=NULL;find_post_in_order(T,q,pre,final,&flag);returnfinal;}

问题2：从G结点开始，继续往后中序遍历？

算法实现：G结点只保存了其左孩子和右孩子的地址，没有办法从G结点开始，继续向下遍历，只能从根结点开始找G结点不断地找后继结点，直到找到最后一个遍历的结点为止。

这个算法的时间复杂度是O(N^2)

代码实现：

// FindPostNode()内部调用voidfind_post_in_order(BinaryTree p,BinaryTreeNode*q,BinaryTreeNode*&pre,BinaryTreeNode*&final);// 对外接口：找指定节点q的中序后继BinaryTreeNode*FindPostNode(BinaryTree T,BinaryTreeNode*q);// 打印结点数据voidvisit(BinaryTreeNode*p);// 中序遍历中序线索二叉树voidInOrder(BinaryTree T){if(T!=NULL){BinaryTreeNode*first=T;// 第一个被访问的结点while(first->lchild!=NULL)first=first->lchild;for(BinaryTreeNode*p=first;p!=NULL,FindPostNode(T,p)){visit(p);}}}

接下来引入线索二叉树来有效的解决上面的问题

线索二叉树

线索二叉树是对普通二叉树的一种优化存储结构，核心目的是利用二叉树中空闲的指针域（空链域），存储节点在某种遍历序列下的前驱和后继节点地址，从而避免在遍历二叉树时使用栈或递归，提升遍历效率。

1. 普通二叉树的指针浪费问题

在一棵有 n 个节点的二叉树中，每个节点有2 个指针域（左孩子lchild、右孩子rchild），总共有 2n 个指针域。

但二叉树的边数只有 n−1 条（除了根节点，每个节点都有一个父节点），因此空闲的指针域数量为：

2n−(n−1)=n+1

这些空闲指针域被白白浪费，线索二叉树就是把这些空闲指针改造为线索。

2. 三种线索二叉树

先序线索化: 按照先序遍历序列的顺序，将普通二叉树的空链域指向当前结点前驱和后继。
中序线索化: 按照中序遍历序列的顺序，将普通二叉树的空链域指向当前结点前驱和后继
后序线索化:按照后序遍历序列的顺序，将普通二叉树的空链域指向当前结点前驱和后继。

普通二叉树—》线索化 -》线索二叉树

普通二叉树—》中序线索化 -》中序线索二叉树。

3. 线索二叉树的存储结构

#defineElemTypechar// 线索二叉树结点的数据域类型typedefstructThreadBinaryTreeNode{ElemType data;structThreadBinaryTreeNode*lchild,rchild;intltag,rtag;// 标志位，标志左右孩子指针指向的是前驱和后继，还是左右孩子结点}*ThreadBTree,ThreadBTreeNode;/* 若ltag==1，表示lchild指向的是前驱 若ltag==0, 表示lchild指向的是左孩子 若rtag==1，表示rchild指向的是后继 若rtag==0, 表示rchild指向的是左孩子 */

4. 手画线索二叉树

此处，只举例手画中序线索二叉树，后序和先序的步骤类似

得到二叉树的中序遍历序列：D(1) -> G(2) -> B(3) -> E(4) -> A(5) -> F(6) -> C(7)。
在每个结点的旁边写上被遍历的顺序。
将所有结点的空链域，用虚线指向该结点的前驱和后继。

手画结果：

5. 代码实现线索化

中序线索化代码实现：

voidin_thread(ThreadBTree P,ThreaBTreeNode*&pre){if(P!=NULL){in_thread(P->lchild,pre);if(P->lchild==NULL){P->lchilPd=pre;P->ltag=1;}if(pre!=NULL&&pre->rchild==NULL){pre->rchild=P;pre->rtag=1;}pre=P;in_thread(P->rchild,pre);}}// 构建中序线索二叉树voidCreateInThreadBTree(ThreadBTree T){ThreadBTreeNode*pre=NULL;in_thread(T,pre);if(pre->rchild==NULL)// 处理最后一个被访问的结点（注：可以去掉if直接修改标志位，中序遍历最后一个结点的右孩子一定非空）pre->rtag=1;}

先序线索化代码实现

voidpre_thread(ThreadBTree P,ThreadBTreeNode*&pre){if(P!=NULL){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_thread(P->lchild,pre);pre_thread(P->rchild,pre);}}// 构建先序线索二叉树voidCreatePreThreadBTree(ThreadBTree T){ThreadBTreeNode*pre=NULL;pre_thread(T,pre);if(pre->rchild==NULL){// 处理最后一个被访问的结点（注：可以去掉if直接修改标志位，线序遍历最后一个结点的右孩子一定非空）pre->rtag=1;}}

后序线索化代码实现：

voidpost_thread(ThreadBTree P,ThreadBTreeNode*&pre){if(P!=NULL){pre_thread(P->lchild,pre);pre_thread(P->rchild,pre);if(P->lchild==NULL){P->lchild=pre;P->ltag=1;}if(pre!=NULL&&pre->rchild==NULL){pre->rchild=P;pre->rtag=1;}pre=p;}}// 构建后序线索二叉树voidCreatePostThreadBTree(ThreadBTree T){ThreadBTreeNode*pre=NULL;post_thread(T,pre);if(pre->rchild==NULL){pre->rtag=1;}}

中序线索二叉树的前驱和后继

问题1：找到q结点的中序前驱和中序后继？
问题2：从G结点开始，继续往后中序遍历？

前面提到的两个问题，都可以用中序线索二叉树有效地解决

在中序线索二叉树中找前驱和后继

// 找中序前驱ThreadBTreeNode*FindInOrderPreNode(ThreadBTreeNode*q){if(q!=NULL){if(q->ltag==1)returnq->lchild;else// q->ltag == 0{ThreadBTreeNode*p=q->lchild;while(p->rtag==0)// 找最右下的结点p=p->rchild;returnp;}}}// 找中序后继ThreadBTreeNode*FindInOrderPostNode(ThreadBTreeNode*q){if(q!=NULL){if(q->rtag==1)returnq->lchild;else// q->rtag == 0{ThreadBTreeNode*p=q->rchild;while(p->ltag==0)// 找最左下的结点p=p->lchild;returnp;}}}

从G节点开始继续往后遍历（本质就是不断地找G的后继结点）

// 找中序后继ThreadBTreeNode*FindInOrderPostNode(ThreadBTreeNode*q);// 打印结点数据voidvisit(ThreadBTreeNode*p);// 中序遍历中序线索二叉树voidInOrder(ThreadBTree T){if(T!=NULL){ThreadBTreeNode*first_node=T;if(T->ltag==0)first_node=T->lchild;while(first_node->ltag==0)first_node=first_node->lchild;// 线索二叉树T第一个被访问的结点for(ThreadBTreeNode*p=first_node;p!=NULL;p=FindInOrderPostNode(p)){visit(p);}}}

至此这两个问题就都解决啦😄

拓展部分

拓展先序线索二叉树找前驱和后继

// 找先序后继ThreadBTreeNode*FindPreOrderPostNode(ThreadBTreeNode p){if(p!=NULL){if(p->rtag==1)returnp->rchild;else{if(p->ltag==0)returnp->lchild;elsereturnp->rchild;}}}

假设可以从p结点访问到他的双亲，那么会出现以下情况

先序线索二叉树的先序遍历

// 找先序后继ThreadBTreeNode*FindPreOrderPostNode(ThreadBTreeNode p);// 打印p结点voidvisit(ThreadBTreeNode*p);// 先序遍历voidpreOrder(ThreadBTreeNode T){if(T!=NULL){ThreadBTreeNode*first_node=T;for(ThreadBTreeNode*p=first_node;p!=NULL;FindPreOrderPostNode(p)){visit(p);}}// 第一个被遍历的结点一定是根结点}

后序线索二叉树的前驱

// 找后序前驱ThreadBTreeNode*FindPostOrderPreNode(ThreadBTreeNode p){if(p!=NULL){if(p->ltag==1)returnp->lchild;else{if(p->rtag==0)returnp->rchild;elsereturnp->lchild;}}}