算法系列15天速成 第十二天 树操作【中】
先前说了树的基本操作，我们采用的是二叉链表来保存树形结构，当然二叉有二叉的困扰之处，比如我想找到当前结点的“前驱”和“后继”，那么我们就必须要遍历一下树，然后才能定位到该“节点”的“前驱”和“后继”，每次定位都是o（n），这不是我们想看到的，那么有什么办法来解决呢？
（1） 在节点域中增加二个指针域，分别保存“前驱”和“后继”，那么就是四叉链表了，哈哈，还是有点浪费空间啊。
（2） 看下面的这个二叉树，我们知道每个结点有2个指针域，4个节点就有8个指针域，其实真正保存节点的指针
仅有3个，还有5个是空闲的，那么为什么我们不用那些空闲的指针域呢，达到资源的合理充分的利用。
一： 线索二叉树
1 概念
刚才所说的在空闲的指针域里面存放“前驱”和“后继”就是所谓的线索。
<1> 左线索： 在空闲的左指针域中存放该“结点”的“前驱”被认为是左线索。
<2> 右线索： 在空闲的右指针域中存放该“结点“的”后继“被认为是右线索。
当“二叉链表”被套上这种线索，就被认为是线索链表，当“二叉树”被套上这种线索就被认为是线索二叉树，当然线索根据
二叉树的遍历形式不同被分为“先序线索”，“中序线索”，“后序线索”。
2 结构图
说了这么多，我们还是上图说话，就拿下面的二叉树，我们构建一个中序线索二叉树，需要多动动脑子哟。
<1> 首先要找到“中序遍历”中的首结点d，因为“d结点”是首节点，所以不存在“前驱”，左指针自然是空，
”d节点”的右指针存放的是“后继”，那么根据“中序遍历”的规则应该是b，所以d的右指针存放着b节点。
<2> 接着就是“b节点”，他的左指针不为空，所以就不管了，但是他的“右指针”空闲，根据规则“b结点“的右
指针存放的是"a结点“。
<3> 然后就是“a节点”，他已经被塞的满满的，所以就没有“线索”可言了。
<4> 最后就是“c节点”，根据规则，他的“左指针”存放着就是“a节点“，”c节点“是最后一个节点，右指针自然就是空的，你懂的。
3 基本操作
常用的操作一般有“创建线索二叉树”，”查找后继节点“，”查找前驱节点“，”遍历线索二叉树“，下面的操作我们就以”中序遍历“来创建中序线索二叉树。
<1> 线索二叉树结构
从“结构图”中可以看到，现在结点的指针域中要么是”子节点（subtree）“或者是”线索（thread）“，此时就要设立标志位来表示指针域存放的是哪一种。
#region 节点标识(用于判断孩子是节点还是线索)
/// <summary>
/// 节点标识(用于判断孩子是节点还是线索)
/// </summary>
public enum nodeflag
{
subtree = 1,
thread = 2
}
#endregion
#region 线索二叉树的结构
/// <summary>
/// 线索二叉树的结构
/// </summary>
/// <typeparam name="t"></typeparam>
public class threadtree<t>
{
public t data;
public threadtree<t> left;
public threadtree<t> right;
public nodeflag leftflag;
public nodeflag rightflag;
}
#endregion
<2> 创建线索二叉树
刚才也说了如何构建中序线索二叉树，在代码实现中，我们需要定义一个节点来保存当前节点的前驱，我练习的时候迫不得已，只能使用两个
ref来实现地址操作，达到一个tree能够让两个变量来操作。
#region 中序遍历构建线索二叉树
/// <summary>
/// 中序遍历构建线索二叉树
/// </summary>
/// <typeparam name="t"></typeparam>
/// <param name="tree"></param>
public void bintreethreadingcreate_ldr<t>(ref threadtree<t> tree, ref threadtree<t> prevnode)
{
if (tree == null)
return;
//先左子树遍历，寻找起始点
bintreethreadingcreate_ldr(ref tree.left, ref prevnode);
//如果left为空，则说明该节点可以放“线索”
tree.leftflag = (tree.left == null) ? nodeflag.thread : nodeflag.subtree;
//如果right为空，则说明该节点可以放“线索”
tree.rightflag = (tree.right == null) ? nodeflag.thread : nodeflag.subtree;
if (prevnode != null)
{
if (tree.leftflag == nodeflag.thread)
tree.left = prevnode;
if (prevnode.rightflag == nodeflag.thread)
prevnode.right = tree;
}
//保存前驱节点
prevnode = tree;
bintreethreadingcreate_ldr(ref tree.right, ref prevnode);
}
#endregion
<3> 查找后继结点
现在大家都知道，后继结点都是保存在“结点“的右指针域中，那么就存在”两种情况“。
《1》 拿“b节点“来说，他没有右孩子，则肯定存放着线索（thread),所以我们直接o（1）的返回他的线索即可。
《2》 拿“a节点”来说，他有右孩子，即右指针域存放的是subtree，悲哀啊，如何才能得到“a节点“的后继呢？其实也很简单，
根据”中序“的定义，”a节点“的后继必定是”a节点“的右子树往左链找的第一个没有左孩子的节点（只可意会，不可言传，嘻嘻）。
#region 查找指定节点的后继
/// <summary>
/// 查找指定节点的后继
/// </summary>
/// <typeparam name="t"></typeparam>
/// <param name="tree"></param>
public threadtree<t> bintreethreadnext_ldr<t>(threadtree<t> tree)
{
if (tree == null)
return null;
//如果查找节点的标志域中是thread，则直接获取
if (tree.rightflag == nodeflag.thread)
return tree.right;
else
{
//根据中序遍历的规则是寻找右子树中中序遍历的第一个节点
var rightnode = tree.right;
//如果该节点是subtree就需要循环遍历
while (rightnode.leftflag == nodeflag.subtree)
{
rightnode = rightnode.left;
}
return rightnode;
}
}
#endregion
<4> 查找前驱节点
这个跟（3)的操作很类似，同样也具有两个情况。
《1》 拿“c结点”来说，他没有“左子树”，则说明“c节点”的左指针为thread，此时，我们只要返回左指针域即可得到前驱结点。
《2》 拿"a节点“来说，他有”左子树“，则说明”a节点“的左指针为subtree，那么怎么找的到”a节点“的前驱呢？同样啊，根据
”中序遍历“的性质，我们可以得知在”a节点“的左子树中往”右链“中找到第一个没有”右孩子“的节点。
#region 查找指定节点的前驱
/// <summary>
/// 查找指定节点的前驱
/// </summary>
/// <typeparam name="t"></typeparam>
/// <param name="tree"></param>
/// <returns></returns>
public threadtree<t> bintreethreadprev_ldr<t>(threadtree<t> tree)
{
if (tree == null)
return null;
//如果标志域中存放的是线索，那么可以直接找出来
if (tree.leftflag == nodeflag.thread)
return tree.left;
else
{
//根据”中序“的规则可知，如果不为thread，则要找出左子树的最后节点
//也就是左子树中最后输出的元素
var leftnode = tree.left;
while (leftnode.rightflag == nodeflag.subtree)
leftnode = leftnode.right;
return leftnode;
}
}
#endregion
<5> 遍历线索二叉树
因为我们构建线索的时候采用的是“中序”，那么我们遍历同样采用“中序”，大家是否看到了“线索”的好处，此时我们找某个节点的时间复杂度变为了
o(1) ~0(n)的时间段，比不是线索的时候查找“前驱"和“后继”效率要高很多。
#region 遍历线索二叉树
/// <summary>
/// 遍历线索二叉树
/// </summary>
/// <typeparam name="t"></typeparam>
/// <param name="tree"></param>
public void bintreethread_ldr<t>(threadtree<t> tree)
{
if (tree == null)
return;
while (tree.leftflag == nodeflag.subtree)
tree = tree.left;
do
{
console.write(tree.data + "\t");
tree = bintreethreadnext_ldr(tree);
} while (tree != null);
}
#endregion
最后上一下总的运行代码
using system;
using system.collections.generic;
using system.linq;
using system.text;
namespace threadchaintree
{
class program
{
static void main(string[] args)
{
threadtreemanager manager = new threadtreemanager();
//生成根节点
threadtree<string> tree = createroot();
//生成节点
addnode(tree);
threadtree<string> prevnode = null;
//构建线索二叉树
manager.bintreethreadingcreate_ldr(ref tree, ref prevnode);
console.writeline("\n线索二叉树的遍历结果为：\n");
//中序遍历线索二叉树
manager.bintreethread_ldr(tree);
}
#region 生成根节点
/// <summary>
/// 生成根节点
/// </summary>
/// <returns></returns>
static threadtree<string> createroot()
{
threadtree<string> tree = new threadtree<string>();
console.writeline("请输入根节点，方便我们生成树\n");
tree.data = console.readline();
console.writeline("根节点生成已经生成\n");
return tree;
}
#endregion
#region 插入节点操作
/// <summary>
/// 插入节点操作
/// </summary>
/// <param name="tree"></param>
static threadtree<string> addnode(threadtree<string> tree)
{
threadtreemanager mananger = new threadtreemanager();
while (true)
{
threadtree<string> node = new threadtree<string>();
console.writeline("请输入要插入节点的数据：\n");
node.data = console.readline();
console.writeline("请输入要查找的父节点数据：\n");
var parentdata = console.readline();
if (tree == null)
{
console.writeline("未找到您输入的父节点，请重新输入。");
continue;
}
console.writeline("请确定要插入到父节点的：1 左侧，2 右侧");
direction direction = (direction)enum.parse(typeof(direction), console.readline());
tree = mananger.bintreethreadaddnode(tree, node, parentdata, direction);
console.writeline("插入成功，是否继续？ 1 继续， 2 退出");
if (int.parse(console.readline()) == 1)
continue;
else
break;
}
return tree;
}
#endregion
}
#region 节点标识(用于判断孩子是节点还是线索)
/// <summary>
/// 节点标识(用于判断孩子是节点还是线索)
/// </summary>
public enum nodeflag
{
subtree = 1,
thread = 2
}
#endregion
#region 线索二叉树的结构
/// <summary>
/// 线索二叉树的结构
/// </summary>
/// <typeparam name="t"></typeparam>
public class threadtree<t>
{
public t data;
public threadtree<t> left;
public threadtree<t> right;
public nodeflag leftflag;
public nodeflag rightflag;
}
#endregion
#region 插入左节点或者右节点
/// <summary>
/// 插入左节点或者右节点
/// </summary>
public enum direction { left = 1, right = 2 }
#endregion
#region 线索二叉树的基本操作
/// <summary>
/// 线索二叉树的基本操作
/// </summary>
public class threadtreemanager
{
#region 将指定节点插入到二叉树中
/// <summary>
/// 将指定节点插入到二叉树中
/// </summary>
/// <typeparam name="t"></typeparam>
/// <param name="tree"></param>
/// <param name="node"></param>
/// <param name="direction">插入做左是右</param>
/// <returns></returns>
public threadtree<t> bintreethreadaddnode<t>(threadtree<t> tree, threadtree<t> node, t data, direction direction)
{
if (tree == null)
return null;
if (tree.data.equals(data))
{
switch (direction)
{
case direction.left:
if (tree.left != null)
throw new exception("树的左节点不为空，不能插入");
else
tree.left = node;
break;
case direction.right:
if (tree.right != null)
throw new exception("树的右节点不为空，不能插入");
else
tree.right = node;
break;
}
}
bintreethreadaddnode(tree.left, node, data, direction);
bintreethreadaddnode(tree.right, node, data, direction);
return tree;
}
#endregion
#region 中序遍历构建线索二叉树
/// <summary>
/// 中序遍历构建线索二叉树
/// </summary>
/// <typeparam name="t"></typeparam>
/// <param name="tree"></param>
public void bintreethreadingcreate_ldr<t>(ref threadtree<t> tree, ref threadtree<t> prevnode)
{
if (tree == null)
return;
//先左子树遍历，寻找起始点
bintreethreadingcreate_ldr(ref tree.left, ref prevnode);
//如果left为空，则说明该节点可以放“线索”
tree.leftflag = (tree.left == null) ? nodeflag.thread : nodeflag.subtree;
//如果right为空，则说明该节点可以放“线索”
tree.rightflag = (tree.right == null) ? nodeflag.thread : nodeflag.subtree;
if (prevnode != null)
{
if (tree.leftflag == nodeflag.thread)
tree.left = prevnode;
if (prevnode.rightflag == nodeflag.thread)
prevnode.right = tree;
}
//保存前驱节点
prevnode = tree;
bintreethreadingcreate_ldr(ref tree.right, ref prevnode);
}
#endregion
#region 查找指定节点的后继
/// <summary>
/// 查找指定节点的后继
/// </summary>
/// <typeparam name="t"></typeparam>
/// <param name="tree"></param>
public threadtree<t> bintreethreadnext_ldr<t>(threadtree<t> tree)
{
if (tree == null)
return null;
//如果查找节点的标志域中是thread，则直接获取
if (tree.rightflag == nodeflag.thread)
return tree.right;
else
{
//根据中序遍历的规则是寻找右子树中中序遍历的第一个节点
var rightnode = tree.right;
//如果该节点是subtree就需要循环遍历
while (rightnode.leftflag == nodeflag.subtree)
{
rightnode = rightnode.left;
}
return rightnode;
}
}
#endregion
#region 查找指定节点的前驱
/// <summary>
/// 查找指定节点的前驱
/// </summary>
/// <typeparam name="t"></typeparam>
/// <param name="tree"></param>
/// <returns></returns>
public threadtree<t> bintreethreadprev_ldr<t>(threadtree<t> tree)
{
if (tree == null)
return null;
//如果标志域中存放的是线索，那么可以直接找出来
if (tree.leftflag == nodeflag.thread)
return tree.left;
else
{
//根据”中序“的规则可知，如果不为thread，则要找出左子树的最后节点
//也就是左子树中最后输出的元素
var leftnode = tree.left;
while (leftnode.rightflag == nodeflag.subtree)
leftnode = leftnode.right;
return leftnode;
}
}
#endregion
#region 遍历线索二叉树
/// <summary>
/// 遍历线索二叉树
/// </summary>
/// <typeparam name="t"></typeparam>
/// <param name="tree"></param>
public void bintreethread_ldr<t>(threadtree<t> tree)
{
if (tree == null)
return;
while (tree.leftflag == nodeflag.subtree)
tree = tree.left;
do
{
console.write(tree.data + "\t");
tree = bintreethreadnext_ldr(tree);
} while (tree != null);
}
#endregion
}
#endregion
}
将文章开头处的数据输入到存储结构中