C语言实现线索二叉树的定义与遍历示例

本文实例讲述了C语言实现线索二叉树的定义与遍历。分享给大家供大家参考,具体如下:

#include <stdio.h>
#include <malloc.h>
typedef char TElemType;
// 二叉树的二叉线索存储表示
typedef enum{
 Link,
 Thread
}PointerTag; // Link(0):指针,Thread(1):线索
typedef struct BiThrNode
{
 TElemType data;
 struct BiThrNode *lchild,*rchild; // 左右孩子指针
 PointerTag LTag,RTag; // 左右标志
}BiThrNode,*BiThrTree;
TElemType Nil = ' '; // 字符型以空格符为空
BiThrTree pre; // 全局变量,始终指向刚刚访问过的结点
// 按先序输入二叉线索树中结点的值,构造二叉线索树T
// 空格(字符型)表示空结点
int CreateBiThrTree(BiThrTree *T)
{
 TElemType h;
 scanf("%c",&h);
 if(h==Nil)
 *T=NULL;
 else
 {
 *T=(BiThrTree)malloc(sizeof(BiThrNode));
 if(!*T)
  exit(0);
 (*T)->data=h; // 生成根结点(先序)
 CreateBiThrTree(&(*T)->lchild); // 递归构造左子树
 if((*T)->lchild) // 有左孩子
  (*T)->LTag=Link;
 CreateBiThrTree(&(*T)->rchild); // 递归构造右子树
 if((*T)->rchild) // 有右孩子
  (*T)->RTag=Link;
 }
 return 1;
}
// 算法6.7 P135
// 中序遍历进行中序线索化。
void InThreading(BiThrTree p)
{
 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); // 递归右子树线索化
 }
}
// 算法6.6 P134
// 中序遍历二叉树T,并将其中序线索化,Thrt指向头结点。
int InOrderThreading(BiThrTree *Thrt,BiThrTree T)
{ *Thrt=(BiThrTree)malloc(sizeof(BiThrNode)); // 建头结点
 if(!*Thrt)
 exit(0);
 (*Thrt)->LTag=Link; //标志左孩子为指针
 (*Thrt)->RTag=Thread; //标志右孩子为线索
 (*Thrt)->rchild=*Thrt; // 右指针回指
 if(!T) // 若二叉树空,则左指针回指
 (*Thrt)->lchild=*Thrt;
 else
 {
 (*Thrt)->lchild=T; //头结点左指针指向树的根
 pre = *Thrt;
 InThreading(T); // 中序遍历进行中序线索化
 pre->RTag=Thread; // 最后一个结点线索化
 pre->rchild=*Thrt;
 (*Thrt)->rchild=pre;
 }
 return 1;
}
// 算法6.5 P134
// 中序遍历二叉线索树T(头结点)的非递归算法。
int InOrderTraverse_Thr(BiThrTree T,int(*Visit)(TElemType))
{
 BiThrTree p;
 p=T->lchild; // p指向根结点
 while(p!=T)
 { // 空树或遍历结束时,p==T
 while(p->LTag==Link)
  p=p->lchild;
 if(!Visit(p->data)) // 访问其左子树为空的结点
  return 0;
 while(p->RTag==Thread&&p->rchild!=T)
 {
  p=p->rchild;
  Visit(p->data); // 访问后继结点
  }
 p=p->rchild;
 }
 return 1;
}
int vi(TElemType c)
{
 printf("%c ",c);
 return 1;
}
int main()
{
 BiThrTree H,T;
 printf("请按先序输入二叉树(如:ab三个空格,表示a为根结点,"
 "b为左子树的二叉树)\n");
 CreateBiThrTree(&T); // 按先序产生二叉树
 InOrderThreading(&H,T); // 中序遍历,并中序线索化二叉树
 printf("中序遍历(输出)二叉线索树:\n");
 InOrderTraverse_Thr(H,vi); // 中序遍历(输出)二叉线索树
 printf("\n");
 system("pause");
 return 0;
}

运行结果:

希望本文所述对大家C语言程序设计有所帮助。

(0)

