树：线索二叉树详解

Love The Way You Lie 2022-05-31 09:07 181阅读 0赞

# 线索二叉树介绍 #

我们在有n个结点的二叉链表中，每个结点有指向左右2个孩子的指针域，所以有2n个指针域，而n个结点的二叉树一共有n-1条分支线，也就是说，**其实存在2n-(n-1) = n+1 个空指针域。空间十分浪费**。在另一方面，**我们对二叉树做中序遍历时，我只知道每个树结点的左右孩子是谁，却不知道该树结点的前驱和后继是谁**。**要想知道必须重新遍历一遍**。

**为什么不考虑在创建时就记住这些前驱和后继呢，那将会省去很多时间**。**仔细想想，如果我们的树结点左右孩子都不为NULL ，如果采用中序遍历，那么该结点的前驱结点是不是左孩子，后继结点是不是右孩子？这就是为什么我们要采用中序遍历的形式来对二叉树进行线索化，那么我需要将孩子结点为NULL的树结点 空间利用起来！**因为字节点虽然为NULL，但是都有前驱和后继结点，**那么我们可以考虑将 lchild 放树节点的前驱结点，rchild放树结点的后继结点**。**那么这里我们是否要考虑区分lchild，rchild 是原有的子节点还是我们后续线索化添加的前驱后继结点呢？**所以要在线索二叉树结点的数据结构都要体现呗。**我们把这种指向前驱和后继的指针称为线索，加上线索的二叉链表称为线索链表，相应的的二叉树就称为线索二叉树（Threaded Binary Tree）。**

# 线索二叉树实现思路 #

创建线索二叉树和创建普通的二叉树（二叉链表）相似，**我们同样约定采用前序遍历的方式进行创建树结点**。**如果普通二叉树不是很清楚的，请看[树：二叉链表的实现][Link 1]**。

**如何线索化二叉树呢？**我们采用中序遍历二叉树访问每一个树结点的时候，**我们只知道当前结点，如何知道前驱结点呢？****我们能否考虑将刚刚访问的结点（pre）保存下来，每次访问树结点的时候，发现左孩子结点为NULL，就将其线索化！它的前驱结点是不是pre结点呢？！tree->lchild = pre；那个刚刚访问的结点 (pre)的右孩子结点 为NULL，那么将其线索化 pre 它的后继结点是不是当前结点呢？！pre->rchild = tree；**具体详细代码请看代码实现。

下面是一张简陋的**二叉线索树的图**，**箭头方向 代表该结点前驱和后继结点。红色箭头表示 原来的孩子结点都不为空，直接就是自己的前驱或者后继结点。黑色箭头表示的通过线索添加的前驱后驱结点，都是孩子结点为NULL 而添加的**。

![SouthEast][]

#    线索二叉树代码实现 #

#define _CRT_SECURE_NO_WARNINGS
    #include <stdio.h>
    #include <stdlib.h>
    typedef char TElemType;
    //指针指向类型，Link(0) 表示为左右孩子结点，Thread(1) 表示前驱或者后驱结点
    typedef enum{Link,Thread}PointerTag;
    typedef struct BiThrNode
    {
    	TElemType data;
    	struct BiThrNode *lchild, *rchild;
    	PointerTag ltag, rtag;
    }BiThrNode,*BiThrTree;
    
    //全局变量，pre 指向刚刚访问的树结点
    BiThrTree pre = NULL;
    
    //约定前序遍历的方式 创建线索二叉树
    void CreateBiThrTree(BiThrTree* tree)
    {
    	TElemType data;
    	scanf("%c", &data);
    	if (' ' == data)
    	{
    		*tree = NULL;
    	}
    	else
    	{
    		*tree = (BiThrTree)malloc(sizeof(BiThrNode));
    		(*tree)->data = data;
    		(*tree)->ltag = (*tree)->rtag = Link;
    		CreateBiThrTree(&(*tree)->lchild);
    		CreateBiThrTree(&(*tree)->rchild);
    	}
    	return;
    }
    //中序遍历的形式 将二叉树结点 线索化
    void MidOrderTraverse_Thr(BiThrTree tree)
    {
    	if (NULL != tree)
    	{
    		//线索化左子树
    		MidOrderTraverse_Thr(tree->lchild);
    
    		if (NULL == tree->lchild)
    		{
    			tree->ltag = Thread;
    			tree->lchild = pre;
    		}
    
    		if (NULL == pre->rchild)
    		{
    			pre->rtag = Thread;
    			pre->rchild = tree;
    		}
    		pre = tree;
    		//线索化右子树
    		MidOrderTraverse_Thr(tree->rchild);
    	}
    	return;
    }
    //创建一个头结点（lchild指向二叉树根结点），配合二叉树 对二叉树进行线索化。
    void BiThrTree_Thr(BiThrTree *head, BiThrTree tree)
    {
    	//创建二叉树的头结点，头结点默认ltag为Link 指向根结点，rtag 默认为线索，rchild指向中序遍历最后一个结点（树最右的结点）
    	BiThrTree headNode = (BiThrTree)malloc(sizeof(BiThrNode));
    	headNode->ltag = Link;
    	headNode->rtag = Thread;
    	//空树 ，左右结点指向自己
    	if (NULL == tree)
    	{
    		headNode->lchild = headNode;
    		headNode->rchild = headNode;
    	}
    	else
    	{
    		pre = headNode;//pre 初始化为头结点
    		headNode->lchild = tree;
    		MidOrderTraverse_Thr(tree);
    		//线索化完毕，pre指向树中序遍历的最后一个结点（树最右边的结点）
    		pre->rtag = Thread;
    		pre->rchild = headNode;
    		headNode->rchild = pre;
    	}
    	*head = headNode;
    	return;
    }
    void visit(TElemType data)
    {
    	printf("%c ", data);
    }
    //中序遍历 线索二叉树，非递归形式
    void MidOrderTraverse(BiThrTree head)
    {
    	BiThrTree tree = head->lchild;
    	//循环结束条件：空树 或者 中序遍历完毕
    	while (tree != head)
    	{
    		//一直循环，直到找到树最左边的结点（树的中序遍历的起点）
    		while (tree->ltag == Link)
    		{
    			tree = tree->lchild;
    		}
    		visit(tree->data);
    		//循环完毕tree为中序遍历中的 根结点
    		while (tree->rtag == Thread && tree->rchild != head)
    		{
    			tree = tree->rchild;
    			visit(tree->data);
    		}
    		//进行右子树
    		tree = tree->rchild;
    	}
    	printf("\n");
    	return;
    }
    
    int main(int argc, char *argv[])
    {
    	BiThrTree tree = NULL, head = NULL;
    	printf("请输入前序遍历结点:");
    	CreateBiThrTree(&tree);
    	BiThrTree_Thr(&head, tree);
    	printf("中序遍历线索二叉树:");
    	MidOrderTraverse(head);
    	return 0;
    }

# 运行结果检测 #

注意输入是，**ABC\_\_D\_\_E\_G\_\_，下划线是空格的意思**。

![SouthEast 1][]

[Link 1]: http://blog.csdn.net/qq_29542611/article/details/79318668
[SouthEast]: /images/20220531/5ea24c0189c749c49669dfb73af1c4d6.png
[SouthEast 1]: /images/20220531/d014ac57b55a46fcaa6fcdacfc8f2de2.png