为防止广告，目前nocow只有登录用户能够创建新页面。如要创建页面请先登录/注册（新用户需要等待1个小时才能正常使用该功能）。

线索二叉树

来自NOCOW
跳转到： 导航, 搜索

线索二叉树(保留遍历时结点在任一序列的前驱和后继的信息)：若结点有左子树，则其lchild域指示其左孩子，否则令lchild域指示其前驱；若结点有右子树，则其rchild域指示其右孩子，否则令rchild指示其后继。还需在结点结构中增加两个标志域LTag和RTag。LTag=0时，lchild域指示结点的左孩子，LTag=1时，lchild域指示结点的前驱；RTag=0时，rchild域指示结点的右孩子，RTag=1时，rchild域指示结点的后继。以这种结点结构构成的二叉链表作为二叉树的存储结构，叫做线索链表，其中指向结点前驱和后继的指针叫做线索，加上线索的二叉树称为线索二叉树。对二叉树以某种次序遍历使其变为线索二叉树的过程叫做线索化。若对二叉树进行中序遍历，则所得的线索二叉树称为中序线索二叉树，线索链表称为为中序线索链表。线索二叉树是一种物理结构。


在中序线索树找结点后继的规律是：若其右标志为1，则右链为线索，指示其后继，否则遍历其右子树时访问的第一个结点（右子树最左下的结点）为其后继；找结点前驱的规律是：若其左标志为1，则左链为线索，指示其前驱，否则遍历左子树时最后访问的一个结点（左子树中最右下的结点）为其前驱。在后序线索树中找到结点的后继分三种情况：

  1. 若结点是二叉树的根，则其后继为空；
  2. 若结点是其双亲的右孩子，或是其双亲的左孩子且其双亲没有右子树，则其后继即为双亲结点；
  3. 若结点是其双亲的左孩子，且其双亲有右子树，则其后继为双亲右子树上按后序遍历列出的第一个结点。

[编辑] 二叉线索存储表示

[编辑] 存储结构

二叉树的二叉线索存储表示：在线索链表上添加一个头结点，并令其lchild域的指针指向二叉树的根结点，其rchild域的指针指向中序遍历时访问的最后一个结点。令二叉树中序序列中的第一个结点的lchild域指针和最后一个结点的rchild域的指针均指向头结点，这样就建立了一个双向线索链表 

/* 二叉树的二叉线索存储表示 */
typedef enum{Link,Thread}PointerTag; /* Link(0)：指针，Thread(1)：线索 */
typedef struct BiThrNode
{
  TElemType data;
  struct BiThrNode *lchild,*rchild; /* 左右孩子指针 */
  PointerTag LTag,RTag; /* 左右标志 */
}BiThrNode,*BiThrTree;

[编辑] 基本操作

/* 二叉树的二叉线索存储的基本操作 */
void CreateBiThrTree(BiThrTree *T)
{ /* 按先序输入线索二叉树中结点的值，构造线索二叉树T。0(整型)/空格(字符型)表示空结点 */
  TElemType ch;
  scanf(form,&ch);
  if(ch==Nil)
    *T=NULL;
  else
  {
    *T=(BiThrTree)malloc(sizeof(BiThrNode)); /* 生成根结点(先序) */
    if(!*T)
      exit(OVERFLOW);
    (*T)->data=ch; /* 给根结点赋植 */
    CreateBiThrTree(&(*T)->lchild); /* 递归构造左子树 */
    if((*T)->lchild) /* 有左孩子 */
      (*T)->LTag=Link; /* 给左标志赋值(指针) */
    CreateBiThrTree(&(*T)->rchild); /* 递归构造右子树 */
    if((*T)->rchild) /* 有右孩子 */
      (*T)->RTag=Link; /* 给右标志赋值(指针) */
  }
}

BiThrTree pre; /* 全局变量，始终指向刚刚访问过的结点 */
void InThreading(BiThrTree p)
{ /* 通过中序遍历进行中序线索化，线索化之后pre指向最后一个结点。算法6.7 */
  if(p) /* 线索二叉树不空 */
  {
    InThreading(p->lchild); /* 递归左子树线索化 */
    if(!p->lchild) /* 没有左孩子 */
    {
      p->LTag=Thread; /* 左标志为线索(前驱) */
      p->lchild=pre; /* 左孩子指针指向前驱 */
    }
    if(!pre->rchild) /* 前驱没有右孩子 */
    {
      pre->RTag=Thread; /* 前驱的右标志为线索(后继) */
      pre->rchild=p; /* 前驱右孩子指针指向其后继(当前结点p) */
    }
    pre=p; /* 保持pre指向p的前驱 */
    InThreading(p->rchild); /* 递归右子树线索化 */
  }
}