相关推荐

  • PHP实现的线索二叉树及二叉树遍历方法详解

    本文实例讲述了PHP实现的线索二叉树及二叉树遍历方法.分享给大家供大家参考,具体如下: <?php require 'biTree.php'; $str = 'ko#be8#tr####acy#####'; $tree = new BiTree($str); $tree->createThreadTree(); echo $tree->threadList() . "\n";从第一个结点开始遍历线索二叉树 echo $tree->threadListReserv

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

    C语言数据结构之线索二叉树及其遍历 遍历二叉树就是以一定的规则将二叉树中的节点排列成一个线性序列,从而得到二叉树节点的各种遍历序列,其实质是:对一个非线性的结构进行线性化.使得在这个访问序列中每一个节点都有一个直接前驱和直接后继.传统的链式结构只能体现一种父子关系,¥不能直接得到节点在遍历中的前驱和后继¥,而我们知道二叉链表表示的二叉树中有大量的空指针,当使用这些空的指针存放指向节点的前驱和后继的指针时,则可以更加方便的运用二叉树的某些操作.引入线索二叉树的目的是: 为了加快查找节点的前驱和后继

  • C语言实现线索二叉树的定义与遍历示例

    本文实例讲述了C语言实现线索二叉树的定义与遍历.分享给大家供大家参考,具体如下: #include <stdio.h> #include <malloc.h> typedef char TElemType; // 二叉树的二叉线索存储表示 typedef enum{ Link, Thread }PointerTag; // Link(0):指针,Thread(1):线索 typedef struct BiThrNode { TElemType data; struct BiThrN

  • Python数据结构与算法之二叉树结构定义与遍历方法详解

    本文实例讲述了Python数据结构与算法之二叉树结构定义与遍历方法.分享给大家供大家参考,具体如下: 先序遍历,中序遍历,后序遍历 ,区别在于三条核心语句的位置 层序遍历  采用队列的遍历操作第一次访问根,在访问根的左孩子,接着访问根的有孩子,然后下一层 自左向右一一访问同层的结点 # 先序遍历 # 访问结点,遍历左子树,如果左子树为空,则遍历右子树, # 如果右子树为空,则向上走到一个可以向右走的结点,继续该过程 preorder(t): if t: print t.value preorde

  • C语言实现线索二叉树的前中后创建和遍历详解

    目录 1.结构 1.1初始化tag 2.基本操作 2.1先序创建二叉树 2.2.先序线索化 2.2.1.先序遍历 2.3.中序线索化 2.3.1中序遍历 2.4.后序线索化 2.4.1后序遍历 总结 1.结构 #include<stdio.h> #include<stdlib.h> #define false 0 #define true 1 using namespace std; typedef struct BTnode{ int data; struct BTnode *l

  • C语言线索二叉树基础解读

    目录 线索二叉树的意义 线索二叉树的定义 线索二叉树结构的实现 二叉树的线索存储结构 二叉树的中序线索化 线索二叉树的中序遍历 总结 线索二叉树的意义 对于一个有n个节点的二叉树,每个节点有指向左右孩子的指针域.其中会出现n+ 1个空指针域,这些空间不储存任何事物,浪费着内存的资源. 对于一些需要频繁进行二叉树遍历操作的场合,二叉树的非递归遍历操作过程相对比较复杂,递归遍历虽然简单明了,但是会有额外的开销,对于操作的时间和空间都比较浪费. 我们可以考虑利用这些空地址,存放指向节点在某种遍历次序下

  • C语言递归实现线索二叉树

    本文实例为大家分享了C语言递归实现线索二叉树的具体代码,供大家参考,具体内容如下 描述:将二叉树中结点的空左孩子指针域指向前驱结点,将空的右孩子指针域指向后继结点. code: #pragma warning(disable:4996) #include<stdio.h> #include<stdlib.h> typedef struct TreeNode { char data; struct TreeNode *lchild, *rchild; int ltag, rtag;

  • C语言数据结构之二叉树的非递归后序遍历算法

    C语言数据结构之二叉树的非递归后序遍历算法 前言: 前序.中序.后序的非递归遍历中,要数后序最为麻烦,如果只在栈中保留指向结点的指针,那是不够的,必须有一些额外的信息存放在栈中. 方法有很多,这里只举一种,先定义栈结点的数据结构 typedef struct{Node * p; int rvisited;}SNode //Node 是二叉树的结点结构,rvisited==1代表p所指向的结点的右结点已被访问过. lastOrderTraverse(BiTree bt){ //首先,从根节点开始,

  • JavaScript实现二叉树定义、遍历及查找的方法详解

    本文实例讲述了JavaScript实现二叉树定义.遍历及查找的方法.分享给大家供大家参考,具体如下: 二叉树(binary tree) 在写这篇文章之前说一下数据结构和算法这个系列,这个系列包含了很多东西,比如啥子排序,线性表,广义表,树,图这些大家都是知道的,但是这些东西我们学了之后工作中能用到的又有多少呢,据我所知绝大部分公司,一线码农,屌丝,程序猿是用不到这些东西,既然这样为啥子我还要强调这个系列呢,本人觉得算法和数据结构是程序的基本功,前提想脱离一线码农,普通程序猿行列,说得通俗一点就是

  • C语言二叉树的三种遍历方式的实现及原理

    二叉树遍历分为三种:前序.中序.后序,其中序遍历最为重要.为啥叫这个名字?是根据根节点的顺序命名的. 比如上图正常的一个满节点,A:根节点.B:左节点.C:右节点,前序顺序是ABC(根节点排最先,然后同级先左后右):中序顺序是BAC(先左后根最后右):后序顺序是BCA(先左后右最后根). 比如上图二叉树遍历结果 前序遍历:ABCDEFGHK 中序遍历:BDCAEHGKF 后序遍历:DCBHKGFEA 分析中序遍历如下图,中序比较重要(java很多树排序是基于中序,后面讲解分析) 下面介绍一下,二

  • C语言深入浅出解析二叉树

    目录 树概念及结构 相关概念 树的表示 树在实际中的运用(表示文件系统的目录树结构) 二叉树概念及结构 概念 需要注意的特殊二叉树 二叉树的性质 二叉树的存储结构 顺序存储 链式存储 总结 树概念及结构 树是一种 非线性 的数据结构,它是由 n ( n>=0 )个有限结点组成一个具有层次关系的集合 把它叫做树是因 为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的 注意: 有一个特殊的结点,称为根结点,根节点没有前驱结点 除根节点外,其余结点被分成M(M>0)个互不相交的集合T1.T2.

随机推荐