C语言数据结构之线索二叉树及其遍历

C语言数据结构之线索二叉树及其遍历

遍历二叉树就是以一定的规则将二叉树中的节点排列成一个线性序列，从而得到二叉树节点的各种遍历序列，其实质是：对一个非线性的结构进行线性化。使得在这个访问序列中每一个节点都有一个直接前驱和直接后继。传统的链式结构只能体现一种父子关系，￥不能直接得到节点在遍历中的前驱和后继￥，而我们知道二叉链表表示的二叉树中有大量的空指针，当使用这些空的指针存放指向节点的前驱和后继的指针时，则可以更加方便的运用二叉树的某些操作。引入线索二叉树的目的是： 为了加快查找节点的前驱和后继。对二叉树的线索化就是对二叉树进行一次遍历，在遍历的过程中检测节点的左右指针是否为空，如果是空，则将他们改为指向前驱和后继节点的线索。

如果二叉树没有被线索化，也可以使用<<非递归>>的代码进行遍历的，但是那就需要借助于<<栈>>,但是在线索化之后，对线索化的二叉树进行<<非递归>>的遍历就不再需要栈的辅助。

实现代码：

#include<stdio.h> 
#include<stdlib.h> 
 
#define OK 1 
#define ERROR 0 
 
typedef char ElemType; 
typedef int Status; 
 
/* 定义枚举类型，其值只能是Link和Thread 
 * Link表示的该指针指示的是孩子 
 * Thread表示的是还指针指示的是前驱或者是后缀 
 * */ 
typedef enum { 
  Link,Thread 
}PointerTag; 
 
typedef struct ThrBiTrNode{ 
  ElemType data; 
  struct ThrBiTrNode *lchild, *rchild; 
  PointerTag rTag, lTag; 
}ThrBiTrNode, *ThrBiTree; 
 
ThrBiTree Pre; 
 
Status InitThreadBinaryTree(ThrBiTree* T){ 
  *T = NULL; 
  return OK; 
} 
//先序建立二叉树,lchild和rchild都是指示做孩子和右孩子，所以lTag和rTag为Link 
Status ThreadBinaryTree_PreOrderInput(ThrBiTree* T){ 
  ElemType c; 
  scanf("%c", &c); 
  if( ' ' == c ){ 
    *T = NULL; 
  } 
  else{ 
    *T = (ThrBiTrNode*)malloc(sizeof(ThrBiTrNode)); 
    if( !*T ){ 
      return ERROR; 
    } 
    (*T)->data = c; 
    (*T)->lTag = Link; 
    (*T)->rTag = Link; 
    ThreadBinaryTree_PreOrderInput(&(*T)->lchild); 
    ThreadBinaryTree_PreOrderInput(&(*T)->rchild); 
  } 
  return OK; 
} 
//<<中序遍历>>对二叉树进行<<线索化>>，但是没有提供Pre的初始值，只是给出了 
//中间的过程，递归的思想和思考方式。 
//1 线索化左子树 
//2 对双亲节点处理//递归中的base 
//3 线索化右子树 
Status InOrderThread(ThrBiTree T){ 
  if( T != NULL ){ 
    InOrderThread(T->lchild);    //线索化左子树 
     
    //对双亲节点进行线索化处理 
    if( T->lchild == NULL ){ //如果左孩子为空，则将lchild作为索引 
            //Pre指向刚刚访问的节点 
      T->lTag = Thread; 
      T->lchild = Pre; 
    } 
    if( Pre->rchild == NULL ){  //直到现在才知道Pre的后缀是T，所以 
            //要对Pre进行设置,如果Pre的rchild为空 
            //则将Pre的rchild设置为后缀，指向T 
      Pre->rTag = Thread; 
      Pre->rchild = T; 
    } 
 
    Pre = T;      //标记当前的节点称为刚刚访问过的节点 
            //Pre最后会指向树的中序遍历的最后的 
            //一个节点 
 
    InOrderThread(T->rchild);  //线索化右子树 
  } 
  return OK; 
} 
//创建中序线索二叉树,为上个函数提供Pre 
Status CreateInOrderThreadBinaryTree(ThrBiTree T, ThrBiTree* headOfTree){ 
  *headOfTree = (ThrBiTrNode*)malloc(sizeof(struct ThrBiTrNode)); 
  if( !headOfTree ) 
    return ERROR; 
  (*headOfTree)->lTag = Link;   //将要指向T 
  (*headOfTree)->rTag = Thread;    //将头节点的rchild用于索引 
  (*headOfTree)->rchild = *headOfTree;   //指向自身 
  if( T == NULL ){ 
    (*headOfTree)->lchild = *headOfTree; //若T为空树，则头节点的lchild 
              //指向自身 
  } 
  else{ 
    (*headOfTree)->lchild = T; 
    Pre = *headOfTree;     //赋值了全局变量Pre 
    InOrderThread(T);        //中序线索化 
    //printf("\n%c\n",Pre->data); 
            //执行完InOrderThread之后Pre指向最后 
            //一个节点 
    Pre->rTag = Thread;    
    Pre->rchild = *headOfTree; 
    //(*headOfTree)->rchild = Pre; 
  } 
  return OK; 
} 
//对中序线索化后的线索二叉树使用<<非递归>>的代码进行中序遍历 
//并且原来的递归形式的代码在这里是不再可以进行遍历。 
//  如果二叉树没有被线索化，也可以使用<<非递归>>的代码进行遍 
//  历的，但是那就需要借助于<<栈>>,但是在线索化之后，对线索 
//  化的二叉树进行<<非递归>>的遍历就不再需要栈的辅助。 
Status visit(ElemType c){ 
  printf("%c ", c); 
  return OK; 
} 
Status InOrderTeaverse_NoRecursion(ThrBiTree T, ThrBiTree headOfTree){ 
//headOfTree是T的头节点的指针，headOfTree->lchild = T; 
  while( T != headOfTree ){ 
    while( T->lTag == Link ){  //找到树(子树)的最左节点 
            //用while接替if// 
            //用if理解while// 
      T = T->lchild; 
    }         
    visit(T->data); 
 
    while( T->rTag == Thread && T->rchild != headOfTree){ 
            //这个while和下面的T=T->rchild 
            //可用ifelse语句理解。 
            //if(rchild是线索 && 不是最后一个节点)  
            //else(rchild不是线索)-->走到右孩子 
            //也就是代码T=T->rchild 
      T = T->rchild; 
      visit(T->data); 
    } 
    T = T->rchild; 
  } 
  return OK; 
} 
//求中序线索二叉树中中序序列下的第一个节点 
ThrBiTrNode* SeekFirstNode_InOrderThrBiTree(ThrBiTree T){ 
  if( T != NULL ){ 
    while( T->lTag == Link ){ 
      T = T->lchild; 
    } 
    return T; 
  } 
  return ERROR; 
} 
//求中序线索二叉树中节点P在中序序列下的下一个节点 
ThrBiTrNode* GetNextNode(ThrBiTrNode* CurrentP){ 
  if( CurrentP->rTag == Link ){  //有右孩子的时候，那么下一个就是以 
          //右孩子为root的树的最左下角元素。 
          //即seekFirstNode的返回值。 
    return SeekFirstNode_InOrderThrBiTree(CurrentP->rchild); 
  } 
  else{        //没有右孩子，则rchild指向后缀 
    return CurrentP->rchild; 
  } 
} 
//使用上面两个函数，SeekFirstNode_InOrderThrBiTree和GetNextNode来实现对 
//中序先做二叉树的遍历 
Status InOrderTraverse_NoRecursion_Method(ThrBiTree T, ThrBiTree head){ 
  for( T = SeekFirstNode_InOrderThrBiTree(T) ; T != head ; T = GetNextNode(T) ) 
    visit(T->data); 
  return OK; 
} 
 
