从上节的讨论得知：遍历二杈树是以一定规则将二杈树中结点排列成一个线性序列，得到二杈树中结点的先序序列或中序序列或后序序列。这实际上是对一个非线性结构进行线性化操作，使每个结点（除第一个和最后一个外）在这些线性序列中有且仅有一个直接前驱和直接后继。但是，当以二杈链表作为存储结构时，只能找到结点的左，右孩子的信息，而不能直接得到结点在任一序列中的前驱和后继信息，这种信息只能在遍历的动态过程中才能得到。      因为在有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);//在二杈排序树中插入新结点svoid 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); //遍历右子树 }}

评论