要说 线索二叉链表，不得 不说一说 二叉链表的遍历。二叉链表的 遍历 其实 就是 将 树型结构 转换 成 一种 线性结构。不过 这种 节点 前驱 后继的关系，只能 在 遍历的时候 动态 获得。拿有没有一种方法 可以 保存 这种 前驱 后继的关系呢？ 总的来看 有 两种方法：
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;}运行截图：
都会有回报，愿你天天开心。