//test 
/* ShowThread函数的目的是想在将T中序线索化之后，使用函数InOrderTraverse 
 * 函数中序遍历，输出一下节点中的信息以检验线索化，但是失败。原因是：在 
 * 线索化之后，空指针域都被应用，所有InOrderTraverse函数中的if( T )是满 
 * 足不了的，故失败。 
Status ShowThread(ThrBiTree C){ 
  printf("%d %d %d %d\n",(C->lchild)->data,(C->rchild)->data,C->lTag,C->rTag); 
  printf("%d %d\n",C->lTag,C->rTag); 
  return OK; 
 * */ 
 
//中序遍历二叉树 
Status InOrderTraverse(ThrBiTree T){ 
  if( T ){ 
    InOrderTraverse(T->lchild); 
    visit(T->data); 
    InOrderTraverse(T->rchild); 
  } 
  return OK; 
} 
int main(){ 
  ThrBiTree T,R,Head = NULL; 
  InitThreadBinaryTree(&T); 
 
  printf("Please Input Binary Tree By PreOrder\n  "); 
  ThreadBinaryTree_PreOrderInput(&T); 
 
  printf("  InOrder Traverse before Thread with Recursion\n"); 
  InOrderTraverse(T); 
  printf("\n"); 
 
  CreateInOrderThreadBinaryTree(T,&Head); 
  printf("  InOrder Traverse after Thread with no-Recursion\n"); 
  InOrderTeaverse_NoRecursion(T,Head); 
  printf("\n"); 
 
  printf("The root is %c \n", T->data);  //不能够通过指针形参的值改变指针实参的值 
            //或者说，对指针形参的改变不会作用到指针 
            //实参上。 
 
  ThrBiTrNode *firstOfInOrder = NULL,*secondOfInOrder = NULL; 
  if( SeekFirstNode_InOrderThrBiTree(T) != ERROR ){ 
    firstOfInOrder = SeekFirstNode_InOrderThrBiTree(T); 
    printf("the value of First Node of InOrderThreadBinaryTree is %c\n", firstOfInOrder->data); 
  } 
  secondOfInOrder = GetNextNode(firstOfInOrder); 
  printf("the value of Node after D is: %c \n", secondOfInOrder->data); 
  secondOfInOrder = GetNextNode(secondOfInOrder); 
  printf("the value of Node after B is: %c \n", secondOfInOrder->data); 
  secondOfInOrder = GetNextNode(secondOfInOrder); 
  printf("the value of Node after E is: %c \n", secondOfInOrder->data); 
  secondOfInOrder = GetNextNode(secondOfInOrder); 
  printf("the value of Node after A is: %c \n", secondOfInOrder->data); 
  secondOfInOrder = GetNextNode(secondOfInOrder); 
  printf("the value of Node after C is: %c \n", secondOfInOrder->data); 
  secondOfInOrder = GetNextNode(secondOfInOrder); 
  printf("the value of Node after G is: %c \n", secondOfInOrder->data); 
  secondOfInOrder = GetNextNode(secondOfInOrder); 
  printf("the value of Node after root is: %c \n", secondOfInOrder->data); 
 
  printf("  InOrder Traverse after Thread with no-Recursion Method_2\n"); 
  InOrderTraverse_NoRecursion_Method(T,Head); 
 
  return 0; 
} 

