数据结构（超详细讲解！！）第二十四节 二叉树（下）

1.遍历二叉树

 在二叉树的一些应用中，常常要求在树中查找具有某种特征的结点，或者对树中全部结点逐一进行某种处理。这就引入了遍历二叉树的问题，即如何按某条搜索路径访问树中的每一个结点，使得每一个结点仅且仅被访问一次。    

遍历二叉树：是指按照某种方法顺着某一条搜索路径寻访二叉树的结点，使得每个结点均被访问一次且仅被访问一次。

1.递归遍历

一棵二叉树由根结点、根结点的左子树和根结点的右子树3部分组成，因而只要依次遍历这3部分，就能遍历整棵二叉树。    

遍历的次序：假如以L、D、R分别表示遍历左子树、遍历根结点和遍历右子树，遍历整个二叉树则有DLR、LDR、LRD、DRL、RDL、RLD六种遍历方案。若规定先左后右，则只有前三种情况，分别规定为：      

DLR——先（根）序遍历，      

LDR——中（根）序遍历，      

LRD——后（根）序遍历。

1.先序遍历

先序遍历二叉树算法的框架是 ：若二叉树为空，遍历结束，否则： 访问根结点； 先序遍历根结点的左子树； 先序遍历根结点的右子树。

void  PreOrder(BiTree bt)	 /* bt为指向根结点的指针*/
{
	if (bt)		/*如果bt为空，结束*/
	{
		visit (bt ); 	  /*访问根结点*/
		PreOrder (bt -> lchild);  /*先序遍历左子树*/
		PreOrder (bt -> rchild);  /*先序遍历右子树*/
	}
}

2.中序遍历

中序遍历二叉树算法的框架是： 若二叉树为空，遍历结束，否则： 中序遍历根结点的左子树； 访问根结点； 中序遍历根结点的右子树。

void  InOrder(BiTree bt)/* bt为指向二叉树根结点的指针*/
{
	if (bt )		/*如果bt为空，结束*/
	{
		InOrder (bt -> lchild);	/*中序遍历左子树*/
		Visit (bt);	/*访问根结点*/
		InOrder (bt -> rchild);	/*中序遍历右子树*/
	}
}

3.后序遍历

后序遍历二叉树算法的框架是:若二叉树为空，遍历结束，否则 后序遍历根结点的左子树； 后序遍历根结点的右子树； 访问根结点。

void  PostOrder(BiTree bt)
/* bt为指向二叉树根结点的指针*/
{
	if (bt )		/*如果bt为空，结束*/
	{
		PostOrder (bt -> lchild);/*后序遍历左子树*/
		PostOrder (bt -> rchild);/*后序遍历右子树*/
		visit (bt );	/*访问根结点*/
	}
}

通过上述三种不同的遍历方式得到三种不同的线性序列，它们的共同的特点是有且仅有一个开始结点和一个终端结点，其余各结点都有且仅有一个前驱结点和一个后继结点。    

从二叉树的遍历定义可知，三种遍历算法的不同之处仅在于访问根结点和遍历左右子树的先后关系。如果在算法中隐去和递归无关的语句visit()，则三种遍历算法是完全相同的。遍历二叉树的算法中的基本操作是访问结点，显然，不论按那种方式进行遍历，对含n个结点的二叉树，其时间复杂度均为O(n)。所含辅助空间为遍历过程中占的最大容量，即树的深度。最坏的情况下为n，则空间复杂度也为O(n)。

4.层序遍历

 二叉树的层次遍历：是指从二叉树的第一层(根结点)开始，从上至下逐层遍历，在同一层中，按从左到右的顺序对结点逐个进行访问。

利用队列来实现    ：

算法思想：遍历从二叉树的根结点开始，首先将根结点入队列，然后执行下面的操作：       

1)取出队头元素；        

2) 访问该元素所指结点；        

3) 若该元素所指结点的左、右孩子结点非空，则将该元素所指结点的左孩子指针和右孩子指针入队。        

4）若队列非空，重复1）-3）；当队列为空时，二叉树的层次遍历结束。

void LevelOrder( BiTree bt) /*层次遍历二叉树bt算法*/
{	初始化队列Q；
	if ( bt == NULL )  	return;
	bt入队列Q;
	while( 队列Q不空){	
		p出队元素；
		Visit( p); /*访问出队结点*/
		if ( p->lchild) /*队首结点左孩子不空，入队*/
		       { 	p->lchild入队Q	}
		if (p->rchild)  /*队首结点右孩子不空，入队*/
		        { 	p->rchild入队Q		}
		}
}

