首先在这里声明一下，本篇博客参考另外一位大神的博客，博客链接如下：http://blog.csdn.net/UncleMing5371/article/details/54176252。由于写的很好理解，所以就拿来借鉴一下，主要目的也是出于学习，让自己的算法能力有所提高。如果有版权问题，欢迎私信我，我收到后立马删除。好了，看下今天的主题——线索二叉树。二叉树的其它知识可以参考以上我上篇文章，C#算法系列（1）——二叉树，在这里就不再赘述。我们先来看下线索二叉树的构建过程。
一、线索二叉树的由来
线索二叉树的本质：主要是针对在构建二叉树时存在空指针域的问题进行优化。具体来讲：对于一个有n个结点二叉链表，每个结点有指向左右孩子的两个指针域，所以一共是2n个指针域。而n个结点的二叉树一共有n-1条分支数，也就是说，其实存在2n-(n-1) = n+1个空指针域。优化的目的是将空指针域给利用起来，将空的指针域指向其前驱或后继。可是这样一来就会存在一个问题，如何区分指针域指向的是孩子结点还是前驱或后继，因此，还需要额外增加一个bool类型的标识位，进行区分。当标识位为0时，则表示的是其孩子结点，若为1时，则指向的是其前驱或后继结点。
二、线索二叉树的构建过程
（1）首先我们对二叉树进行中序遍历，将所有的结点的右指针域为空的指针域指向它的后继结点。如下图：
通过中序遍历我们知道H的right指针为空，并且H的后继节点为D（如上图第1步），I的right指针为空，并且I的后继节点为B（如上图第2步），以此类推，知道G的后继节点为null，则G的right指针指向null。
（2）接下来将这颗二叉树的所有节点左指针域为空的指针域指向它的前驱节点。如下图：
如上图，H的left指针域指向Null（如第1步），I的前驱节点是D，则I的left指针指向D，以此类推。
（3） 通过上面两步完成了整个二叉树的线索化，最后结果如下图：
通过观察上图（蓝色虚线代表后继、绿色虚线代表前驱），可以看出，线索二叉树，等于是把一棵二叉树转变成了一个“ 特殊的双向链表“(后面会解释为什么叫特殊的双向链表），这样对于我们的新增、删除、查找节点带来了方便。所以我们对二叉树以某种次序遍历使其变为线索二叉树的过程称做是线索化。如下图：
仔细分析上面的双向链表，与线索化之后的二叉树相比，比如节点D与后继节点I，在完成线索化之后，并没有直接线索指针，而是存在父子节点的指针；节点A与节点F，在线索化完成之后，节点A并没有直接指向后继节点F的线索指针，而是通过父子节点遍历可以找到最终的节点F，前驱节点也存在同样的问题，正因为很多节点之间不存在直接的线索，所以我将此双向链表称做“ 特殊的双向链表”，再使用过程中根据指针是线索指针还是子节点指针来分别处理，所以在每个节点需要标明当前的左右指针是线索指针还是子节点指针，这就需要修改节点的数据结构。修改后的数据结构如下：
class TreeNode<T>
{
private T data; //数据域
public TreeNode<T> lChild; //左孩子
public TreeNode<T> rChild; //右孩子
private bool ltag; //true表线索, false结点
private bool rtag;
public Boolean Ltag
{
get { return ltag; }
set { ltag = value; }
}
public Boolean Rtag
{
get { return rtag; }
set { rtag = value; }
}
public T Data
{
get { return data; }
set { data = value; }
}
public TreeNode(T val)
{
this.data = val;
this.lChild = null;
this.rChild = null;
}
} 最终的二叉链表修改为如下图的样子：
二、线索二叉树的代码（C#版）
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace 二叉树_线索化
{
class BinaryTree<T>
{
private TreeNode<T> pre; //指向刚刚访问过的结点
//通过数组构建二叉树
public TreeNode<T> CreatBinaryTree(T[] vals, int index)
{
TreeNode<T> root = null;
if (index < vals.Length)
{
root = new TreeNode<T>(vals[index]);
root.lChild = CreatBinaryTree(vals, index * 2 + 1);
root.rChild = CreatBinaryTree(vals, index * 2 + 2);
}
return root;
}
//中序遍历线索化
// 如果当前结点无左孩子，则刚刚访问的pre结点为当前结点的前驱
// 如果刚刚访问的pre结点无右孩子，则当前结点为pre结点的后继
public void InTreading(TreeNode<T> root)
{
if (root == null)
{
return;
}
//处理左子树
InTreading(root.lChild);
//左指针为空,将左指针指向前驱节点
if (root.lChild == null)
{
root.lChild = pre;
root.Ltag = true;
}
//前一个节点的后继节点指向当前节点
if (pre != null && pre.rChild == null)
{
pre.rChild = root;
pre.Rtag = true;
}
pre = root;
//处理右子树
InTreading(root.rChild);
}
//中序遍历线索二叉树，按照后继方式进行遍历
public void InOrderTraversal(TreeNode<T> root)
{
//1、找中序遍历方式最开始的节点
while (root != null && !root.Ltag)
{
root = root.lChild;
}
while (root != null)
{
Console.Write(root.Data + " ");
//如果右指针是线索
if (root.Rtag)
{
root = root.rChild;
}
//如果右指针不是线索，找到右子树开始的节点(即右子树最左边的结点)
else
{
root = root.rChild;
while (root != null && !root.Ltag)
{
root = root.lChild;
}
}
}
}
//中序遍历线索二叉树，按照前驱方式遍历（思路：找到最右子节点开始倒序遍历）
public void InPreOrderTraversal(TreeNode<T> root)
{
//找最后一个结点
while (root.rChild != null && !root.Rtag)
{
root = root.rChild;
}
while (root != null)
{
Console.Write(root.Data + " ");
//如果左指针是线索
if (root.Ltag)
{
root = root.lChild;
}
//如果左指针不是线索，找到左子树开始的节点
//（因为是倒序，所以最开始的结点为左子树最右边的结点）
else
{
root = root.lChild;
while (root.rChild != null && !root.Rtag)
{
root = root.rChild;
}
}
}
}
//前序线索化二叉树
public void PreThreading(TreeNode<T> root)
{
if (root == null)
{
return;
}
//左指针为空,将左指针指向前驱节点
if (root.lChild == null)
{
root.lChild = pre;
root.Ltag = true;
}
//前一个节点的后继节点指向当前节点
if (pre != null && pre.rChild == null)
{
pre.rChild = root;
pre.Rtag = true;
}
pre = root;
//如果左指针不是索引，处理左子树
if (!root.Ltag)
{
PreThreading(root.lChild);
}
//如果右指针不是索引，处理右子树
if (!root.Rtag)
{
PreThreading(root.rChild);
}
}
//前序遍历线索二叉树（按照后继线索遍历）
public void PreInTraversal(TreeNode<T> root)
{
while (root != null)
{
while (!root.Ltag)
{
Console.Write(root.Data + " ");
root = root.lChild;
}
Console.Write(root.Data + " ");
root = root.rChild;
}
}
}
}以及主程序测试类Program.cs：
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace 二叉树_线索化
{
class Program
{
static void Main(string[] args)
{
char[] data = { 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J' };
BinaryTree<char> tree = new BinaryTree<char>();
TreeNode<char> root = tree.CreatBinaryTree(data,0);
Console.WriteLine("二叉树中序线索化...");
tree.InTreading(root);
Console.Write("中序按后继节点遍历线索二叉树结果：");
tree.InOrderTraversal(root);
Console.WriteLine();
Console.Write("中序按前驱节点遍历线索二叉树结果：");
tree.InPreOrderTraversal(root);
Console.WriteLine();
TreeNode<char> root2 = tree.CreatBinaryTree(data,0);
Console.WriteLine("二叉树先序线索化...");
tree.PreThreading(root2);
Console.Write("先序按后继节点遍历线索二叉树结果：");
tree.PreInTraversal(root2);
Console.WriteLine();
Console.ReadKey();
}
}
}
实验结果截图如下：
以上若有不对或有疑问的地方欢迎私信我，谢谢！！！
参考资料：