C#|C#通过线索二叉树进行中序遍历输出 C#|数据结构

程序如下所示
建立线索二叉树，或者说对二叉树线索化，实质上就是遍历一棵二叉树。在遍历过程中，访问结点的操作是检查当前的左，右指针域是否为空，将它们改为指向前驱结点或后续结点的线索。为实现这一过程，设指针pre始终指向刚刚访问的结点，即若指针p指向当前结点，则pre指向它的前驱，以便设线索。
另外，在对一颗二叉树加线索时，必须首先申请一个头结点，建立头结点与二叉树的根结点的指向关系，对二叉树线索化后，还需建立最后一个结点与头结点之间的线索。
下面是建立中序二叉树的递归算法，其中pre为全局变量。
///
/// 通过中序遍历对二叉树线索化
///
///
///
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;
}

} /// /// 寻找中序遍历线索二叉树的第一个节点 /// /// static ThreadNode FirstNode(ThreadNode T) { while (T.lchild!=null&&T.ltag==0) { T = T.lchild; } return T; } /// /// 寻找中序线索二叉树中节点p再中序序列下的后继节点 /// /// /// static ThreadNode Nextnode(ThreadNode p) { if (p.rtag==0) { return FirstNode(p.rchild); }else { return p.rchild; }} /// /// 通过中序线索二叉树实现中序遍历 /// /// static void Inorder(ThreadNode T) { for (ThreadNode p=FirstNode(T); p!=null; p=Nextnode(p)) { Console.WriteLine(p.data); }}}

public class ThreadNode{
public ThreadNode() { }
public int data; //数据元素
public ThreadNode lchild, rchild; //左右孩子结点
public int ltag, rtag; //左右线索标志
}
【C#|C#通过线索二叉树进行中序遍历输出】加粗样式