程序如下所示 建立线索二叉树，或者说对二叉树线索化，实质上就是遍历一棵二叉树。在遍历过程中，访问结点的操作是检查当前的左，右指针域是否为空，将它们改为指向前驱结点或后续结点的线索。为实现这一过程，设指针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;//左右线索标志 }
加粗样式
