从上节的讨论得知:遍历二杈树是以一定规则将二杈树中结点排列成一个线性序列,得到二杈树中结点的先序序列或中序序列或后序序列。这实际上是对一个非线性结构进行线性化操作,使每个结点(除第一个和最后一个外)在这些线性序列中有且仅有一个直接前驱和直接后继。但是,当以二杈链表作为存储结构时,只能找到结点的左,右孩子的信息,而不能直接得到结点在任一序列中的前驱和后继信息,这种信息只能在遍历的动态过程中才能得到。
      因为在有n个结点的二杈链表中必定存在n+1个空链域,故可以利用这些空链域来存放结点的前驱和后继信息。
      试做如下规定:若结点有左子树,则其lchild域指示其左孩子,否则令lchild域指示其前驱;若结点有右子树,则其rchild域指示其右孩子,否则令rchild域指示其后继。为了避免混淆,需要改变结点结构,增加两个标志域:LTag,RTag。
      其中:LTag = 0,lchild域指示其左孩子;  LTag = 1,lchild域指示其前驱。
            RTag = 0,rchild域指示其右孩子;  RTag = 1,rchild域指示其后继。
      以这种结点结构构成的二杈链表作为二杈树的存储结构,叫做线索链表,其中指向结点前驱和后继的指针,叫做线索。加上线索的二杈树叫做线索二杈树。对二杈树以某种次序遍历使其变成线索二杈树的过程叫做线索化。
      在线索树上进行遍历,只要先找到序列中的第一个结点,然后依次找结点后继直到其后继为空为止。
      求遍历后的线性序列的前驱和后继。前序线索化能依次找到后继,但是前驱需要求双亲;中序线索化前驱和后继都不需要求双亲,但是都不很直接;后序线索化能依次找到前驱,但是后继需要求双亲。可以看出,线索化成中序是最佳的选择,基本上算是达到了要求。
      //二杈树的二杈线索存储表示
typedef enum PointerTag {Link, Thread}; //Link:指针,Thread:线索
typedef struct BiThrNode{
      ElemType data;
      struct BiThrNode *lchild, *rchild;//左,右孩子指针
      PointerTag LTag, RTag; //左,右标志
} *BiThrTree;
      为了方便起见,我们仿照线性表的存储结构,在二杈树的线索链表上也添加一个头结点,并令其lchild域的指针指向二杈树的根结点,其rchild域的指针指向中序遍历时访问的最后一个结点;反之,令二杈树中序序列的第一个结点的lchild域的指针和最后一个结点的rchild域的指针均指向头结点。这好比为二杈树建立了一个双向线索链表,既可以从第一个结点起顺后继进行遍历,也可以从最后一个结点起顺前驱进行遍历。
 void InOrderTraverse_Thr(BiThrTree T)//中序遍历线索二杈树的非递归算法, T 指向头结点
{
      BiThrTree p = T->lchild; //p指向根结点

      while (p != T) //空树或遍历结束时,p == T
      {
            while (p->LTag == Link)//寻找第一个结点
            {
                  p = p->lchild;
            }
            cout << p->data << ' ';//输出该结点

            while (p->RTag == Thread && p->rchild != T)//访问后继结点
            {
                  p = p->rchild;
                  cout << p->data << ' ';//输出该结点
            }

            p = p->rchild;
      }
}

void InThreading(BiThrTree & p, BiThrTree & pre) //中序线索化
{
      if (p)
      {
            InThreading(p->lchild, pre); //左子树线索化
            if (! p->lchild)//若当前结点的左子树为空,则建立前驱线索
            {
                  p->LTag = Thread;
                  p->lchild = pre;
            }
            else
                  p->LTag = Link;
            if (pre && !pre->rchild)//若前驱结点非空,且其右孩子为空,则建立后继线索
            {
                  pre->RTag = Thread;
                  pre->rchild = p;
            }
            pre = p;    //中序向前遍历接点 ,保持pre指向p的前驱
            pre->RTag = Link;//默认前驱结点右孩子非空
            InThreading(p->rchild, pre); //右子树线索化
      }
}

BiThrTree InOrderThreading(BiThrTree T)//中序遍历二杈树,并将其中序线索化
{
      BiThrTree Thrt = new BiThrNode;  //建立头结点
      if (!Thrt)
 {
  printf("Out of space!");
  return NULL;
 }
 Thrt->LTag = Link;
 Thrt->RTag = Thread;
 Thrt->rchild = Thrt; //右指针回指

 if (!T)//若二杈树为空,则左指针回指
            Thrt->lchild = Thrt;
      else
      {
            Thrt->lchild = T;
            BiThrTree pre = Thrt;
            InThreading(T, pre);//中序线索化

            pre->rchild = Thrt; //最后一个结点线索化
            pre->RTag = Thread;
            Thrt->rchild = pre; //此时pre指向最后一个结点
      }
      return Thrt;
}

////////////////////////////////////////////////////////////////////////////////////////
//应用示例:我先生成一棵二杈排序树(输入单个字符,以#结束),并以递归方式遍历输出结点;
//然后把该二杈排序树中序线索化,最后中序遍历线索二杈树输出结点。
#include <iostream>

using namespace std;

