先前說(shuō)了樹(shù)的基本操作，我們采用的是二叉鏈表來(lái)保存樹(shù)形結(jié)構(gòu)，當(dāng)然二叉有二叉的困擾之處，比如我想找到當(dāng)前結(jié)點(diǎn)的“前驅(qū)”和“后繼”，那么我們就必須要遍歷一下樹(shù)，然后才能定位到該“節(jié)點(diǎn)”的“前驅(qū)”和“后繼”，每次定位都是O（n），這不是我們想看到的，那么有什么辦法來(lái)解決呢？
（1） 在節(jié)點(diǎn)域中增加二個(gè)指針域，分別保存“前驅(qū)”和“后繼”，那么就是四叉鏈表了，哈哈，還是有點(diǎn)浪費(fèi)空間啊。
（2） 看下面的這個(gè)二叉樹(shù)，我們知道每個(gè)結(jié)點(diǎn)有2個(gè)指針域，4個(gè)節(jié)點(diǎn)就有8個(gè)指針域，其實(shí)真正保存節(jié)點(diǎn)的指針
僅有3個(gè)，還有5個(gè)是空閑的，那么為什么我們不用那些空閑的指針域呢，達(dá)到資源的合理充分的利用。
一： 線索二叉樹(shù)
1 概念
剛才所說(shuō)的在空閑的指針域里面存放“前驅(qū)”和“后繼”就是所謂的線索。
1> 左線索： 在空閑的左指針域中存放該“結(jié)點(diǎn)”的“前驅(qū)”被認(rèn)為是左線索。
2> 右線索： 在空閑的右指針域中存放該“結(jié)點(diǎn)“的”后繼“被認(rèn)為是右線索。
當(dāng)“二叉鏈表”被套上這種線索，就被認(rèn)為是線索鏈表，當(dāng)“二叉樹(shù)”被套上這種線索就被認(rèn)為是線索二叉樹(shù)，當(dāng)然線索根據(jù)
二叉樹(shù)的遍歷形式不同被分為“先序線索”，“中序線索”，“后序線索”。
2 結(jié)構(gòu)圖
說(shuō)了這么多，我們還是上圖說(shuō)話(huà)，就拿下面的二叉樹(shù)，我們構(gòu)建一個(gè)中序線索二叉樹(shù)，需要多動(dòng)動(dòng)腦子喲。
1> 首先要找到“中序遍歷”中的首結(jié)點(diǎn)D，因?yàn)椤癉結(jié)點(diǎn)”是首節(jié)點(diǎn)，所以不存在“前驅(qū)”，左指針自然是空，
”D節(jié)點(diǎn)”的右指針存放的是“后繼”，那么根據(jù)“中序遍歷”的規(guī)則應(yīng)該是B，所以D的右指針存放著B(niǎo)節(jié)點(diǎn)。
2> 接著就是“B節(jié)點(diǎn)”，他的左指針不為空，所以就不管了，但是他的“右指針”空閑，根據(jù)規(guī)則“B結(jié)點(diǎn)“的右
指針存放的是"A結(jié)點(diǎn)“。
3> 然后就是“A節(jié)點(diǎn)”，他已經(jīng)被塞的滿(mǎn)滿(mǎn)的，所以就沒(méi)有“線索”可言了。
4> 最后就是“C節(jié)點(diǎn)”，根據(jù)規(guī)則，他的“左指針”存放著就是“A節(jié)點(diǎn)“，”C節(jié)點(diǎn)“是最后一個(gè)節(jié)點(diǎn)，右指針自然就是空的，你懂的。
3 基本操作
常用的操作一般有“創(chuàng)建線索二叉樹(shù)”，”查找后繼節(jié)點(diǎn)“，”查找前驅(qū)節(jié)點(diǎn)“，”遍歷線索二叉樹(shù)“，下面的操作我們就以”中序遍歷“來(lái)創(chuàng)建中序線索二叉樹(shù)。
1> 線索二叉樹(shù)結(jié)構(gòu)
從“結(jié)構(gòu)圖”中可以看到，現(xiàn)在結(jié)點(diǎn)的指針域中要么是”子節(jié)點(diǎn)（SubTree）“或者是”線索（Thread）“，此時(shí)就要設(shè)立標(biāo)志位來(lái)表示指針域存放的是哪一種。
復(fù)制代碼 代碼如下:
#region 節(jié)點(diǎn)標(biāo)識(shí)(用于判斷孩子是節(jié)點(diǎn)還是線索)
/// summary>
/// 節(jié)點(diǎn)標(biāo)識(shí)(用于判斷孩子是節(jié)點(diǎn)還是線索)
/// /summary>
public enum NodeFlag
{
SubTree = 1,
Thread = 2
}
#endregion
#region 線索二叉樹(shù)的結(jié)構(gòu)
/// summary>
/// 線索二叉樹(shù)的結(jié)構(gòu)
/// /summary>
/// typeparam name="T">/typeparam>
public class ThreadTreeT>
{
public T data;
public ThreadTreeT> left;
public ThreadTreeT> right;
public NodeFlag leftFlag;
public NodeFlag rightFlag;
}
#endregion
2> 創(chuàng)建線索二叉樹(shù)
剛才也說(shuō)了如何構(gòu)建中序線索二叉樹(shù)，在代碼實(shí)現(xiàn)中，我們需要定義一個(gè)節(jié)點(diǎn)來(lái)保存當(dāng)前節(jié)點(diǎn)的前驅(qū)，我練習(xí)的時(shí)候迫不得已，只能使用兩個(gè)
ref來(lái)實(shí)現(xiàn)地址操作，達(dá)到一個(gè)Tree能夠讓兩個(gè)變量來(lái)操作。
復(fù)制代碼 代碼如下:
#region 中序遍歷構(gòu)建線索二叉樹(shù)
/// summary>
/// 中序遍歷構(gòu)建線索二叉樹(shù)
/// /summary>
/// typeparam name="T">/typeparam>
/// param name="tree">/param>
public void BinTreeThreadingCreate_LDRT>(ref ThreadTreeT> tree, ref ThreadTreeT> prevNode)
{
if (tree == null)
return;
//先左子樹(shù)遍歷，尋找起始點(diǎn)
BinTreeThreadingCreate_LDR(ref tree.left, ref prevNode);
//如果left為空，則說(shuō)明該節(jié)點(diǎn)可以放“線索”
tree.leftFlag = (tree.left == null) ? NodeFlag.Thread : NodeFlag.SubTree;
//如果right為空，則說(shuō)明該節(jié)點(diǎn)可以放“線索”
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;
}
//保存前驅(qū)節(jié)點(diǎn)
prevNode = tree;
BinTreeThreadingCreate_LDR(ref tree.right, ref prevNode);
}
#endregion
3> 查找后繼結(jié)點(diǎn)
現(xiàn)在大家都知道，后繼結(jié)點(diǎn)都是保存在“結(jié)點(diǎn)“的右指針域中，那么就存在”兩種情況“。
《1》 拿“B節(jié)點(diǎn)“來(lái)說(shuō)，他沒(méi)有右孩子，則肯定存放著線索（Thread),所以我們直接O（1）的返回他的線索即可。
《2》 拿“A節(jié)點(diǎn)”來(lái)說(shuō)，他有右孩子，即右指針域存放的是SubTree，悲哀啊，如何才能得到“A節(jié)點(diǎn)“的后繼呢？其實(shí)也很簡(jiǎn)單，
根據(jù)”中序“的定義，”A節(jié)點(diǎn)“的后繼必定是”A節(jié)點(diǎn)“的右子樹(shù)往左鏈找的第一個(gè)沒(méi)有左孩子的節(jié)點(diǎn)（只可意會(huì)，不可言傳，嘻嘻）。
復(fù)制代碼 代碼如下:
#region 查找指定節(jié)點(diǎn)的后繼
/// summary>
/// 查找指定節(jié)點(diǎn)的后繼
/// /summary>
/// typeparam name="T">/typeparam>
/// param name="tree">/param>
public ThreadTreeT> BinTreeThreadNext_LDRT>(ThreadTreeT> tree)
{
if (tree == null)
return null;
//如果查找節(jié)點(diǎn)的標(biāo)志域中是Thread，則直接獲取
if (tree.rightFlag == NodeFlag.Thread)
return tree.right;
else
{
//根據(jù)中序遍歷的規(guī)則是尋找右子樹(shù)中中序遍歷的第一個(gè)節(jié)點(diǎn)
var rightNode = tree.right;
//如果該節(jié)點(diǎn)是subTree就需要循環(huán)遍歷
while (rightNode.leftFlag == NodeFlag.SubTree)
{
rightNode = rightNode.left;
}
return rightNode;
}
}
#endregion
4> 查找前驅(qū)節(jié)點(diǎn)
這個(gè)跟（3)的操作很類(lèi)似，同樣也具有兩個(gè)情況。
《1》 拿“C結(jié)點(diǎn)”來(lái)說(shuō)，他沒(méi)有“左子樹(shù)”，則說(shuō)明“C節(jié)點(diǎn)”的左指針為T(mén)hread，此時(shí)，我們只要返回左指針域即可得到前驅(qū)結(jié)點(diǎn)。
《2》 拿"A節(jié)點(diǎn)“來(lái)說(shuō)，他有”左子樹(shù)“，則說(shuō)明”A節(jié)點(diǎn)“的左指針為SubTree，那么怎么找的到”A節(jié)點(diǎn)“的前驅(qū)呢？同樣啊，根據(jù)
”中序遍歷“的性質(zhì)，我們可以得知在”A節(jié)點(diǎn)“的左子樹(shù)中往”右鏈“中找到第一個(gè)沒(méi)有”右孩子“的節(jié)點(diǎn)。
復(fù)制代碼 代碼如下:
#region 查找指定節(jié)點(diǎn)的前驅(qū)
/// summary>
/// 查找指定節(jié)點(diǎn)的前驅(qū)
/// /summary>
/// typeparam name="T">/typeparam>
/// param name="tree">/param>
/// returns>/returns>
public ThreadTreeT> BinTreeThreadPrev_LDRT>(ThreadTreeT> tree)
{
if (tree == null)
return null;
//如果標(biāo)志域中存放的是線索，那么可以直接找出來(lái)
if (tree.leftFlag == NodeFlag.Thread)
return tree.left;
else
{
//根據(jù)”中序“的規(guī)則可知，如果不為T(mén)hread，則要找出左子樹(shù)的最后節(jié)點(diǎn)
//也就是左子樹(shù)中最后輸出的元素
var leftNode = tree.left;
while (leftNode.rightFlag == NodeFlag.SubTree)
leftNode = leftNode.right;
return leftNode;
}
}
#endregion
5> 遍歷線索二叉樹(shù)
因?yàn)槲覀儤?gòu)建線索的時(shí)候采用的是“中序”，那么我們遍歷同樣采用“中序”，大家是否看到了“線索”的好處，此時(shí)我們找某個(gè)節(jié)點(diǎn)的時(shí)間復(fù)雜度變?yōu)榱?/P>
O(1) ~0(n)的時(shí)間段，比不是線索的時(shí)候查找“前驅(qū)"和“后繼”效率要高很多。
復(fù)制代碼 代碼如下:
#region 遍歷線索二叉樹(shù)
/// summary>
/// 遍歷線索二叉樹(shù)
/// /summary>
/// typeparam name="T">/typeparam>
/// param name="tree">/param>
public void BinTreeThread_LDRT>(ThreadTreeT> 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
最后上一下總的運(yùn)行代碼
復(fù)制代碼 代碼如下:
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();
//生成根節(jié)點(diǎn)
ThreadTreestring> tree = CreateRoot();
//生成節(jié)點(diǎn)
AddNode(tree);
ThreadTreestring> prevNode = null;
//構(gòu)建線索二叉樹(shù)
manager.BinTreeThreadingCreate_LDR(ref tree, ref prevNode);
Console.WriteLine("\n線索二叉樹(shù)的遍歷結(jié)果為：\n");
//中序遍歷線索二叉樹(shù)
manager.BinTreeThread_LDR(tree);
}
#region 生成根節(jié)點(diǎn)
/// summary>
/// 生成根節(jié)點(diǎn)
/// /summary>
/// returns>/returns>
static ThreadTreestring> CreateRoot()
{
ThreadTreestring> tree = new ThreadTreestring>();
Console.WriteLine("請(qǐng)輸入根節(jié)點(diǎn)，方便我們生成樹(shù)\n");
tree.data = Console.ReadLine();
Console.WriteLine("根節(jié)點(diǎn)生成已經(jīng)生成\n");
return tree;
}
#endregion
#region 插入節(jié)點(diǎn)操作
/// summary>
/// 插入節(jié)點(diǎn)操作
/// /summary>
/// param name="tree">/param>
static ThreadTreestring> AddNode(ThreadTreestring> tree)
{
ThreadTreeManager mananger = new ThreadTreeManager();
while (true)
{
ThreadTreestring> node = new ThreadTreestring>();
Console.WriteLine("請(qǐng)輸入要插入節(jié)點(diǎn)的數(shù)據(jù)：\n");
node.data = Console.ReadLine();
Console.WriteLine("請(qǐng)輸入要查找的父節(jié)點(diǎn)數(shù)據(jù)：\n");
var parentData = Console.ReadLine();
if (tree == null)
{
Console.WriteLine("未找到您輸入的父節(jié)點(diǎn)，請(qǐng)重新輸入。");
continue;
}
Console.WriteLine("請(qǐng)確定要插入到父節(jié)點(diǎn)的：1 左側(cè)，2 右側(cè)");
Direction direction = (Direction)Enum.Parse(typeof(Direction), Console.ReadLine());
tree = mananger.BinTreeThreadAddNode(tree, node, parentData, direction);
Console.WriteLine("插入成功，是否繼續(xù)？ 1 繼續(xù)， 2 退出");
if (int.Parse(Console.ReadLine()) == 1)
continue;
else
break;
}
return tree;
}
#endregion
}
#region 節(jié)點(diǎn)標(biāo)識(shí)(用于判斷孩子是節(jié)點(diǎn)還是線索)
/// summary>
/// 節(jié)點(diǎn)標(biāo)識(shí)(用于判斷孩子是節(jié)點(diǎn)還是線索)
/// /summary>
public enum NodeFlag
{
SubTree = 1,
Thread = 2
}
#endregion
#region 線索二叉樹(shù)的結(jié)構(gòu)
/// summary>
/// 線索二叉樹(shù)的結(jié)構(gòu)
/// /summary>
/// typeparam name="T">/typeparam>
public class ThreadTreeT>
{
public T data;
public ThreadTreeT> left;
public ThreadTreeT> right;
public NodeFlag leftFlag;
public NodeFlag rightFlag;
}
#endregion
#region 插入左節(jié)點(diǎn)或者右節(jié)點(diǎn)
/// summary>
/// 插入左節(jié)點(diǎn)或者右節(jié)點(diǎn)
/// /summary>
public enum Direction { Left = 1, Right = 2 }
#endregion
#region 線索二叉樹(shù)的基本操作
/// summary>
/// 線索二叉樹(shù)的基本操作
/// /summary>
public class ThreadTreeManager
{
#region 將指定節(jié)點(diǎn)插入到二叉樹(shù)中
/// summary>
/// 將指定節(jié)點(diǎn)插入到二叉樹(shù)中
/// /summary>
/// typeparam name="T">/typeparam>
/// param name="tree">/param>
/// param name="node">/param>
/// param name="direction">插入做左是右/param>
/// returns>/returns>
public ThreadTreeT> BinTreeThreadAddNodeT>(ThreadTreeT> tree, ThreadTreeT> 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("樹(shù)的左節(jié)點(diǎn)不為空，不能插入");
else
tree.left = node;
break;
case Direction.Right:
if (tree.right != null)
throw new Exception("樹(shù)的右節(jié)點(diǎn)不為空，不能插入");
else
tree.right = node;
break;
}
}
BinTreeThreadAddNode(tree.left, node, data, direction);
BinTreeThreadAddNode(tree.right, node, data, direction);
return tree;
}
#endregion
#region 中序遍歷構(gòu)建線索二叉樹(shù)
/// summary>
/// 中序遍歷構(gòu)建線索二叉樹(shù)
/// /summary>
/// typeparam name="T">/typeparam>
/// param name="tree">/param>
public void BinTreeThreadingCreate_LDRT>(ref ThreadTreeT> tree, ref ThreadTreeT> prevNode)
{
if (tree == null)
return;
//先左子樹(shù)遍歷，尋找起始點(diǎn)
BinTreeThreadingCreate_LDR(ref tree.left, ref prevNode);
//如果left為空，則說(shuō)明該節(jié)點(diǎn)可以放“線索”
tree.leftFlag = (tree.left == null) ? NodeFlag.Thread : NodeFlag.SubTree;
//如果right為空，則說(shuō)明該節(jié)點(diǎn)可以放“線索”
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;
}
//保存前驅(qū)節(jié)點(diǎn)
prevNode = tree;
BinTreeThreadingCreate_LDR(ref tree.right, ref prevNode);
}
#endregion
#region 查找指定節(jié)點(diǎn)的后繼
/// summary>
/// 查找指定節(jié)點(diǎn)的后繼
/// /summary>
/// typeparam name="T">/typeparam>
/// param name="tree">/param>
public ThreadTreeT> BinTreeThreadNext_LDRT>(ThreadTreeT> tree)
{
if (tree == null)
return null;
//如果查找節(jié)點(diǎn)的標(biāo)志域中是Thread，則直接獲取
if (tree.rightFlag == NodeFlag.Thread)
return tree.right;
else
{
//根據(jù)中序遍歷的規(guī)則是尋找右子樹(shù)中中序遍歷的第一個(gè)節(jié)點(diǎn)
var rightNode = tree.right;
//如果該節(jié)點(diǎn)是subTree就需要循環(huán)遍歷
while (rightNode.leftFlag == NodeFlag.SubTree)
{
rightNode = rightNode.left;
}
return rightNode;
}
}
#endregion
#region 查找指定節(jié)點(diǎn)的前驅(qū)
/// summary>
/// 查找指定節(jié)點(diǎn)的前驅(qū)
/// /summary>
/// typeparam name="T">/typeparam>
/// param name="tree">/param>
/// returns>/returns>
public ThreadTreeT> BinTreeThreadPrev_LDRT>(ThreadTreeT> tree)
{
if (tree == null)
return null;
//如果標(biāo)志域中存放的是線索，那么可以直接找出來(lái)
if (tree.leftFlag == NodeFlag.Thread)
return tree.left;
else
{
//根據(jù)”中序“的規(guī)則可知，如果不為T(mén)hread，則要找出左子樹(shù)的最后節(jié)點(diǎn)
//也就是左子樹(shù)中最后輸出的元素
var leftNode = tree.left;
while (leftNode.rightFlag == NodeFlag.SubTree)
leftNode = leftNode.right;
return leftNode;
}
}
#endregion
#region 遍歷線索二叉樹(shù)
/// summary>
/// 遍歷線索二叉樹(shù)
/// /summary>
/// typeparam name="T">/typeparam>
/// param name="tree">/param>
public void BinTreeThread_LDRT>(ThreadTreeT> 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
}
將文章開(kāi)頭處的數(shù)據(jù)輸入到存儲(chǔ)結(jié)構(gòu)中
您可能感興趣的文章:- 算法系列15天速成 第十四天 圖【上】
- 算法系列15天速成——第十三天 樹(shù)操作【下】
- 算法系列15天速成 第十一天 樹(shù)操作（上）
- 算法系列15天速成 第十天 棧
- 算法系列15天速成 第八天 線性表【下】
- 算法系列15天速成 第九天 隊(duì)列
- 算法系列15天速成 第七天 線性表【上】
- 算法系列15天速成 第六天 五大經(jīng)典查找【下】
- 算法系列15天速成 第五天 五大經(jīng)典查找【中】
- 算法系列15天速成 第四天 五大經(jīng)典查找【上】
- 算法系列15天速成 第三天 七大經(jīng)典排序【下】
- 算法系列15天速成 第二天 七大經(jīng)典排序【中】
- 算法系列15天速成 第一天 七大經(jīng)典排序【上】
- 算法系列15天速成——第十五天 圖【下】（大結(jié)局）
