线索二叉树的实现

线索二叉树算法#include#include#includetypedef char DataType;/*定义DataType类型*/typedef enum {Link,Thread}PointerTag;typedef struct node{DataType data;struct node *lchild, *rchild;/*左右孩子子树*/PointerTag LTag,RTag;}BiThrNode; /*结点类型*/typedef BiThrNode *BiThrTree ;/*二叉树类型*/void CreatBinTree(BiThrTree *T){ /*构造二叉链表,注意:输入序列是先序序列*/char ch;if ((ch=getchar())==' ')*T=NULL;else{ /*读入非空格*/*T=(BiThrNode *)malloc(sizeof(BiThrNode));/*生成结点*/ (*T)->data=ch;(*T)->LTag=Link;(*T)->RTag=Link;CreatBinTree(&(*T)->lchild); /*构造左子树 */CreatBinTree(&(*T)->rchild); /*构造右子树*/}}BiThrTree pre;/*全局变量*/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;}/*后继线索*/ pre=p;/*保持pre指向p*/InThreading(p->rchild);/*右子树线索化*/}}int InOrderThreading(BiThrTree *Thrt,BiThrTree T)/*中序遍厉二叉树T，并将其中序线索化，Thrt指向头结点*/{ if(!(*Thrt=(BiThrTree)malloc(sizeof(BiThrNode)))) 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->rchild=*Thrt;pre->RTag=Thread;/*最后一个结点线索化*/(*Thrt)->rchild=pre;}return 1;}int print(BiThrTree e){printf("%d %c %d\n",e->LTag,e->data,e->RTag);return 1;}int InOrderTraverse(BiThrTree T,int (* visit)(BiThrTree e))/*T指向头结点，头结点的左链lchild指向根结点，中序遍厉二叉树*/ {BiThrTree p;p=T->lchild;/*p指向根结点*/while(p!=T)/*空树或遍厉结束时，p==T*/{while(p->LTag==Link) p=p->lchild;if(!visit(p)) return 0;/*打印*/while(p->RTag==Thread&&p->rchild!=T){p=p->rchild;visit(p);}/*访问后继结点*/p=p->rchild;}return 1;}void main(){ /*测试程序*/BiThrTree T,Thrt;CreatBinTree(&T);InOrderThreading(&Thrt,T);InOrderTraverse(Thrt,print);}/*可输入"-+a *b -c d /e f "来测试(注意空格)*/。

6.4 线索化二叉树从前面的讨论可知，遍历二叉树就是将非线性结构的二叉树线性化，即按一定规则将二叉树中的结点排列成一个线性序列依次访问。

如图6.20(a)所示的二叉树，经中序遍历得到线性序列：BADEC，经前序遍历得到线性序列：ABCDE，经后序遍历得到线性序列：BEDCA。

在这些线性序列中，二叉树中的每个结点（除第一个和最后一个外）有且仅有唯一的一个前趋和唯一的一个后继，很容易找到各个结点的直接前驱和直接后继。

但当以二叉链表作为二叉树的存储结构时，只能找到结点的左、右孩子，而不能直接找到前驱和后继，只有在遍历的动态过程中得到这些信息。

如果将这些信息在第一次遍历时保存起来，在需要再次对二叉树进行“遍历”时就可以将二叉树视为线性结构进行访问，从而简化遍历操作。

那么，如何存储遍历中得到的结点前驱和后继的信息呢？一个简单的办法是在每个结点上增加两个指针域fwd和bkwd，分别指向存储遍历中得到的结点前驱和后继。

fwd L child data R child bkwd这是采用多重链表来表示二叉树。

这种方法虽简单易行，但这种结构的存储密度将大大降低，浪费存储空间。

另一种方法，是利用原有链域L child 和R child的空链域。

在n个结点的二叉链表中有2n个孩子链域，其中仅有n-1个链域是用来指示结点的左右孩子，而另外n+1个链域是空链域。

