C＃通過中序遍曆對二叉樹進行線索化

本文講解
C#通過中序遍曆對二叉樹進行線索化
在二叉樹的結點上加上線索的二叉樹稱為線索二叉樹，對二叉樹以某種遍曆方式（如先序、中序、後序或層次等）進行遍曆，使其變為線索二叉樹的過程稱為對二叉樹進行線索化。 [1]
對於n個結點的二叉樹，在二叉鏈存儲結構中有n+1個空鏈域，利用這些空鏈域存放在某種遍曆次序下該結點的前驅結點和後繼結點的指針，這些指針稱為線索，加上線索的二叉樹稱為線索二叉樹。

這種加上了線索的二叉鏈錶稱為線索鏈錶，相應的二叉樹稱為線索二叉樹(Threaded BinaryTree)。根據線索性質的不同，線索二叉樹可分為前序線索二叉樹、中序線索二叉樹和後序線索二叉樹三種。
注意：線索鏈錶解决了無法直接找到該結點在某種遍曆序列中的前驅和後繼結點的問題，解决了二叉鏈錶找左、右孩子困難的問題。

///
/// 通過中序遍曆對二叉樹線索化
///
///
///
static void InThread(ref ThreadNode p, ref ThreadNode pre)
{
if (p != null)
{
InThread(ref p.lchild,ref pre);
if (p.lchild == null) { p.lchild = pre; p.ltag = 1; }
if (pre!=null&&pre.rchild==null) { pre.rchild = p;pre.rtag = 1; }
pre = p;
InThread(ref p.rchild, ref pre);
}
}
///
/// 創建線索二叉樹主邏輯
///
///
static void CreateInThread(ref ThreadNode T) {
ThreadNode pre = null;
if (T!=null) {
InThread(ref T,ref pre);
pre.rchild = null;
pre.rtag = 1;
}