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;
}

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

        }

    }



}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

public class ThreadNode{
public ThreadNode() { }
public int data;//数据元素
public ThreadNode lchild, rchild;//左右孩子结点
public int ltag, rtag;//左右线索标志
}

加粗样式