现在把这些空链域利用起来，使其指向结点的前驱或后继；对那些原来就不为空的链域，则仍然指向左或右孩子。

如果把指向前驱和后继的指针称为线索（Thread），那么，如何区分指向左、右孩子的指针和指向前驱、后继的线索呢？在原结点结构上增加标志域定义为：0 Lchild为左指针，指向左孩子0 Rchild为右指针，指向右孩子ltag＝rtag＝1 Lchild为左线索，指向前驱 1 Rchild为右线索，指向后继以这种结点构成的二叉链表作为二叉树的存储结构，叫做线索链表，其C语言类型说明如下：Typedef struct ThreadTNode{enum{0，1} ltag, rtag;Elem Type data;Struct ThreadTNode *Lchild, *Rchild;}ThreadTNode, *ThreadTree;为了节省内存空间，我们用C语言的位段方法将结点中的左标志域和右标志域与数据域合并在一个存储单元中（即各用一位表示左标志和右标志，其余各位表示结点值）。

斐波那契数列二叉树斐波那契数列是一种非常有趣的数列，它的每一项都是前两项的和。

例如，斐波那契数列的前几项是1、1、2、3、5、8、13、21、34、55、89、144……这个数列在数学和计算机科学中都有广泛的应用，其中一个应用就是构建斐波那契数列二叉树。

斐波那契数列二叉树是一种特殊的二叉树，它的每个节点都对应着斐波那契数列中的一个数。

具体来说，根节点对应着第n项斐波那契数，左子树对应着第n-1项斐波那契数，右子树对应着第n-2项斐波那契数。

这样，我们就可以通过斐波那契数列来构建一棵二叉树。

斐波那契数列二叉树的构建过程非常简单，我们可以使用递归的方式来实现。

具体来说，我们可以定义一个函数fibonacciTree(n)，它的返回值是一棵斐波那契数列二叉树，其中n表示根节点对应的斐波那契数列的下标。

函数的实现如下：```class TreeNode:def __init__(self, val=0, left=None, right=None):self.val = valself.left = leftself.right = rightdef fibonacciTree(n):if n == 0:return TreeNode(0)elif n == 1:return TreeNode(1)else:left = fibonacciTree(n-1)right = fibonacciTree(n-2)return TreeNode(left.val + right.val, left, right)```在这个函数中，我们首先判断n的值，如果n为0或1，则直接返回一个只有根节点的二叉树。

否则，我们递归地构建左子树和右子树，然后将它们的值相加作为根节点的值，最后返回一棵完整的二叉树。

使用上面的代码，我们可以构建出斐波那契数列二叉树的任意一棵子树。

例如，如果我们想构建第5项斐波那契数列对应的子树，可以调用fibonacciTree(5)函数，得到如下的二叉树：```5/ \3 2/ \ / \2 1 1 1```这棵二叉树的根节点对应着第5项斐波那契数，左子树对应着第4项斐波那契数，右子树对应着第3项斐波那契数。

实验九线索二叉树的创建及遍历实验目的：掌握二叉树的线索链表存储结构，能够实现二叉树的线索链表的创建、遍历等基本操作实验要求：1、认真阅读和掌握教材上和本实验相关的内容及算法2、上机将线索二叉树的线索链表存储表示的创建和遍历算法实现。

3、进行简单的输入输出验证。

实验内容：编程实现二叉树的线索链表存储表示的基本操作，这些基本操作包括：线索二叉树的创建、线索二叉树的中序遍历算法的实现。

要求对程序中的一些关键语句要有注释，并能够进行简单的输入输出验证。

参考代码#include <stdlib.h>#include <stdio.h>#define OVERFLOW 0//线索二叉树的二叉链表存储定义typedef enum PointerTag {LINK=0,THREAD=1};struct BiThrNode{char data;struct BiThrNode * lchild, * rchild;PointerTag LTag, RTag;};typedef struct BiThrNode BiThrNode;typedef BiThrNode * BiThrTree;/*****************************************************************\** 按先序次序输入二叉树中的结点的值（一个字符）构造二叉链表表示的二叉树，* 字符'#'表示空树。