void InOrderThreading(BiThrTree *Thrt,BiThrTree T)
{ /* 中序遍历二叉树T，并将其中序线索化，Thrt指向头结点。算法6.6 */
  *Thrt=(BiThrTree)malloc(sizeof(BiThrNode));
  if(!*Thrt) /* 生成头结点不成功 */
    exit(OVERFLOW);
  (*Thrt)->LTag=Link; /* 建头结点，左标志为指针 */
  (*Thrt)->RTag=Thread; /* 右标志为线索 */
  (*Thrt)->rchild=*Thrt; /* 右指针回指 */
  if(!T) /* 若二叉树空，则左指针回指 */
    (*Thrt)->lchild=*Thrt;
  else
  {
    (*Thrt)->lchild=T; /* 头结点的左指针指向根结点 */
    pre=*Thrt; /* pre(前驱)的初值指向头结点 */
    InThreading(T); /* 中序遍历进行中序线索化，pre指向中序遍历的最后一个结点 */
    pre->rchild=*Thrt; /* 最后一个结点的右指针指向头结点 */
    pre->RTag=Thread; /* 最后一个结点的右标志为线索 */
    (*Thrt)->rchild=pre; /* 头结点的右指针指向中序遍历的最后一个结点 */
  }
}

void InOrderTraverse_Thr(BiThrTree T,void(*Visit)(TElemType))
{ /* 中序遍历线索二叉树T(头结点)的非递归算法。算法6.5 */
  BiThrTree p;
  p=T->lchild; /* p指向根结点 */
  while(p!=T)
  { /* 空树或遍历结束时，p==T */
    while(p->LTag==Link) /* 由根结点一直找到二叉树的最左结点 */
      p=p->lchild;
    Visit(p->data); /* 访问此结点 */
    while(p->RTag==Thread&&p->rchild!=T) /* p->rchild是线索(后继)，且不是遍历的最后一个结点 */
    {
      p=p->rchild;
      Visit(p->data); /* 访问后继结点 */
    }
    p=p->rchild; /* 若p->rchild不是线索(是右孩子)，p指向右孩子，返回循环，*/
  }              /* 找这棵子树中序遍历的第1个结点 */
}

void PreThreading(BiThrTree p)
{ /* PreOrderThreading()调用的递归函数 */
  if(!pre->rchild) /* p的前驱没有右孩子 */
  {
    pre->rchild=p; /* p前驱的后继指向p */
    pre->RTag=Thread; /* pre的右孩子为线索 */
  }
  if(!p->lchild) /* p没有左孩子 */
  {
    p->LTag=Thread; /* p的左孩子为线索 */
    p->lchild=pre; /* p的左孩子指向前驱 */
  }
  pre=p; /* 移动前驱 */
  if(p->LTag==Link) /* p有左孩子 */
    PreThreading(p->lchild); /* 对p的左孩子递归调用preThreading() */
  if(p->RTag==Link) /* p有右孩子 */
    PreThreading(p->rchild); /* 对p的右孩子递归调用preThreading() */
}

void PreOrderThreading(BiThrTree *Thrt,BiThrTree T)
{ /* 先序线索化二叉树T，头结点的右指针指向先序遍历的最后1个结点 */
  *Thrt=(BiThrTree)malloc(sizeof(BiThrNode));
  if(!*Thrt) /* 生成头结点 */
    exit(OVERFLOW);
  (*Thrt)->LTag=Link; /* 头结点的左指针为孩子 */
  (*Thrt)->RTag=Thread; /* 头结点的右指针为线索 */
  (*Thrt)->rchild=*Thrt; /* 头结点的右指针指向自身 */
  if(!T) /* 空树 */
    (*Thrt)->lchild=*Thrt; /* 头结点的左指针也指向自身 */
  else
  { /* 非空树 */
    (*Thrt)->lchild=T; /* 头结点的左指针指向根结点 */
    pre=*Thrt; /* 前驱为头结点 */
    PreThreading(T); /* 从头结点开始先序递归线索化 */
    pre->rchild=*Thrt; /* 最后一个结点的后继指向头结点 */
    pre->RTag=Thread;
    (*Thrt)->rchild=pre; /* 头结点的后继指向最后一个结点 */
  }
}

