瞅数据结构写代码（28） 线索二叉链表的实现

看数据结构写代码（28） 线索二叉链表的实现

要说 线索二叉链表，不得 不说一说 二叉链表的遍历。二叉链表的 遍历 其实 就是 将 树型结构 转换 成 一种 线性结构。不过 这种 节点 前驱 后继的关系，只能 在 遍历的时候 动态 获得。拿有没有一种方法 可以 保存 这种 前驱 后继的关系呢？ 总的来看 有 两种方法：

1. 将二叉链表 加上 节点 加上 前驱 ，后继的 指针

2. 一个n个节点的 二叉树，必定有 n+1 个空链域。(n个 节点 有 2n 个 链域，这些链域 指向了 n-1 个节点（根节点没有被指），所以 空链域 = 2n - (n-1) = n + 1），那么 可以 利用 这些 空 链域 来存放前驱 后继的信息。 这样 我们 需要 增加 两个标志位, leftTag 和 rightTag，当leftTag   为 0 的时候 leftChild 指向的 是 左孩子，当为1 的 时候 表示 指向前驱 ，当 rightTag 为0 的时候 指向 右 孩子，为1 指向 后继。 这些 为1 的 链域，我们称 之为 线索。加了 线索的 二叉链表 叫做 线索二叉链表。

关于 这两种方法，书中 说的 第一种 浪费 存储空间，降低了存储密度，我就有点 不理解了， 两个指针 占用空间 为 2 * 4 = 8, 可 就算 标志位 用 枚举型 也是 占用 2*4 = 8个字节，就算 用 bool型，也没 减少 多少存储空间。为什么 不用 第一种呢？ 第一种 使用起来 多方便。 不明白，可能 自己的 境界 不够高，看得不够远吧。

还有 一点 疑惑的 是 树中 说的 头节点 的 leftChild 指向 根节点，rightChild 指向 最后一个 被访问的节点。为什么 不能 把 leftChild指向 第一个被 访问的节点呢？ 这样 对于 遍历 算法的 清晰度 更有益处。 下面 图示：

我下面的 线索花 算法 就更改了 头节点 leftChild 指向 第一个被访问的 节点。 。

至于 这样 是对， 还是错呢？ 是不是 对 其他 操作 有不便呢？ 等待 自己 回答吧。

在上代码 之前 有必要 说一下 线索二叉链表 根据 遍历 根节点 的 顺序，分为，先序遍历，中序遍历，后序遍历

除了 中序 遍历，其他的两种线索二叉链表 是 不 完善的 。

不完善 指的 是 在 查找 前驱 后继时 需要 知道 父亲 节点的信息，无法 直接 获取。

中序 查找 节点 前驱 为 左子树的 右下角，后继 为 右子树的 左下角

先序 查找 前驱 为 节点 父 节点 或者 父 节点的 左子树，需要 借助 栈，无法直接获取。查找 后继  为 左 子树 或者 右子树（左子树为空）。

后序查找 前驱 为 左子树 或者右子树，查找 后继 为  父亲的 右子树 （最后 被 访问的节点） 或者 父亲节点 ，借助栈，无法直接获取。

所以 中序 线索二叉链表 是 最合适的。 如果 想用 先序 ，后序 线索，请用 线索三叉链表。有空 实现以下吧。

说了这么多，下面 上代码吧，今天 也够累的了。

源代码网盘地址：点击打开链接

// binaryTree.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include <cstdlib>

typedef int ElementType;
enum E_State
{
	E_State_Error = 0,
	E_State_Ok = 1
};

enum E_Tag
{
	E_Tag_Link = 0,//指针，指向左右子树
	E_Tag_Threaded = 1,//线索,指向前驱后继
};

typedef  struct ThBiTreeNode
{
	ElementType data;
	ThBiTreeNode * leftChild;
	ThBiTreeNode * rightChild;
	E_Tag leftTag;
	E_Tag rightTag;
} * ThBiTree;

void treeInit(ThBiTree * tree){
	*tree = NULL;
}
//其实 自己 不懂 这个 函数 初始化...
E_State treeCreate(ThBiTree *tree){
	ElementType data;
	scanf("%d",&data);
	if (data == 0)
	{
		*tree = NULL;
	}else
	{
		*tree = (ThBiTree)malloc(sizeof(ThBiTreeNode));
		(*tree)->data = data;
		//设置 默认 E_Tag_Link
		(*tree)->leftTag = E_Tag_Link;
		(*tree)->rightTag = E_Tag_Link;
		treeCreate(&(*tree)->leftChild);
		treeCreate(&(*tree)->rightChild);
	}
	return E_State_Ok;
}


//后序遍历 销毁树
void treeClear(ThBiTree * tree){
	if (tree != NULL)
	{
		if ((*tree)->leftChild != NULL)
		{
			treeClear(&(*tree)->leftChild);
		}
		else if((*tree)->rightChild != NULL)
		{
			treeClear(&(*tree)->rightChild);
		}
		free(*tree);
		*tree = NULL;
	}
}

void treeDestory(ThBiTree * tree){
	treeClear(tree);
}

//二叉树的 中序 线索化...
void inThreading(ThBiTree tree,ThBiTree &pre){
	if (tree)
	{
		inThreading(tree->leftChild,pre);
		if (tree->leftChild == NULL)//当前节点左孩子为空
		{
			tree->leftChild = pre;
			tree->leftTag = E_Tag_Threaded;
		}
		if (pre->rightChild == NULL)//前驱右孩子为空
		{
			pre->rightChild = tree;
			pre->rightTag = E_Tag_Threaded;
		}
		pre = tree;
		inThreading(tree->rightChild,pre);
	}
}

//根课本上最大的不同，头节点 的leftChild 指向 第一个 被访问的节点.
E_State inOrderThreading(ThBiTree & head,ThBiTree tree){
	head = (ThBiTree)malloc(sizeof(ThBiTreeNode));
	if (head != NULL)
	{
		head->leftTag = E_Tag_Link;
		head->rightTag = E_Tag_Threaded;
		if (tree == NULL)//空树
		{
			head->leftChild = head;//左右孩子都指向自己
			head->rightChild = head;
		}
		else
		{
			ThBiTree pre = head;//保存线索化中的 前驱
			//head->leftChild = tree;//头指针左孩子 指向根节点..
			inThreading(tree,pre);
			pre->rightChild = head;pre->rightTag = E_Tag_Threaded;//最后一个节点 指向头指针
			//查找 第一个 被访问的节点。
			//将头节点的 左孩子 设置 成 第一个 被访问的节点.
			ThBiTree firstNode = tree;
			while (firstNode->leftTag == E_Tag_Link)
			{
				firstNode = firstNode->leftChild;
			}
			head->leftChild = firstNode;
			head->rightChild = pre;//头指针右孩子 指向最后 访问的 节点
		}
		return E_State_Ok;
	}
	return E_State_Error;
}

//获取前驱
ThBiTree treeGetPre(ThBiTree tree){
	ThBiTree pre = NULL;
	if (tree != NULL)
	{
		if (tree->leftTag == E_Tag_Threaded)
		{
			pre = tree->leftChild;
		}
		else//前驱是 左子树的 右下角
		{
			pre = tree->leftChild;
			while (pre->rightTag == E_Tag_Link)
			{
				pre = pre->rightChild;
			}
		}
	}
	return pre;
}

//获取 后继
ThBiTree treeGetNext(ThBiTree tree){
	ThBiTree next = NULL;
	if (tree != NULL)
	{
		if (tree->rightTag == E_Tag_Threaded)//当rightTag是线索是，rightChild 指向后继
		{
			next = tree->rightChild;
		}
		else//是指针时，指向右子树的最左下角
		{
			next = tree->rightChild;//不用 担心节点的 右子树 为空的问题，因为tag 不是线索，必不为空
			while (next->leftTag == E_Tag_Link)
			{
				next = next->leftChild;
			}
		}
	}
	return next;
}

//中序线索遍历..
void inOrderTraverse(ThBiTree head){
	printf("\n------------中序顺序访问--------------\n");
	ThBiTree next = head->leftChild;//指向第一个被访问的节点.
	while (next != head)//当树空时 或者 到达 结尾时
	{
		printf("%d\t",next->data);
		next = treeGetNext(next);
	}
}

//中序 逆序 遍历（查找前驱）
void inOrderTraversePre(ThBiTree head){
	printf("\n------------中序逆序访问--------------\n");
	ThBiTree pre = head->rightChild;
	while (pre != head)
	{
		printf("%d\t",pre->data);
		pre = treeGetPre(pre);
	}
}


int _tmain(int argc, _TCHAR* argv[])
{
	ThBiTree tree;
	printf("---------------创建树（先序,0代表子树为空）-----------------\n");
	treeCreate(&tree);
	ThBiTree head;
	inOrderThreading(head,tree);
	inOrderTraverse(head);
	inOrderTraversePre(head);
	return 0;
}

运行截图：