** 例如，一棵二叉树的三种遍历次序为：* 先序：-+a*b-cd/ef 中序：a+b*c-d-e/f 后序：abcd-*+ef/* 程序中应该输入：-+a##*b##-c##d##/e##f##** 又如，一棵二叉树的三种遍历次序为：* 先序：ABDFGCEH 中序：BFDGACHE 后序：FGDBHECA* 程序中应该输入：AB#DF##G##C#EH###*\******************************************************************/ void CreateBiTree(BiThrTree &T){char ch;ch = getchar();if (ch=='#') T=NULL;else{if (!(T = (BiThrNode *)malloc(sizeof(BiThrNode)))) exit(OVERFLOW);T->data = ch;T->LTag = LINK;T->RTag = LINK;CreateBiTree(T->lchild);CreateBiTree(T->rchild);}return;}//CreateBiTreevoid PrintBiTree(BiThrTree T){//按中序遍历次序输出二叉树T中的结点的值（一个字符），二叉树T用二叉链表存储。

莫里斯算法莫里斯算法（Morris Traversal）是一种二叉树遍历的算法，通过只使用一个指针和利用线索二叉树的思想，实现对二叉树的中序遍历，时间复杂度为O(n)，空间复杂度为O(1)。

1. 线索二叉树线索二叉树是指将一颗二叉树中所有的空指针域指向该节点的直接前驱节点或直接后继节点的二叉树。

线索化后，原本空闲的指针域存储前驱或后继的指针，可以方便地实现对二叉树的遍历。

在递归遍历的过程中，需要记录每个节点是否已经被遍历。

线索二叉树分为前序线索二叉树、中序线索二叉树、后序线索二叉树。

其中，利用中序线索二叉树可以实现对二叉树的中序遍历。

2. Morris遍历算法Morris遍历算法是一种利用线索二叉树对二叉树进行中序遍历的算法，它的核心思想是在遍历节点的过程中，利用空闲的指针域存储前驱或后继的指针，从而实现对二叉树的遍历。

Morris遍历算法对于空间的要求比较严格，它只需要使用一个指针来实现对二叉树的遍历，因此空间复杂度为O(1)，非常适合解决空间限制的问题。

在时间复杂度方面，Morris遍历算法需要在遍历每个节点和寻找其前驱节点时，都需要遍历部分节点，因此时间复杂度为O(n)。

具体而言，Morris遍历算法利用线索化指针判断节点是否被访问过，从而实现对二叉树的遍历。

Morris遍历算法的具体流程如下：1）初始化当前节点为根节点2）重复以下操作，直到当前节点为空a. 如果当前节点没有左孩子节点，则输出当前节点，将其右孩子节点作为下一次要访问的节点，更新当前节点为右孩子节点b. 如果当前节点存在左孩子节点，则寻找当前节点的左子树中的最右侧节点，该节点为当前节点的直接前驱节点i. 如果该节点的右孩子指向当前节点，则说明当前节点是第二次访问该节点，将其右孩子设为null，输出该节点，更新当前节点为右孩子节点ii. 如果该节点的右孩子指向null，则说明当前节点为第一次访问该节点，将其右孩子设为当前节点，更新当前节点为左孩子节点Morris遍历算法的特点是利用空闲的指针域存储前驱或后继的指针，实现对二叉树的遍历。

6·4 线索二叉树1、线索二叉树的结点结构二叉树的遍历本质上是将一个复杂的非线性结构转换为线性结构，使每个结点都有了唯一前驱和后继（第一个结点无前驱，最后一个结点无后继）。

对于二叉树的一个结点，查找其左右子女是方便的，其前驱后继只有在遍历中得到。

为了容易找到前驱和后继，有两种方法。

一是在结点结构中增加向前和向后的指针fwd和bkd，这种方法增加了存储开销，不可取；二是利用二叉树的空链指针。

