首页 > 其他分享 >数据结构(五)——二叉树的遍历和线索二叉树

数据结构(五)——二叉树的遍历和线索二叉树

时间:2024-03-23 21:30:39浏览次数:28  
标签:pre 结点 遍历 NULL 二叉树 数据结构 线索

5.3. 二叉树的遍历和线索二叉树

5.3.1_1 二叉树的先中后序遍历

遍历:按照某种次序把所有结点都访问一遍

二叉树的递归特性:
        ①要么是个空二叉树
        ②要么就是由“根节点+左子树+右子树”组成的二叉树

先序遍历:根左右(NLR)
中序遍历:左根右(LNR)
后序遍历:左右根(LRN)


先序遍历(PreOrder)的操作过程如下:
1. 若二叉树为空,则什么也不做;
2. 若二叉树非空:
        ①访问根结点;
        ②先序遍历左子树;
        ③先序遍历右子树。
代码实现如下:

typedef struct BiTNode{  
    ElemType data;  
    struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;

// 先序遍历
void PreOrder(BiTree T){  
    if(T!=NULL){     
        visit(T);                 //访问根结点        
        PreOrder(T->lchild);      //递归遍历左子树 
        PreOrder(T->rchild);      //递归遍历右子树
    }
}

先序遍历—第一次路过时访问结点,图示如下

中序遍历(InOrder)的操作过程如下:
1. 若二叉树为空,则什么也不做;
2. 若二叉树非空:
        ①中序遍历左子树;
        ②访问根结点;
        ③中序遍历右子树;
代码实现如下: 

typedef struct BiTNode{  
    ElemType data;  
    struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;

// 中序遍历
void PreOrder(BiTree T){  
    if(T!=NULL){     
        PreOrder(T->lchild);      //递归遍历左子树 
        visit(T);                 //访问根结点        
        PreOrder(T->rchild);      //递归遍历右子树
    }
}

中序遍历—第二次路过时访问结点,图示如下

后序遍历(InOrder)的操作过程如下:
1. 若二叉树为空,则什么也不做;
2. 若二叉树非空:
        ①后序遍历左子树;
        ②后序遍历右子树;
        ③访问根结点。
代码实现如下:

typedef struct BiTNode{  
    ElemType data;  
    struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;

// 后序遍历
void PreOrder(BiTree T){  
    if(T!=NULL){     
        PreOrder(T->lchild);      //递归遍历左子树 
        PreOrder(T->rchild);      //递归遍历右子树
        visit(T);                 //访问根结点        
    }
}

后序遍历—第三次路过时访问结点 ,图示如下

// 应用:求树的深度
int treeDepth(BiTree T){  
    if(T == NULL){  
        return 0;  
    }else{      
        int l = treeDepth(T->lchild); 
        int r = treeDepth(T->rchild); 
        //树的深度=Max(左子树深度,右子树深度)+1
        return l>r ? l+1 r+1;  
    }
}

5.3.1_2 二叉树的层次遍历


算法思想:
①初始化一个辅助队列
②根结点入队
③若队列非空,则队头结点出队,访问该结点,并将其左、右孩子插入队尾(如果有的话)
④重复③直至队列为空
代码实现:

// 二叉树结点(链式存储)
typedef struct BiTNode{  
    char data;   
    struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;

// 链式队列结点
typedef struct LinkNode{ 
    BiTNode *data;             //存结点的指针而不是结点本身
    struct LinkNode *next;
}LinkNode;

typedef struct{ 
    LinkNode *front, *rear;    //队头队尾
}LinkQueue;

// 层序遍历
void LevelOrder(BiTree T){  
    LinkQueue Q; 
    InitQueue(Q);              //初始化辅助队列
    BiTree p;
    EnQueue(Q, T);             //将根结点入队
    while(!IsEmpty(Q)){        //队列不空则循环
        DeQueue(Q, p);         //队头结点出队
        visit(p);              //访问出队结点
        if(p->lchild!=NULL)      
            EnQueue(Q, p->lchild);     //左孩子入队
        if(p->rchild!=NULL)    
            EnQueue(Q, p->rchild);     //右孩子入队
    }
}

5.3.1_3 由遍历序列构造二叉树

若只给出一棵二叉树的 前/中/后/层 序遍历序列中的一种,不能唯一确定一棵二叉树
一种遍历序列可能对应多种形态



前序 + 中序遍历序列

由前序遍历可推出根节点在中序遍历中的位置,从而确定左右结点,再依此类推

后序 + 中序遍历序列

由后序遍历可推出根结点在中序遍历中的位置,从而确定左右结点在中序遍历的位置

层序 + 中序遍历序列

由层序遍历可推出根结点,再根据根节点进一步确定左右的根的位置

5.3.2_1 线索二叉树的概念

普通二叉树进行遍历时,找前驱、后继很不方便,且每次都要从根结点出发,无法从一个指定的结点开始遍历​​​​​​​​​​​​​​。

n 个结点的二叉树,有 n+1 个空链域,可用来记录前驱、后继的信息。
指向前驱、后继的指针被称为“线索”,形成的二叉树就称为线索二叉树。



线索二叉树的存储

线索二叉树的结点在原本二叉树的基础上,新增了左右线索标志 tag。
tag == 0 时,表示指针指向孩子;tag == 1 时,表示指针是“线索”。

// 线索二叉树的结点
typedef struct ThreadNode{ 
    ElemType data;   
    struct ThreadNode *lchild, *rchild; 
    int ltag, rtag;	//左、右线索标志
}ThreadNode,*ThreadTree;

中序线索二叉树的存储

先序线索二叉树



5.3.2_2 二叉树的线索化

中序线索化

//线索二叉树结点
typedef struct ThreadNode{
    ElemType data;  
    struct ThreadNode *lchild, *rchild;   
    int ltag, rtag;            //左、右线索标志
}ThreadNode, *ThreadTree;

// 中序遍历二叉树,一边遍历一边线索化
void InThread(ThreadTree T) {
	if (T != NULL) {
		InThread(p->lchild);    //中序遍历左子树
		visit(T);               //访问根结点
		InThread(p->rchild);    //中序遍历右子树
	}
}

void visit(ThreadNode *q) {
    if(q->lchild==NULL){        //左子树为空,建立前驱线索
        q->lchild=pre;          //
        q->ltag=1;              //修改ltag=1,只有变成1才表示指针是线索
    }
    if(pre!=NULL&&pre->rchild==NULL){
        pre->rchild=q;          //建立前驱结点的后继线索
        pre->rtag=1;
    }
    pre=q;
}

//全局变量pre,指向当前访问结点的前驱
ThreadNode *pre=NULL;           //pre没有前驱,最开始指向NULL


// 中序化线索二叉树T
void CreateInThread(ThreadTree T) {
    pre = NULL;                //pre初始化为NULL
	if (T != NULL) {           //非空二叉树才能线索化
		InThread(T, pre);      //中序化线索二叉树
		if(pre->rchild = NULL)
		    pre->rtag = 1;     //处理遍历的最后一个结点
	}
}

先序线索化 

// 先序遍历二叉树T
void PreThread(ThreadTree T) {
	if (T != NULL) {           //非空二叉树才能线索化
        visit(T);              //先处理根结点
		if(T->ltag ==0)        //lchild不是前驱线索
            PreThread(T->child);
        PreThread(T->child);
  	}
}


void visit(ThreadNode *q) {
    if(q->lchild==NULL){        //左子树为空,建立前驱线索
        q->lchild=pre;          //
        q->ltag=1;              //修改ltag=1,只有变成1才表示指针是线索
    }
    if(pre!=NULL&&pre->rchild==NULL){
        pre->rchild=q;          //建立前驱结点的后继线索
        pre->rtag=1;
    }
    pre=q;
}

//全局变量pre,指向当前访问结点的前驱
ThreadNode *pre=NULL;           //pre没有前驱,最开始指向NULL

void CreateInThread(ThreadTree T) {
    pre = NULL;                //pre初始化为NULL
	if (T != NULL) {           //非空二叉树才能线索化
		PreThread(T);          //先序化线索二叉树
		if(pre->rchild = NULL)
		    pre->rtag = 1;     //处理遍历的最后一个结点
	}
}

后序线索化 

// 后序遍历二叉树T
void PostThread(ThreadTree T) {
	if (T != NULL) {           //非空二叉树才能线索化
		PreThread(T->child);   //后序遍历左子树
        PreThread(T->child);   //后序遍历右子树
        visit(T);              //访问根结点
  	}
}


void visit(ThreadNode *q) {
    if(q->lchild==NULL){        //左子树为空,建立前驱线索
        q->lchild=pre;          //
        q->ltag=1;              //修改ltag=1,只有变成1才表示指针是线索
    }
    if(pre!=NULL&&pre->rchild==NULL){
        pre->rchild=q;          //建立前驱结点的后继线索
        pre->rtag=1;
    }
    pre=q;
}

//全局变量pre,指向当前访问结点的前驱
ThreadNode *pre=NULL;           //pre没有前驱,最开始指向NULL

//后续线索化二叉树T
void CreateInThread(ThreadTree T) {
    pre = NULL;                //pre初始化为NULL
	if (T != NULL) {           //非空二叉树才能线索化
		PostThread(T);          //后续线索化二叉树
		if(pre->rchild = NULL)
		    pre->rtag = 1;     //处理遍历的最后一个结点
	}
}

5.3.2_3 在线索二叉树中找前驱后继

在中序线索二叉树中找到指定结点*p 的中序后继 next  
①若 p->rtag==1,则 next = p->rchild
②若 p->rtag==0,则 next = p 的右子树中最左下结点

// 找到以p为根的子树中,第一个被中序遍历的结点
ThreadNode *FirstNode(ThreadNode *p){
    // 循环找到最左下结点(不一定是叶结点)
    while(p->ltag==0)
        p=p->rchild;
    return p;
}

// 在中序线索二叉树中找到结点p的后继结点
ThreadNode *NextNode(ThreadNode *p){
    // 右子树中最左下的结点
    if(p->rtag==0)
        return FirstNode(p->lchild);
    else
        return p->rchild;    //rtage==1直接返回后继线索
}

// 对中序线索二叉树进行中序循环(利用线索实现的非递归方法) 空间复杂度O(1)
void InOrder(ThreadNode *T){
    for(ThreadNode *p=FirstNode(T); p!=NULL; p=NextNode(p))
        visit(p);
}

在中序线索二叉树中找到指定结点*p 的中序前驱 pre
①若 p->ltag==1,则 pre = p->lchild
②若 p->ltag==0

// 找到以p为根的子树中,最后一个被中序遍历的结点
ThreadNode *LastNode(ThreadNode *p){
    // 循环找到最右下结点(不一定是叶结点)
    while(p->rtag==0)
        p=p->rchild;
    return p;
}

// 在中序线索二叉树中找到结点p的前驱结点
ThreadNode *PreNode(ThreadNode *p){
    // 左子树中最右下的结点
    if(p->ltag==0)
        return LastNode(p->lchild);
    else
        return p->lchild;        //ltage==1直接返回前驱线索
}

// 对中序线索二叉树进行中序循环(非递归方法实现)
void RevOrder(ThreadNode *T){
    for(ThreadNode *p=LastNode(T); p!=NULL; p=PreNode(p))
        visit(p);
}

在先序线索二叉树中找到指定结点*p 的先序后继 next
①若 p->rtag==1,则 next = p->rchild
②若 p->rtag==0

在先序线索二叉树中找到指定结点*p 的先序前驱 pre
①若 p->ltag==1,则 next = p->lchild
②若 p->ltag==0

在后序线索二叉树中找到指定结点*p 的后序前驱 pre
①若 p->ltag==1,则 pre = p->lchild
②若 p->ltag==0

在后序线索二叉树中找到指定结点*p 的后序后继 next
①若 p->rtag==1,则 next = p->rchild
②若 p->rtag==0

​​​​​​​

标签:pre,结点,遍历,NULL,二叉树,数据结构,线索
From: https://blog.csdn.net/a_rain2333/article/details/136922678

相关文章

  • 《数据结构与算法分析》作业一(详解版)
    1.什么是数据结构?有关数据结构的讨论涉及哪三个方面?答:(1)数据结构是指相互之间存在着一种或多种关系的数据元素的集合和该集合中数据元素之间的关系组成.(2)逻辑结构、存储结构以及运算结构。2.什么是算法?算法的特性有哪些?根据这些特性,解释算法与程序的区别?答:(1)算法是一组明......
  • leedcode-二叉树的所有路径
    迭代法-深度优先搜索classSolution:defbinaryTreePaths(self,root:Optional[TreeNode])->List[str]:ifnotroot:return[]#如果根节点为空,直接返回空列表stack=[(root,str(root.val))]#初始化栈,栈中存储的是节点......
  • 一道平衡二叉树的求解
    最近在看二叉树的算法,我觉得有点迷迷糊糊,就是那种一看就会,一写就费。我有点很奇怪的感觉,就感觉二叉树的很多问题,其实在于一步一步的遍历(或者称为迭代,或者是递归方法),然后在遍历的基础上进行逻辑(业务)操作。首先在这讲一下递归。递归有三部曲:一.确定函数参数,确定函数的返回值......
  • python 内置数据结构-数值型
    内置数值型数据结构int整数(int):在Python中,整数是没有小数部分的数字。整数可以是正数、负数或零。Python中的整数没有大小限制,取决于内存区域的大小,可以表示任意大小的整数。x=10y=-5z=0print(x,y,z)#输出:10-50float浮点数(float):浮点数是带有小数......
  • 二维矩阵螺旋遍历
    //3.螺旋矩阵//例如n=4//要求:打印出螺旋矩阵,求i行j列的数字,0<n<10000//算法思想:只要找出每一层的第一个数即可,第一个数值为上一层的第一个数+4*n+4,循//环时n每次减2//+-------------------------->X轴//|1234//1213145//|1116156//|10......
  • 可持久化数据结构
    前言可持久化数据结构是一些很厉害的东西,大家可以去看lxl的课件和她在WC2024上的讲课,由于能力限制,这个博客会讲得比较基础。这里应该有个题单。根据lxl的课件,我们可以把其分为几类:部分可持久化:允许访问历史版本,不能修改历史版本完全可持久化:允许把目前版本替换为历史......
  • java数据结构与算法基础-----排序------堆排序
    java数据结构与算法刷题目录(剑指Offer、LeetCode、ACM)-----主目录-----持续更新(进不去说明我没写完):https://blog.csdn.net/grd_java/article/details/123063846文章目录堆排序是利用堆(数据结构)设计的排序算法,属于选择排序,最坏,最好,平均时间复杂度均为O(nlogn),不稳......
  • 数据结构(九)模拟堆---以题为例
    维护一个集合,初始时集合为空,支持如下几种操作:Ix,插入一个数 x;PM,输出当前集合中的最小值;DM,删除当前集合中的最小值(数据保证此时的最小值唯一);Dk,删除第 k 个插入的数;Ckx,修改第 k 个插入的数,将其变为 x;现在要进行 N 次操作,对于所有第 2 个操作,输出当前集合的最小......
  • 数据结构:详解【栈和队列】的实现
    目录1.栈1.1栈的概念及结构1.2栈的实现1.3栈的功能1.4栈的功能的实现1.5完整代码2.队列2.1队列的概念及结构2.2队列的实现2.3队列的功能2.4队列的功能的实现2.5完整代码1.栈1.1栈的概念及结构栈:一种特殊的线性表,其只允许在固定的一端进行插入和删除......
  • 数据结构笔记
    数据结构数据在内存中的存储方式(存储结构)程序=数据+算法算法=操作的步骤算法的时间复杂度动态数组链表迭代器栈和队列二叉搜索树二叉平衡树哈希表1.时间复杂度考量算法的时间复杂度有一个前提就是控制变量,语句的执行时间相同,数据的样本量相同……......