5.练习

1.找出分别满足下面条件的所有二叉树（非空形态）：    

（a)前序序列和中序序列相同；      

(b)中序序列和后序序列相同；    

 (c)前序序列和后序序列相同；    

 (d)前序序列、中序序列和后序序列都相同。

2.已知一棵二叉树的中序序列和后序序列分别为BDCEAFHG和DECBHGFA，画出这棵二叉树。

结论：

1)  由二叉树的前序序列和中序序列可以唯一确定这棵二叉树。

2)  由二叉树的后序序列和中序序列可以唯一确定这棵二叉树。

3)  由二叉树的前序序列和后序序列不能唯一确定这棵二叉树。

2.非递归遍历

二叉树前序遍历的非递归算法的关键：在前序遍历过某结点的整个左子树后，如何找到该结点的右子树的根指针。

解决办法：在访问完该结点后，将该结点的指针保存在栈中，以便以后能通过它找到该结点的右子树。

1.先序遍历

先序算法执行轨迹

步骤：

1.栈s初始化；

2.循环直到root为空或栈s为空

2.1 当root不空时循环

2.1.1 输出root->data;（可将输出变为任何处理）    

2.1.2 将指针root的值保存到栈中；    

2.1.3 继续遍历root的左子树

2.2 如果栈s不空，则

2.2.1 将栈顶元素弹出至root；

2.2.2 准备遍历root的右子树；

//先序遍历
Void Firstorder（BiTree bt）
{	 p=bt；       /*根结点为当前结点*/
S=Initial( );  /*初始化栈*/
While(p||！Empty（S））  
{
While（p） /*当前结点不空*/
{  visit(p);  /*访问结点*/
Push（S，p); /*当前结点入栈*/
p=p->Lchild; /*左孩子作为当前结点*/

}
If(!Empty(S))  /*栈不空*/
{
p=pop(s);   /*出栈*/
p=p->Rchild; /*右孩子作为当前结点*/
}
}
}

2.中序遍历

//中序遍历
Void Inorder（BiTree bt）
{	 p=bt；       /*根结点为当前结点*/
S=Initial( );  /*初始化栈*/
While(p||！Empty（S））  
{
While（p） /*当前结点不空*/
{
Push（S，p); /*当前结点入栈*/
p=p->Lchild; /*左孩子作为当前结点*/

}
If(!Empty(S))  /*栈不空*/
{
p=pop(s);   /*出栈*/
Visit(p);   /*访问结点*/
p=p-Rchild; /*右孩子作为当前结点*/
}
}
}

3.后序遍历

typedef enum{L,R} tagtype;     /*定义枚举类型*/
typedef struct {
Bitree ptr;
tagtype tag;
}stacknode;                  /*定义栈结点类型*/ 
typedef struct{
stacknode Elem[maxsize];
int top;
}SqStack;                     /*定义顺序栈*/

void PostOrderUnrec(Bitree bt)   /*后序遍历算法*/
 {   p=bt;
     If(!p) return;     
do
{    while (p)        /*遍历左子树*/       
{
x.ptr = p;               
x.tag = L;           /*标记为左子树*/               
push(s,x);         /*入栈*/
p=p->lchild;      /*左孩子作为当前结点*/
}            
while (!StackEmpty(s) && s.Elem[s.top].tag==R) {     
x = pop(s);
p = x.ptr;
visite(p);         //tag为R，表示右子树访问完毕，故访问根结点               
}
 if (!StackEmpty(s)){                    
s.Elem[s.top].tag =R;             /*遍历右子树*/                    
p=s.Elem[s.top].ptr->rchild;   /*右孩子作为当前结点*/                      
}
}while (!StackEmpty(s));
}

4.练习

1.交换二叉树各结点的左、右子树(递归算法)

void  unknown ( BiTree   T )
 {
   BiTreeNode  *p = T,  *temp;
   if ( p != NULL ) 
    {
       temp = p->lchild; 
       p->lchild = p->rchild;
       p->rchild = temp;
       unknown ( p->lchild );
       unknown ( p->rchild );
    }
 }

2.不用栈消去递归算法中的第二个递归语句 （即消去尾递归）