现将二叉树的结点结构重新定义如下：其中：ltag=0 时ltag=1 时lchild指向前驱；rtag=0 时rchild指向左子女；rtag=1 时rchild指向后继；以这种结点结构构成的二叉链表作为二叉树的存储结构，叫做线索链表，指向前驱和后继的指针叫线索，加上线索的二叉树叫线索二叉树，对二叉树进行某种形式遍历使其变为线索二叉树的过程叫线索化。

学习线索化时，有三点必须注意：一是何种“序”的线索化，是先序、中序还是后序；二是要“前驱”线索化、“后继”线索化还是“全”线索化（前驱后继都要）；三是只有空指针处才能加线索。

2、对二叉树进行中序线索化的算法bithptr *pre; /* 全程变量*/void INTHREAD(bithptr *p){if(p!=NULL){ INTHREAD(p->lchild); /* 左子树线索化*/if(p->lchild==NULL) { p->ltag=1;p->lchild=pre;}if(p->rchild==NULL) p->rtag=1;if(pre!=NULL && pre->rtag==1) pre->rchild=p;pre=p; /* 前驱指向当前结点*/INTHREAD(p->rchild); /* 右子树线索化*/}3、在线索二叉树上查找前驱和后继（1）中序线索二叉树：若结点的ltag=1，lchild指向其前驱；否则，该结点的前驱是以该结点为根的左子树上按中序遍历的最后一个结点。

令狐采学创作全令狐采学线索链表应用报告提交人：郭超峰班级：计算机1404学号：20143678一：问题定义及需求分析二：概要设计三：详细设计四：调试分析五：使用说明六:测试结果（截屏）七：组内个人设计部分八：附录（带源代码）一：问题定义及需求分析课题：全线索链表应用课题描述：对二叉树的二叉链表结点增加两个指针域，前驱指针prior和后继指针next。

通过该结点构造全线索二叉链表。

课题要求：设计一个全线索二叉链表的应用程序。

1)创建全线索二叉树。

2)完成全线索二叉树的主要基本操作。

3)给出简单应用实例。

输入输出形式：本实验中全线索二叉树元素均为整形（int）。

程序功能：1：创建二叉树。

2：对二叉树中序遍历进行全线索化。

3：求树中任意元素的前驱、后继、左孩子、右孩子。

4：对二叉树进行元素的插入和删除。

5：对二叉树的清空操作。