void PreOrderTraverse_Thr(BiThrTree T,void(*Visit)(TElemType))
{ /* 先序遍历线索二叉树T(头结点)的非递归算法 */
  BiThrTree p=T->lchild; /* p指向根结点 */
  while(p!=T) /* p没指向头结点(遍历的最后1个结点的后继指向头结点) */
  {
    Visit(p->data); /* 访问根结点 */
    if(p->LTag==Link) /* p有左孩子 */
      p=p->lchild; /* p指向左孩子(后继) */
    else /* p无左孩子 */
      p=p->rchild; /* p指向右孩子或后继 */
  }
}

void PostThreading(BiThrTree p)
{ /* PostOrderThreading()调用的递归函数 */
  if(p) /* p不空 */
  {
    PostThreading(p->lchild); /* 对p的左孩子递归调用PostThreading() */
    PostThreading(p->rchild); /* 对p的右孩子递归调用PostThreading() */
    if(!p->lchild) /* p没有左孩子 */
    {
      p->LTag=Thread; /* p的左孩子为线索 */
      p->lchild=pre; /* p的左孩子指向前驱 */
    }
    if(!pre->rchild) /* p的前驱没有右孩子 */
    {
      pre->RTag=Thread; /* p前驱的右孩子为线索 */
      pre->rchild=p; /* p前驱的后继指向p */
    }
    pre=p; /* 移动前驱 */
  }
}

void PostOrderThreading(BiThrTree *Thrt,BiThrTree T)
{ /* 后序递归线索化二叉树 */
  *Thrt=(BiThrTree)malloc(sizeof(BiThrNode));
  if(!*Thrt) /* 生成头结点 */
    exit(OVERFLOW);
  (*Thrt)->LTag=Link; /* 头结点的左指针为孩子 */
  (*Thrt)->RTag=Thread; /* 头结点的右指针为线索 */
  if(!T) /* 空树 */
    (*Thrt)->lchild=(*Thrt)->rchild=*Thrt; /* 头结点的左右指针指向自身 */
  else
  { /* 非空树 */
    (*Thrt)->lchild=(*Thrt)->rchild=T; /* 头结点的左右指针指向根结点(最后一个结点) */
    pre=*Thrt; /* 前驱为头结点 */
    PostThreading(T); /* 从头结点开始后序递归线索化 */
    if(pre->RTag!=Link) /* 最后一个结点没有右孩子 */
    {
      pre->rchild=*Thrt; /* 最后一个结点的后继指向头结点 */
      pre->RTag=Thread;
    }
  }
}

void DestroyBiTree(BiThrTree *T)
{ /* DestroyBiThrTree调用的递归函数，T指向根结点 */
  if(*T) /* 非空树 */
  {
    if((*T)->LTag==0) /* 有左孩子 */
      DestroyBiTree(&(*T)->lchild); /* 销毁左孩子子树 */
    if((*T)->RTag==0) /* 有右孩子 */
      DestroyBiTree(&(*T)->rchild); /* 销毁右孩子子树 */
    free(*T); /* 释放根结点 */
    T=NULL; /* 空指针赋0 */
  }
}

void DestroyBiThrTree(BiThrTree *Thrt)
{ /* 初始条件：线索二叉树Thrt存在。操作结果：销毁线索二叉树Thrt */
  if(*Thrt) /* 头结点存在 */
  {
    if((*Thrt)->lchild) /* 根结点存在 */
      DestroyBiTree(&(*Thrt)->lchild); /* 递归销毁头结点lchild所指二叉树 */
    free(*Thrt); /* 释放头结点 */
    *Thrt=NULL; /* 线索二叉树Thrt指针赋0 */
  }
}
来自“http://www.nocow.cn/index.php?title=%E7%BA%BF%E7%B4%A2%E4%BA%8C%E5%8F%89%E6%A0%91&oldid=105”
个人工具