线索化二叉树
先看一个问题，将数列{1,3,6,8,10,14}构成一颗二叉树。看到下图这个颗树能知道它是一颗完全二叉树。其中存在一个问题，它的一些指针是没有充分的利用。例如：8，10，14，6在一定程度上浪费了指针。
问题分析：
- 当我们对上面的二叉树进行中序遍历时，数列为{8,3,10,1,6,14}
- 但是6,8,10,14这几个节点的左右指针，并没有完全的利用上。
- 如果我们希望充分的利用各个节点的左右市镇，让各个节点可以指向自己的前后节点怎么做？解决方案是线索二叉树。
线索化二叉树概念
- N个节点的二叉链表中含有N 1公式2n-(n-1)=n 1个空指针域。利用二叉链表中的空指针域，存放指向节点再某种遍历次序下的前序和后续的节点的指针（这种附加的指针称为“线索”）。
- 这种加上了线索的二叉链表称为线索链表，相应的二叉树称为线索二叉树（Threaded BinaryTree）。根据线索性质的不同，线索二叉树可分为前序线索二叉树、中序线索二叉树和后序线索二叉树三种。
- 一个节点的前一个节点，称为前驱节点。
- 一个节点的后一个节点，称为后继节点。
案例
将下面的二叉树，进行中序线索二叉树。中序遍历的数列为{8,3,10,1,14,6}
思路分析
当线索化二叉树后，Node节点的属性left和right，有如下情况：
- left指向的是左子树，也可能是指向的前驱节点。比如1节点left指向的左子树，而10节点的left指向的就是前驱节点。
- right指向的是右子树，也可能是指向后续节点，比如1节点right指向的是右子树，而10节点的right指向的是后继节点。
代码
代码语言：javascript复制 public class ThreadedBinaryNode
{
public int Id { get; set; }
public string Name { get; set; }
public ThreadedBinaryNode Left { get; set; }
public ThreadedBinaryNode Right { get; set; }
//如果LeftType==0表示指向的是左子树，如果是1则表示指向前驱节点
//如果RightType表示指向的是右子树，如果是1则表示指向后继节点
public int LeftType { get; set; }
public int RightType { get; set; }
public ThreadedBinaryNode(int id, string name)
{
this.Id = id;
this.Name = name;
}
public override string ToString()
{
return $"TreeNode [id = { Id } , name ={ Name }]";
}
/// <summary>
/// 前序遍历
/// </summary>
public void PreOrder()
{
Console.WriteLine(this);
//递归向左子树前序遍历
if (this.Left != null)
{
this.Left.PreOrder();
}
//递归向右子树前序遍历
if (this.Right != null)
{
this.Right.PreOrder();
}
}
/// <summary>
/// 中序遍历
/// </summary>
public void InfixOrder()
{
//递归向左子树中序遍历
if (this.Left != null)
{
this.Left.InfixOrder();
}
//输出父节点
Console.WriteLine(this);
//递归向右子树中序遍历
if (this.Right != null)
{
this.Right.InfixOrder();
}
}
/// <summary>
/// 后续遍历
/// </summary>
public void PostOrder()
{
if (this.Left != null)
{
this.Left.PreOrder();
}
if (this.Right != null)
{
this.Right.PreOrder();
}
Console.WriteLine(this);
}
/// <summary>
/// 前序遍历查找
/// </summary>
/// <param name="id">根据id查找节点</param>
/// <returns></returns>
public ThreadedBinaryNode PreOrderSearch(int id)
{
Console.WriteLine("前序遍历查找" DateTime.Now);
//比较当前节点是不是
if (this.Id == id)
{
return this;
}
//1.则判断当前节点的左子节点是否为空，如果不为空，则递归前序查找
//2.如果左递归前序查找，找到节点，则返回
ThreadedBinaryNode resNode = null;
if (this.Left != null)
{
resNode = this.Left.PreOrderSearch(id);
}
//说明我们左子树找到
if (resNode != null)
{
return resNode;
}
//左递归前序查找，找到站点，则返回，否则继续判断
//当前的节点的右子节点是否为空，如果不为空，则继续向右递归前序查找。
if (this.Right != null)
{
resNode = this.Right.PreOrderSearch(id);
}
return resNode;
}
//中序遍历查找
public ThreadedBinaryNode InfixOrderSearch(int id)
{
ThreadedBinaryNode resNode = null;
if (this.Left != null)
{
resNode = this.Left.InfixOrderSearch(id);
}
if (resNode != null)
{
return resNode;
}
Console.WriteLine("中序遍历查找" DateTime.Now);
if (this.Id == id)
{
return this;
}
if (this.Right != null)
{
resNode = this.Right.InfixOrderSearch(id);
}
return resNode;
}
//后序遍历查找
public ThreadedBinaryNode PostOrderSearch(int id)
{
ThreadedBinaryNode resNode = null;
if (this.Left != null)
{
resNode = this.Left.PostOrderSearch(id);
}
if (resNode != null)
{
return resNode;
}
if (this.Right != null)
{
resNode = this.Right.PostOrderSearch(id);
}
if (resNode != null)
{
return resNode;
}
Console.WriteLine("后序遍历查找" DateTime.Now);
if (this.Id == id)
{
return this;
}
return resNode;
}
/// <summary>
/// 根据id删除指定节点
/// </summary>
/// <param name="id"></param>
public void DeleteNode(int id)
{
if (this.Left != null && this.Left.Id == id)
{
this.Left = null;
return;
}
if (this.Right != null && this.Right.Id == id)
{
this.Right = null;
return;
}
if (this.Left != null)
{
this.Left.DeleteNode(id);
}
if (this.Right != null)
{
this.Right.DeleteNode(id);
}
}
}
//定义ThreadedBinaryTree实现了线索化功能的二叉树
public class ThreadedBinaryTree
{
private ThreadedBinaryNode root;
//为了线索化，需要创建给指向当前节点的前驱节点的指针
//在递归进行线索化时，pre总是保留前一个节点
private ThreadedBinaryNode preNode;
public void SetRoot(ThreadedBinaryNode root)
{
this.root = root;
}
public void SetThreadedBinaryNode()
{
SetThreadedBinaryNode(root);
}
/// <summary>
/// 线索化方法（中序）
/// </summary>
/// <param name="node">当前需要线索化的节点</param>
public void SetThreadedBinaryNode(ThreadedBinaryNode node)
{
if (node == null) return;
//1.先线索化左子树
SetThreadedBinaryNode(node.Left);
//2.线索化当前节点
//处理当前节点的前驱节点
if (node.Left == null)
{
//让当前节点的左指针，指向前驱节点
node.Left = preNode;
//修改当前节点的左指针类型，指向的前驱节点
node.LeftType = 1;
}
//处理后继节点
if (preNode != null && preNode.Right == null)
{
//让前驱节点的右指针指向当前节点
preNode.Right = node;
//修改前驱节点的右指针类型
preNode.RightType = 1;
}
//每处理一个节点后，让当前节点是下一个节点的前驱节点
preNode = node;
//3.再线索化右子树
SetThreadedBinaryNode(node.Right);
}
//前序遍历
public void PreOrder()
{
if (this.root != null)
{
this.root.PreOrder();
}
else
{
Console.WriteLine("二叉树为空，无法遍历！");
}
}
//中序遍历
public void InfixOrder()
{
if (this.root != null)
{
this.root.InfixOrder();
}
else
{
Console.WriteLine("二叉树为空，无法遍历！");
}
}
//后续遍历
public void PostOrder()
{
if (this.root != null)
{
this.root.PostOrder();
}
else
{
Console.WriteLine("二叉树为空，无法遍历！");
}
}
/// <summary>
/// 前序遍历查找
/// </summary>
/// <param name="id">根据id查找节点</param>
/// <returns></returns>
public ThreadedBinaryNode PreOrderSearch(int id)
{
if (root != null)
{
return root.PreOrderSearch(id);
}
else
{
return null;
}
}
//中序遍历查找
public ThreadedBinaryNode InfixOrderSearch(int id)
{
if (root != null)
{
return root.InfixOrderSearch(id);
}
else
{
return null;
}
}
//后序遍历查找
public ThreadedBinaryNode PostOrderSearch(int id)
{
if (root != null)
{
return root.PostOrderSearch(id);
}
else
{
return null;
}
}
public void DeleteNode(int id)
{
if (root != null)
{
if (root.Id == id)
{
root = null;
}
else
{
root.DeleteNode(id);
}
}
else
{
Console.WriteLine("空树无法删除！");
}
}
}调用
代码语言：javascript复制 static void Main(string[] args)
{
ThreadedBinaryNode root = new ThreadedBinaryNode(1,"tom");
ThreadedBinaryNode node2 = new ThreadedBinaryNode(3,"jack");
ThreadedBinaryNode node3 = new ThreadedBinaryNode(6,"simth");
ThreadedBinaryNode node4 = new ThreadedBinaryNode(8,"mary");
ThreadedBinaryNode node5 = new ThreadedBinaryNode(10,"king");
ThreadedBinaryNode node6 = new ThreadedBinaryNode(14,"dim");
root.Left = node2;
root.Right = node3;
node2.Left = node4;
node2.Right = node5;
node3.Right = node6;
ThreadedBinaryTree threadedBinaryTree = new ThreadedBinaryTree();
threadedBinaryTree.SetRoot(root);
threadedBinaryTree.SetThreadedBinaryNode();
ThreadedBinaryNode leftNode = node5.Left;
Console.WriteLine("10号节点的前驱节点是：" leftNode);
ThreadedBinaryNode rightNode = node5.Right;
Console.WriteLine("10号节点的后继节点是：" rightNode);
Console.Read();
}运行效果
接下来我们继续探索，如何遍历线索化二叉树
对前面的中序线索化的二叉树，进行遍历。
因为线索化后，各个节点指向有变化，因此原来的遍历方式不能使用，这是需要使用心的遍历方式线索化二叉树，各个节点可以通过线型方式遍历，因此无需使用递归方式，这样也提高了遍历的效率。遍历的次序应当和中序遍历保持一致。
代码：
代码语言：javascript复制 //遍历线索化二叉树的方法
public void ThreadedList()
{
//定义一个变量，存储当前遍历的节点，从root开始
ThreadedBinaryNode tempNode = root;
while (tempNode != null)
{
//循环找到lefttype == 1 的节点，第一个找到就是8节点
//后面随着遍历而变化，因为lefttype==1时，说明该节点时按照线索化
while (tempNode.LeftType == 0)
{
tempNode = tempNode.Left;
}
//打印当前节点
Console.WriteLine(tempNode);
//如果当前节点的右指针指向的时后续节点，就一直输出
while (tempNode.RightType == 1)
{
//获取到当前节点的后继节点
tempNode = tempNode.Right;
Console.WriteLine(tempNode);
}
//替换这个遍历的节点
tempNode = tempNode.Right;
}
}调用：
代码语言：javascript复制 static void Main(string[] args)
{
ThreadedBinaryNode root = new ThreadedBinaryNode(1,"tom");
ThreadedBinaryNode node2 = new ThreadedBinaryNode(3,"jack");
ThreadedBinaryNode node3 = new ThreadedBinaryNode(6,"simth");
ThreadedBinaryNode node4 = new ThreadedBinaryNode(8,"mary");
ThreadedBinaryNode node5 = new ThreadedBinaryNode(10,"king");
ThreadedBinaryNode node6 = new ThreadedBinaryNode(14,"dim");
root.Left = node2;
root.Right = node3;
node2.Left = node4;
node2.Right = node5;
node3.Left = node6;
ThreadedBinaryTree threadedBinaryTree = new ThreadedBinaryTree();
threadedBinaryTree.SetRoot(root);
threadedBinaryTree.SetThreadedBinaryNode();
ThreadedBinaryNode leftNode = node5.Left;
Console.WriteLine("10号节点的前驱节点是：" leftNode);
ThreadedBinaryNode rightNode = node5.Right;
Console.WriteLine("10号节点的后继节点是：" rightNode);
Console.WriteLine("线索化的方式遍历线索化二叉树");
threadedBinaryTree.ThreadedList();// 8,3,10,1,14,6
//当线索化二叉树后，能在
Console.Read();
}运行效果：