//二杈树的二杈线索存储表示
typedef char ElemType;
typedef enum PointerTag {Link, Thread}; //Link:指针,Thread:线索
typedef struct BiThrNode{
      ElemType data;
      struct BiThrNode *lchild, *rchild;//左,右孩子指针
      PointerTag LTag, RTag; //左,右标志
} *BiThrTree;

void InOrderTraverse_Thr(BiThrTree T);//中序遍历线索二杈树的非递归算法, T 指向头结点
void InThreading(BiThrTree & p, BiThrTree & pre); //中序线索化
BiThrTree InOrderThreading(BiThrTree T);//中序遍历二杈树,并将其中序线索化
void CreateBTree(BiThrTree & bt);//生成一棵二杈排序树(输入单个字符,以#结束)
BiThrTree NewBTree(ElemType x);//构造一个数据域为x的新结点
void Insert(BiThrTree & b, BiThrTree s);//在二杈排序树中插入新结点s
void InOrderPrint_1(BiThrTree p); //中序遍历输出结点(递归)

int main()
{
      BiThrTree bt = NULL;

      CreateBTree(bt);//生成一棵二杈排序树(输入单个字符,以#结束)
      InOrderPrint_1(bt); //中序遍历输出结点(递归)
      cout << endl;

      BiThrTree BT = InOrderThreading(bt);//中序遍历二杈树,并将其中序线索化
      InOrderTraverse_Thr(BT);//中序遍历线索二杈树的非递归算法, T 指向头结点

      system("PAUSE");
      return EXIT_SUCCESS;
}

void InOrderTraverse_Thr(BiThrTree T)//中序遍历线索二杈树的非递归算法, T 指向头结点
{
      BiThrTree p = T->lchild; //p指向根结点

      while (p != T) //空树或遍历结束时,p == T
      {
            while (p->LTag == Link)//寻找第一个结点
            {
                  p = p->lchild;
            }
            cout << p->data << ' ';//输出该结点

            while (p->RTag == Thread && p->rchild != T)//访问后继结点
            {
                  p = p->rchild;
                  cout << p->data << ' ';//输出该结点
            }

            p = p->rchild;
      }
}

void InThreading(BiThrTree & p, BiThrTree & pre) //中序线索化
{
      if (p)
      {
            InThreading(p->lchild, pre); //左子树线索化
            if (! p->lchild)//若当前结点的左子树为空,则建立前驱线索
            {
                  p->LTag = Thread;
                  p->lchild = pre;
            }
            else
                  p->LTag = Link;
            if (pre && !pre->rchild)//若前驱结点非空,且其右孩子为空,则建立后继线索
            {
                  pre->RTag = Thread;
                  pre->rchild = p;
            }
            pre = p;    //中序向前遍历接点 ,保持pre指向p的前驱
            pre->RTag = Link;//默认前驱结点右孩子非空
            InThreading(p->rchild, pre); //右子树线索化
      }
}

BiThrTree InOrderThreading(BiThrTree T)//中序遍历二杈树,并将其中序线索化
{
      BiThrTree Thrt = new BiThrNode;  //建立头结点
      if (!Thrt)
 {
  printf("Out of space!");
  return NULL;
 }
 Thrt->LTag = Link;
 Thrt->RTag = Thread;
 Thrt->rchild = Thrt; //右指针回指

 if (!T)//若二杈树为空,则左指针回指
            Thrt->lchild = Thrt;
      else
      {
            Thrt->lchild = T;
            BiThrTree pre = Thrt;
            InThreading(T, pre);//中序线索化

            pre->rchild = Thrt; //最后一个结点线索化
            pre->RTag = Thread;
            Thrt->rchild = pre; //此时pre指向最后一个结点
      }
      return Thrt;
}

void CreateBTree(BiThrTree & bt)//生成一棵二杈排序树(输入单个字符,以#结束)
{
      ElemType x;
      cin >> x;
      while (x != '#')
      {
            BiThrTree s = NewBTree(x);//构造一个数据域为x的新结点
            Insert(bt, s);//在二杈排序树中插入新结点s
            cin >> x;
      }
}

BiThrTree NewBTree(ElemType x)//构造一个数据域为x的新结点
{
 BiThrTree s = new BiThrNode;
      if (!s)
 {
  printf("Out of space!");
  exit (1);
 }
 s->data = x;
 s->lchild = s->rchild = NULL;
 s->LTag = s->RTag = Link;

      return s;
}


void Insert(BiThrTree & b, BiThrTree s)//在二杈排序树中插入新结点s
{
 if (b == NULL)
  b = s;
 else if (b->data == s->data)//不做任何插入操作
  return;
 else if(b->data > s->data)//把s所指结点插入到左子树中
      Insert(b->lchild, s);
 else               //把s所指结点插入到右子树中
      Insert(b->rchild, s);
}

void InOrderPrint_1(BiThrTree p) //中序遍历输出结点(递归)
{
 if (p != NULL)
 {
  InOrderPrint_1(p->lchild); //遍历左子树
            cout << p->data << ' ';//输出该结点
  InOrderPrint_1(p->rchild); //遍历右子树
 }
}

Posted on 2006-05-18 16:13 梦想飞扬 阅读(1475) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理