C语言数据结构之线索二叉树及其遍历
更新时间:2020年4月25日 17:30 点击:1509
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#中使用二叉树实时计算海量用户积分排名的实现详解,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-06-25
- 这篇文章主要介绍了举例讲解C语言程序中对二叉树数据结构的各种遍历方式,先序中序后序二叉树遍历几乎成了最老生常谈的数据结构基础知识,的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了一波二叉树遍历问题的C++解答实例分享,包括节点打印和转换为镜像等问题的解答,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了C++使用递归和非递归算法实现的二叉树叶子节点个数计算方法,涉及C++二叉树的定义、遍历、统计相关操作技巧,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了C语言数据结构之二叉树的非递归后序遍历算法的相关资料,希望通过本文能帮助到大家,让大家实现这样的功能,需要的朋友可以参考下...2020-04-25
- 二叉树是数据结构中的树的一种特殊情况,有关二叉树的相关概念,这里不再赘述,如果不了解二叉树相关概念,建议先学习数据结构中的二叉树的知识点...2020-04-25
- 这篇文章主要介绍了php实现的二叉树遍历算法,结合具体实例形式分析了php针对二叉树的常用前序、中序及后序遍历算法实现技巧,需要的朋友可以参考下...2017-06-20
- 这篇文章主要介绍了如何在Python中创建二叉树,帮助大家更好的理解和学习使用python,感兴趣的朋友可以了解下...2021-03-30
- 这篇文章主要介绍了C语言 二叉查找树性质详解及实例代码的相关资料,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了C++基于先序、中序遍历结果重建二叉树的方法,结合实例形式分析了基于C++构建二叉树的相关操作技巧,需要的朋友可以参考下...2020-04-25
C++基于递归和非递归算法判定两个二叉树结构是否完全相同(结构和数据都相同)
这篇文章主要介绍了C++基于递归和非递归算法判定两个二叉树结构是否完全相同,若判断二叉树的结构和数据都相同则为完全相同.涉及C++二叉树的创建、遍历、比较等相关操作技巧,需要的朋友可以参考下...2020-04-25- 这篇文章主要为大家详细介绍了C++实现二叉树基本操作,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2020-04-25
- 这篇文章主要介绍了C语言实现二叉树遍历的迭代算法,包括二叉树的中序遍历、先序遍历及后序遍历等,是非常经典的算法,需要的朋友可以参考下...2020-04-25
- 在本篇文章里小编给大家分享了关于c++先序二叉树的构建的相关知识点,需要的朋友们跟着学习下。...2020-04-25
- 这篇文章主要介绍了平衡二叉树的实现实例,需要的朋友可以参考下...2020-04-25
- 这篇文章主要为大家详细介绍了C++二叉树实现词频分析功能,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2020-04-25
- 这篇文章主要介绍了C++ 数据结构二叉树(前序/中序/后序递归、非递归遍历)的相关资料,这里提供实例代码来帮助大家理解掌握二叉树,需要的朋友可以参考下...2020-04-25
C++实现LeetCode(105.由先序和中序遍历建立二叉树)
这篇文章主要介绍了C++实现LeetCode(105.由先序和中序遍历建立二叉树),本篇文章通过简要的案例,讲解了该项技术的了解与使用,以下就是详细内容,需要的朋友可以参考下...2021-07-23- 这篇文章主要介绍了C语言二叉树的非递归遍历,包括了先序遍历、中序遍历与后序遍历,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了C++非递归建立二叉树的方法,实例分析了二叉树的原理与C++实现技巧,具有一定参考借鉴价值,需要的朋友可以参考下...2020-04-25