void unknown ( BiTree T ) 
{
    BiTreeNode *p = T, *temp;
    while ( p != NULL ) 
     {
        temp = p->lchild; 
        p->lchild = p->rchild;
        p->rchild = temp;
       unknown ( p->lchild );
       p = p->rchild;
    }
 }

3.使用栈消去递归算法中的两个递归语句

void unknown ( BiTree  T ) 
{
  BiTreeNode  *p,  *temp，S[Max]; 
  int top=-1; 
  if ( T != NULL ) 
{
   top++;S[top]= T;
    while ( top>-1 )
      {
        p=S[top]; top--;    /*栈中退出一个结点*/
             temp = p->lchild;     /*交换子女*/
             p->lchild = p->rchild;
             p->rchild = temp;
  if ( p->rchild != NULL )
             top++;S[top]= p->rchild;
         if ( p->lchild != NULL )
             top++;S[top]= p->p->lchild;
      }
   } 
}

2.应用

1.设计算法输出二叉树的所有叶子结点的值。

基本思想：        

若二叉树为空树，则叶子数目为0。        

对于一棵非空二叉树，如果它的左子树和右子树都为空，那么此二叉树只有一个结点，就是叶子，此时叶子数目为1；否则，二叉树的叶子数目为左子树叶子数目和右子树叶子数目的总和。

int BitreeLeaf ( BiTree bt )
{
	if ( bt == NULL ) return 0 ;	/* 空树，叶子数为0 */
	if ( bt->lchild ==NULL&& bt->rchild == NULL)	
		return 1 ; /*只有一个根结点，叶子数为1*/
	return ( BitreeLeaf ( bt -> lchild ) + BitreeLeaf ( bt -> rchild )) ;
}

2.设计算法求二叉树的深度。

基本思想：      

若二叉树为空，约定二叉树的深度为0；      

对于一棵二叉树，如果它的左子树和右子树都为空，那么此二叉树只有一个根结点，此时二叉树的深度为1；否则，先求出其左、右子树的深度depthL和depthR，那么整棵二叉树的深度为1+max（depthL，depthR）。

int BitreeDepth ( BiTree bt )
{	int d = 0,depthL, depthR;  /*depthL和depthR分别为左、右子树的深度*/
	if ( bt == NULL ) return 0 ;		/*空树，深度为0 */
	if ( bt -> lchild ==NULL && bt -> rchild == NULL)				return 1;		/*叶子结点，深度为1 */
	depthL = BitreeDepth ( bt -> lchild ) ;	/*左子树深度 */
	depthR = BitreeDepth ( bt -> rchild ) ;	/*右子树深度 */
	d = max (depthL , depthR )	/*d为左右子树中较深者的深度*/
	return d+1 ; 	/* 整棵二叉树的深度为左、右子树中较深者的深度+1 */
}

3.创建二叉树

创建二叉树的方法有两种，一种是给定一棵二叉树的先序遍历序列和中序遍历序列创建二叉树，另一种是给定一棵二叉树的“扩展先序遍历序列”创建二叉树。

（1）结合先序遍历序列和中序遍历序列创建二叉树            

基本思想：

先序遍历的第一个结点一定是二叉树的根结点，而根据中序遍历规则，这个结点将同一棵二叉树的中序遍历序列分成了左、右两部分，左边部分是二叉树的根结点的左子树的中序遍历序列，右边部分是二叉树的根结点的右子树的中序遍历序列。根据这两个子序列，在先序序列中找到对应的子序列，左子序列的第一个结点为左子树的根结点，右子序列的第一个结点为右子树的根结点。对左右子树，再反复利用这个方法，最终根据先序序列和中序序列能唯一地确定出一棵二叉树。

（2）结合“扩展先序遍历序列”创建二叉树。    

扩展先序遍历序列：

就是先对原有二叉树用空子树进行扩展，使每个结点的左右子树（包括空子树）都存在，然后再对扩展后的二叉树进行先序遍历。遍历序列中用特定的符号表示空子树。

其扩展先序遍历序列为：

5 8 9 0 0 7 0 0 6 0 3 4 0 0 0    

其中“0”表示空子树。