以上就是线索二叉树及遍历的实例，如有疑问请留言或者到本站社区交流讨论，感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！

# 线索二叉树及遍历  # 数据结构中线索二叉树的遍历  # C语言数据结构二叉树之堆的实现和堆排序详解  # C语言数据结构二叉树先序、中序、后序及层次四种遍历  # C语言二叉树的三种遍历方式的实现及原理  # C语言实现二叉树的基本操作  # C语言数据结构之二叉树的非递归后序遍历算法  # C语言植物大战数据结构二叉树堆  # 遍历  # 递归  # 二叉树  # 子树  # 的是  # 为空  # 则将  # 那就  # 可以使用  # 链式  # 线性化  # 都是  # 都有  # 在这里  # 但是在  # 在这个  # 出了  # 第一个  # 目的是  # 走到 

相关文章： C++如何编写函数模板？（泛型编程入门）  个人网站制作流程图片大全,个人网站如何注销？    如何快速搭建支持数据库操作的智能建站平台？  开心动漫网站制作软件下载,十分开心动画为何停播？  如何通过宝塔面板实现本地网站访问？  网站企业制作流程,用什么语言做企业网站比较好？  如何制作一个表白网站视频,关于勇敢表白的小标题？  定制建站平台哪家好？企业官网搭建与快速建站方案推荐  如何有效防御Web建站篡改攻击？  香港代理服务器配置指南：高匿IP选择、跨境加速与SEO优化技巧  魔毅自助建站系统：模板定制与SEO优化一键生成指南  红河网站制作公司,红河事业单位身份证如何上传？  如何在阿里云通过域名搭建网站？  MySQL查询结果复制到新表的方法(更新、插入)  北京网站制作公司哪家好一点,北京租房网站有哪些？  香港服务器建站指南：免备案优势与SEO优化技巧全解析  专业网站设计制作公司,如何制作一个企业网站，建设网站的基本步骤有哪些？  如何用wdcp快速搭建高效网站？  定制建站价位费用解析与套餐推荐全攻略  贸易公司网站制作流程,出口贸易网站设计怎么做？  如何批量查询域名的建站时间记录？  开封网站制作公司,网络用语开封是什么意思？  视频网站app制作软件,有什么好的视频聊天网站或者软件？  兔展官网 在线制作,怎样制作微信请帖？  制作网站外包平台,自动化接单网站有哪些？  相册网站制作软件,图片上的网址怎么复制？  建站之星后台密码遗忘如何找回？  详解jQuery停止动画——stop()方法的使用  如何配置支付宝与微信支付功能？  北京制作网站的公司,北京铁路集团官方网站？  如何通过可视化优化提升建站效果？  建站之星如何实现PC+手机+微信网站五合一建站？  官网自助建站平台指南：在线制作、快速建站与模板选择全解析  江苏网站制作公司有哪些,江苏书法考级官方网站？  如何解决VPS建站LNMP环境配置常见问题？  威客平台建站流程解析：高效搭建教程与设计优化方案  已有域名如何免费搭建网站？  GML (Geography Markup Language)是什么，它如何用XML来表示地理空间信息？  如何选择CMS系统实现快速建站与SEO优化？  网站制作和推广的区别,想自己建立一个网站做推广，有什么快捷方法马上做好一个网站？  定制建站流程步骤详解：一站式方案设计与开发指南  javascript中对象的定义、使用以及对象和原型链操作小结  深入理解Android中的xmlns:tools属性  成都网站制作价格表,现在成都广电的单独网络宽带有多少的，资费是什么情况呢？  如何快速搭建高效WAP手机网站？  制作ppt免费网站有哪些,有哪些比较好的ppt模板下载网站？  香港网站服务器数量如何影响SEO优化效果？  网站app免费制作软件,能免费看各大网站视频的手机app？  盘锦网站制作公司,盘锦大洼有多少5G网站？