测试数据：测试的二叉树为如下二：概要设计int data;BiThrNodetypedef struct{ElemType data[100];int Stacksize;}SqStack; //抽象数据类型SqStack void *InitStack(SqStack *p); //初始化栈int StackEmpty(SqStack *S); //判断栈空int Push(SqStack *S,ElemType e); //入栈ElemType Pop(SqStack *S,ElemType e); //出栈BiThrTree CreatBiTree(BiThrTree p); //二叉树的构建BiThrTree InOrderThreading(BiThrTree p); //中序线索化int InOrder(BiThrTree p); //求中序序列int qianqu(BiThrTree p); //求前驱int houji(BiThrTree p); //求后继int zuohai(BiThrTree p); //求左孩子int youhai(BiThrTree p); //求右孩子int Insert(BiThrTree p); //插入元素int Delete(BiThrTree p); //删除元素int Clear(BiThrTree p); //将二叉树清空Int main() //主函数调用上述函数求解相应问题三：详细设计各模块的算法如下：Status InitStack(SqStack *p){//初始化栈p.Stacksize=-1;return OK;}Status StackEmpty(SqStack *S){//判断栈空if(p->Stacksize=-1)return TURE;else return FALSE;}Status Push(SqStack *S,ElemType e){ //入栈P->Stacksize=p->Stacksize+1;P->data[p->Stacksize]=e;return OK;}Status Pop(SqStack *S,ElemType e){//出栈e=p->data[p->Stacksize];P->Stacksize=p->Stacksize-1;return e;}Status CreatBiTree(BiThrTree p){//二叉树的构建scanf(&m);if(m==0) p=NULL;else{if(!(p=(BiThrTree)malloc(sizeof(BiThrNode)))) exit(OVERFLOW); //存储分配失败else{p->data=m;p->prior=NULL;p->next=NULL;p->lchild=NULL;p->rchild=NULL;p->lchild=CreatBiTree(p->lchild); //递归构建左子树p->rchild=CreatBiTree(p->rchild); //递归构建右子树}}return p; //返回头节点}Status InOrderThreading(BiThrTree p){//中序线索化InitStack(&S);if(!(Thr=(BiThrTree)malloc(sizeof(BiThrNode))))exit (OVERFLOW); //存储分配失败Thr->data=0; Thr->lchild=p; //Thr为头节点Thr->rchild=NULL; p1=p;pre=Thr; //pre为全局变量，指向p1的前一个节点while(p1||!StackEmpty(&S)){if(p1){Push(&S,p1); p1=p1->lchild; //进栈}else{p1=Pop(&S,p1); //出栈pre->next=p1;p1->prior=pre; //中序线索化 pre=p1;p1=p1->rchild;}}pre->next=Thr; //最后一个节点线索化 Thr->prior=pre;return Thr; //返回头节点}Status InOrder(BiThrTree p){//求中序序列for(p1=p->next;p1!=p;p1=p1->next){printf(p1->data); //输出节点值}求前驱、后继、左孩子、右孩子思路差距不大，下面以求前驱为例：Status qianqu(BiThrTree p){//求前驱scanf(&e); //输入要查找元素for(p2=p->next;p2->data!=0;p2=p2->next){ //逐个检查树中元素if(p2->data==e){p3=p2->prior;if(p3->data==0){Printf(“该点不存在中序前驱！”)；break;}else{printf("该点的中序前驱为：");printf(p3->data); //输出e的前驱break;}}}Status Insert(BiThrTree p){//插入元素p2=(BiThrTree)malloc(sizeof(BiThrNode));printf("输入所要插入的节点：");scanf(&a);printf("输入所要查找的节点：");scanf(&b);for(p1=p->next;p1!=p;p1=p1->next){ //逐个检查树中元素if(p1->data==b)break;}if(p1==p)printf("该节点不存在！\n");else{switch(j){case 1:{ //插入元素作为左孩子p2->data=a;p2->lchild=NULL;p2->rchild=NULL;p2->next=p1;p2->prior=p1->prior;p1->prior->next=p2;p1->prior=p2;p1->lchild=p2;break;}case 2:{ //插入元素作为右孩子 p2->data=a;p2->lchild=NULL;p2->rchild=NULL;p2->prior=p1;p2->next=p1->next;p1->next->prior=p2;p1->next=p2;p1->rchild=p2;break;}default :exit(0);}}//switch}//else}Status Delete(BiThrTree p){//删除元素scanf(&a); //输入要删除的元素for(p1=p->next;p1!=p;p1=p1->next){ //逐个检查树中是否有此元素if(p1->data==a) break;}if(p1==p) printf("该树中无此节点！");else{if(p1==p1->prior->rchild){ //元素作为右孩子p1->prior->next=p1->next;p1->next->prior=p1->prior;p1->prior->rchild=NULL;free(p1); //释放P1 }if(p1==p1->next->lchild){ //元素作为左孩子p1->prior->next=p1->next;p1->next->prior=p1->prior;p1->next->lchild=NULL;free(p1); //释放p1 }}//else}//DeleteStatus Clear(BiThrTree p){//将二叉树清空for(p1=p->next;p2!=p;){p2=p1->next;free(p1); //释放节点p1p1=p2;}free(p); //释放头节点}四：调试分析1：对所遇到问题的解决方法及分析1）建立二叉树时遇到问题：输入时未使用0来表明无左右孩子，导致递归无法结束，原因是为理解递归建立二叉树的过程。