BiTree CreateBiTree(char str[])
{	BiTree bt;
	static int i=0;
	char c = str[i++];
	if( c==‘.’ )	bt = NULL;/* 创建空树 */
 	else
	{	bt = (BiTree)malloc(sizeof(BiTreeNode)); 
   		bt->data = c; 	/* 创建根结点 */
	   	bt->lchild  = CreateBiTree(str); 
                            /* 创建左子树 */
	   	bt->rchild = CreateBiTree(str); 
                           /* 创建右子树 */
	}
	return bt;
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.mfbz.cn/a/181917.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

一条Update语句的执行过程是怎样的？

一条Update语句的执行过程是怎样的？

先看第一个问题，这里做个简单描述 ，因为我们着重还是看Update MySQL执行一条Select语句是怎么运行的？ 这个问题大家在面试的时候大家都背过类似的题，而且网上也有很多答案，这里分享一个大致流程介绍，关于…
阅读更多...
11.docker的网络-docker0的理解及bridge网桥模式的介绍与实例

11.docker的网络-docker0的理解及bridge网桥模式的介绍与实例

1.docker0的基本理解 安装完docker服务后，我们首先查看一下宿主机的网络配置 ifconfig我们可以看到，docker服务会默认在宿主机上创建一个虚拟网桥docker0，该网桥网络的名字称为docker0。它在内核层连通了其他物理或者虚拟网卡，这…
阅读更多...
camera-caps：Jetson设备上的一种实用的V4L2可视化界面

camera-caps：Jetson设备上的一种实用的V4L2可视化界面

camera-caps：Jetson设备上的一种实用的V4L2可视化界面 github地址是： https://github.com/jetsonhacks/camera-caps 注意：Jetpack5.x需要选择tag 5.x版本
阅读更多...
【element优化经验】怎么让element-ui中表单多语言切换排版不乱

【element优化经验】怎么让element-ui中表单多语言切换排版不乱

目录 前言： 痛点： 1.左对齐，右对齐在中文和外语情况下字数不同，固定宽度会使名称换行，不在整行对齐，影响美观。 2.如果名称和输入框不在一行，会使页面越来越长 3.label-width值给变量&#…
阅读更多...
fork介绍,返回值问题,写时拷贝,进程切换,子进程开始执行的位置,子进程的用途

fork介绍,返回值问题,写时拷贝,进程切换,子进程开始执行的位置,子进程的用途

目录 fork 介绍 fork的返回值问题 介绍 fork()时,系统要做什么 数据是否要独立 如果共享的话,就会出现问题! 写时拷贝 引入 介绍 举例(fork返回值) fork返回的值是什么 创建失败的原因 子进程执行位置从哪里开始 引入 进程切换 子进程执行的位置 子进程的…
阅读更多...
DAOS低时延与高性能RDMA网络

DAOS低时延与高性能RDMA网络

什么是RDMA RDMA（Remote Direct Memory Access）远程直接内存访问是一种技术，它使两台联网的计算机能够在主内存中交换数据，而无需依赖任何一台计算机的处理器、缓存或操作系统。与基于本地的直接内存访问 ( DMA ) 一样&#xff0c…
阅读更多...
超级武器！深入LoadRunner性能测试流程及极速分析结果！

超级武器！深入LoadRunner性能测试流程及极速分析结果！

性能测试目的 1 什么是性能测试? 性能测试是通过性能的测试工具模拟多种正常、峰值以及异常负载条件来对系统的各项性能指标进行测试。 负载测试和压力测试都属于性能测试，两者可以结合进行。通过负载测试，确定在各种工作负载下系统的性能&#xff0…
阅读更多...
Redis深入理解-Socket连接建立流程以及文件事件处理机制

Redis深入理解-Socket连接建立流程以及文件事件处理机制

Redis Server 运行原理图 Redis 服务器中 Socket 网络建立以及文件事件模型 一个 redis 单机，可以抗几百上千的并发，这里的并发指的就是同时可以有几百个 client 对这个 redis server 发起请求，都需要去建立网络连接，同时间可能会…
阅读更多...
Jmeter怎么实现接口关联？

Jmeter怎么实现接口关联？

用于接口测试时，后一个接口经常需要用到前一次接口返回的结果，应该如何获取前一次请求的结果值，应用于后一个接口呢，拿一个登录的例子来说明如何获取。 1、打开jmeter，新建一个测试计划，在测试计划里新建一…
阅读更多...
利用 docker 实现JMeter分布式压测

利用 docker 实现JMeter分布式压测

为什么需要分布式？ 在工作中经常需要对一些关键接口做高QPS的压测，JMeter是由Java 语言开发，没创建一个线程（虚拟用户），JVM默认会为每个线程分配1M的堆栈内存空间。受限于单台试压机的配置很难实现太高的并…
阅读更多...
量子计算概述

量子计算概述

目录 1.量子计算介绍 2.量子计算应用 3.量子计算研究机构 1.量子计算介绍 量子计算是一种遵循量子力学规律调控量子信息单元进行计算的新型计算模式。经典计算使用2进制进行运算，但2进制只有0和1两种状态，而量子计算除了包含0和1两种状…
阅读更多...
深入理解Spring AOP的工作流程

深入理解Spring AOP的工作流程

文章目录 引言什么是AOP？Spring AOP的工作原理1. JDK动态代理2. CGLIB代理 Spring AOP的注解方式Aspect注解EnableAspectJAutoProxy注解 Spring AOP的工作流程拓展应用1. 自定义注解2. 异常处理3. 切面优先级 结论 🎉深入理解Spring AOP的工作流程 ☆* o…
阅读更多...
相机和滤镜应用程序Nevercenter CameraBag Photo mac软件特点说明

相机和滤镜应用程序Nevercenter CameraBag Photo mac软件特点说明

Nevercenter CameraBag Photo mac是一款相机和滤镜应用程序，它提供了一系列先进的滤镜、调整工具和预设，可以帮助用户快速地优化和编辑照片。 Nevercenter CameraBag Photo mac软件特点 1. 滤镜：Nevercenter CameraBag Photo提供了超过200种…
阅读更多...
Harmony Ble蓝牙App（二）连接与发现服务

Harmony Ble蓝牙App（二）连接与发现服务

Ble蓝牙App（二）连接与发现服务 前言正文一、BlePeripheral回调二、连接和断连三、连接状态回调四、发现服务五、服务提供者六、显示服务七、源码 前言 在上一篇中我们进行扫描设备的处理，本文中进行连接和发现服务的数据处理，运行…
阅读更多...
多数据库使用django-apscheduler时，migrate后并不能生成django_apscheduler_djangojob表的问题

多数据库使用django-apscheduler时，migrate后并不能生成django_apscheduler_djangojob表的问题

先说一下django-apscheduler定时器的使用过程： django-apscheduler基本使用 1.安装django-apscheduler代码如下（示例）： pip install django-apscheduler 2.配置settings.py的INSTALLED_APPS代码如下（示例&#xff09…
阅读更多...
性能测试必备知识-使用MySQL存储过程构造大量数据：实例解析

性能测试必备知识-使用MySQL存储过程构造大量数据：实例解析

在软件开发过程中，测试是一个不可或缺的环节。通过测试，我们可以发现并修复软件中的各种问题，提高软件的质量和稳定性。然而，手动编写大量的测试用例是一项耗时且容易出错的任务。为了解决这个问题，我们需要学会使用批…
阅读更多...
ES ElasticSearch安装、可视化工具kibana安装

ES ElasticSearch安装、可视化工具kibana安装

1、安装ES docker run -d --name es9200 -e "discovery.typesingle-node" -p 9200:9200 elasticsearch:7.12.1访问测试： http://域名:9200/ 2、安装kibana对es进行可视化操作 执行命令 docker run -d --name kibana5601 -p 5601:5601 kibana:7.1.12.修…
阅读更多...
在线工具收集

在线工具收集

在线工具收集 1、在线P图 https://www.photopea.com/ 一款类似于PS的在线抠图软件 ①去除图片中的文字，并填充背景色 第一步：使用矩形选中要清除的文字 第二步：点击编辑选择填充 第三步：选择内容识别，保留透明区域…
阅读更多...
[MySQL] MySQL 表的增删查改

[MySQL] MySQL 表的增删查改

本篇文章对mysql表的增删查改进行了详细的举例说明解释。对表的增删查改简称CRUD : Create(创建), Retrieve(读取)，Update(更新)，Delete（删除）。其中重点是对查询select语句进行了详细解释，并且通过多个实际例子来帮助…
阅读更多...
物联网AI MicroPython学习之语法 I2S音频总线接口

物联网AI MicroPython学习之语法 I2S音频总线接口

学物联网，来万物简单IoT物联网！！ I2S 介绍 模块功能: I2S音频总线驱动模块 接口说明 I2S - 构建I2S对象 函数原型：I2S(id, sck, ws, sd, mode, bits, format, rate, ibuf)参数说明： 参数类型必选参数&#xff1f…
阅读更多...
最新文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发 尧图建网站