首页 > 其他分享 >【遍历二叉树】---先，中，后，层序遍历 及 先序建立整树

【遍历二叉树】---先，中，后，层序遍历 及 先序建立整树

时间：2024-09-13 22:52:20浏览次数：13  
标签：结点 遍历 层序 先序 序列 指针 二叉树

0.二叉树结点的链式存储结构

#include<stdio.h>
#include<stdlib.h>

typedef char TElemType;//树中元素基本类型为char类型

#define bool int
#define true 1
#define false 0

//二叉树结点链式存储结构（二叉链表）
typedef struct BiNode
{
	TElemType data;//数据域
	struct BiNode* lchild, * rchild;//左，右孩子指针
}BiNode,*BiTree;
//BiNode：用来定义结点类型
//BiTree：用来定义树类型

1.遍历的相关特性

  • 遍历定义------- 顺着某一条搜索路径巡访二叉树中的结点，使得每个结点均被访问一次，而且仅被访问一次(又称周游)。
  • “访问”：可以是对结点作各种处理，如:输出结点的信息、修改结点的数据值等，但要求这种访问不破坏原来的数据结构。
  • 遍历目的：得到树中所有结点的一个线性排列。
  • 遍历用途：它是树结构插入、删除、修改、查找和排序运算的前提，是二叉树一切运算的基础和核心。

2.遍历方法

2.1方法概览

在这里插入图片描述
假设：

  • L:遍历左子树
  • D:访问根结点
  • R:遍历右子树
  • 则遍历整个二叉树的方案共有6种：

在这里插入图片描述

  • 若规定先左后右，则只有前三种情况：

在这里插入图片描述

  • 算法描述如下：
    在这里插入图片描述
    由二叉树的递归定义可知，遍历左子树和遍历右子树可如同遍历二又树一样“递归”进行。

2.2先序遍历二叉树----DLR

2.2.1方法详解：根左右

在这里插入图片描述
核心：子树为空时，结束操作；子树不为空，重复先序遍历的过程遍历子树

2.2.2手写遍历顺序实例分析：

  • （1）较简单的例子
    在这里插入图片描述
  • （2）较复杂的例子
    在这里插入图片描述

在这里插入图片描述

2.2.3先序递归遍历算法

  • 简单示例的分析：
    在这里插入图片描述
    在这里插入图片描述
  • 实例在程序中运行的过程
    在这里插入图片描述
  • 算法步骤：
    注意：传入指向根结点的一级指针，因为遍历并不改变数据结构
bool PreOrderTraverse(BiTree T)

（1）返回条件：子树为空，则返回true;
（2）访问根结点
（3）递归遍历左子树
（4）递归遍历右子树

//1.先序遍历二叉树(根左右)
//注意：传入指向根结点的一级指针，因为遍历并不改变数据结构
bool PreOrderTraverse(BiTree T)
{
	//[1]返回条件：子树为空，则返回true;
	if (T == NULL)
	return true;

	//[2]访问根结点
	printf("%c", T->data);

	//[3]递归遍历左子树
	PreOrderTraverse(T->lchild);

	//[4]递归遍历右子树
	PreOrderTraverse(T->rchild);
}

2.3中序遍历二叉树----LDR

2.3.1方法详解：左根右

在这里插入图片描述

2.3.2手写遍历顺序实例分析：

  • （1）较简单的例子
    在这里插入图片描述

  • （2）较复杂的例子
    在这里插入图片描述
    在这里插入图片描述

2.3.3中序递归遍历算法

  • 简单示例的分析：
    在这里插入图片描述
    在这里插入图片描述
  • 算法步骤：
bool InOrderTraverse(BiTree T)

注意：传入指向根结点的一级指针，因为遍历并不改变数据结构

（1）返回条件：子树为空，则返回true;;
（2）递归遍历左子树
（3）访问根结点
（4）递归遍历右子树

//2.中序遍历二叉树(左根右)
//注意：传入指向根结点的一级指针，因为遍历并不改变数据结构
bool InOrderTraverse(BiTree T)
{
	//[1]返回条件：子树为空，则返回true;
	if (T == NULL)
	return true;

	//[2]递归遍历左子树
	InOrderTraverse(T->lchild);

	//[3]访问根结点
	printf("%c", T->data);

	
	//[4]递归遍历右子树
	InOrderTraverse(T->rchild);
}

2.4后序遍历二叉树----LRD

2.4.1方法详解：左右根

在这里插入图片描述

2.4.2手写遍历顺序实例分析：

  • （1）较简单的例子
    在这里插入图片描述

  • （2）较复杂的例子
    在这里插入图片描述
    在这里插入图片描述

2.3.3后序递归遍历算法

  • 简单示例的分析：
    在这里插入图片描述

在这里插入图片描述

  • 算法步骤：
bool PostOrderTraverse(BiTree T)

注意：传入指向根结点的一级指针，因为遍历并不改变数据结构

（1）返回条件：子树为空，则返回true;;
（2）递归遍历左子树
（3）递归遍历右子树
（4）访问根结点

//3.后序遍历二叉树(左右根)
//注意：传入指向根结点的一级指针，因为遍历并不改变数据结构
bool PostOrderTraverse(BiTree T)
{
	//[1]返回条件：子树为空，则返回true;
	if (T == NULL)
		return true;

	//[2]递归遍历左子树
	PostOrderTraverse(T->lchild);

	//[3]递归遍历右子树
	PostOrderTraverse(T->rchild);

	//[4]访问根结点
	printf("%c", T->data);
}

2.5运算式树的实例：

在这里插入图片描述

可以自己练习一下

2.6遍历算法的分析

  • （1）如果去掉输出语句，从递归的角度看，三种算法是完全相同的，或说这三种算法的访问路径是相同的，只是访问结点的时机不同。
    在这里插入图片描述
    在这里插入图片描述
  • （2）算法的效率分析
  • 时间效率: O(n) 每个结点只访问一次
  • 空间效率: O(n) 栈占用的最大辅助空间

2.7由遍历序列确定二叉树（核心先后定根，中分左右）

2.7.1遍历二叉树的特点

  • 若二叉树中各结点的值均不相同，则二叉树结点的先序序列、中序序列、后序序列都是唯一的。
  • 由二叉树的先序序列和中序序列，或由二叉树的后序序列和中序序列可以确定唯一一棵二叉树

2.7.2已知先序和中序序列求二叉树

在这里插入图片描述
回顾先序特点：根左右
回顾中序特点：左根右
实例分析：
在这里插入图片描述
（1）

  • 先序根左右，故A为根
  • 中序左根右，故CDBFE为左子树；---------------IHGJ为右子树
    ------即先序中的BCDEF序列---------即先序中的GHIJ序列
    在这里插入图片描述

（2）

  • 先序根左右，故左子树中B为根;右子树中G为根
  • 中序左根右，
    -B为根:---- CD为左子树；---------------FE为右子树
    即先序中的CD序列---------即先序中的EF序列
  • G为根:------IH为左子树；---------------J为右子树
    即先序中的HI序列---------即先序中的J序列
    在这里插入图片描述
    (3)
  • 先序根左右，故左子树中C为根,E为根;右子树中H为根,J为叶子结点
  • 中序左根右，
    -C为根:---- D为右子树
    由中序中的CD序列根右得到
  • E为根:------F为左子树
    由中序中的FE序列左根得到
  • H为根:------I为左子树
    由中序中的IH序列左根得到

在这里插入图片描述
通过以上三步得到对应的二叉树

2.6.3已知后序和中序序列求二叉树

在这里插入图片描述
在这里插入图片描述

（1）

  • 后序左右根，故A为根
  • 中序左根右，故BDCE为左子树；---------------FHG为右子树
    ------即后序中的DECB序列---------即先序中的HGF序列
    在这里插入图片描述

（2）

  • 后序左右根，故左子树中B为根;右子树中F为根
  • 中序左根右，
  • B为根:----------------DCE为右子树
    ----------即后序中的DEC序列
  • F为根:---------------HG为右子树
    ---------即后序中的HG序列
    在这里插入图片描述

(3)

  • 后序左右根，故左子树中C为根;右子树中G为根
  • 中序左根右，
  • C为根:---- D为左叶子结点，E为右叶子节点
    由中序中的DCE序列左根右得到
  • G为根:------H为左叶子结点
    由中序中的HG序列左根得到
    在这里插入图片描述

2.7层序遍历二叉树----（从上往下，从左往右，逐层遍历）

2.7.1遍历特点

对于一颗二叉树，从根结点开始，按从上到下、从左到右的顺序访问每一个结点 且 每一个结点仅仅访问一次。
比如：
在这里插入图片描述
这颗二叉树的层序遍历结果为 abfcdgeh

2.7.2算法的设计思路

在这里插入图片描述
依旧是上述图例，分析此算法的执行过程：

  • （1）根结点指针入队
    在这里插入图片描述
  • （2）根结点指针出队，入队根结点的左右孩子指针bf
    在这里插入图片描述
    在这里插入图片描述
  • （3）b结点指针出队，入队b结点的左右孩子指针cd
    在这里插入图片描述
    在这里插入图片描述
  • （4）f结点指针出队，入队f结点的左孩子指针g,其右孩子指针不存在
    在这里插入图片描述
    在这里插入图片描述
  • （5）c结点指针出队，c结点的左右孩子指针不存在
    在这里插入图片描述
    在这里插入图片描述
  • （6）d结点指针出队，入队d结点的左孩子指针g,其右孩子指针不存在
    在这里插入图片描述
    在这里插入图片描述
  • （7）e结点指针出队，入队d结点的右孩子指针,其右孩子指针不存在

在这里插入图片描述
在这里插入图片描述

  • （8）h结点指针出队，h结点的左右孩子指针不存在
    在这里插入图片描述
    在这里插入图片描述
  • （9）此时队列为空，层序遍历结束
bool LevelOrder(BiNode* b)

注意：传入二叉树的根结点指针

//{4} 二叉树的层序遍历
// 注意：传入二叉树的根结点指针
bool LevelOrder(BiNode* b)
{
	//[1]创建并初始化一个队列
	queue qu;
	Initqueue(&qu);

	//[2]将根结点指针入队
	Enqueue(&qu, b);

	//[3]队不空时循环
	while (!queueEmpty(&qu))
	{
		//<1>从队列中出列一个结点*e，访问并输出它
		ElemType e;//这里的的e是用来接收队头元素的
		//队列中所有元素都是指向树结点的指针
		Dequeue(&qu, &e);
		printf("%c", e->data); // 输出当前结点的值
	    
	    //<2>若它有左孩子结点，将左孩子结点进队:
		if (e->lchild != NULL)
		{
			Enqueue(&qu, e->lchild);
		}

		//<3>若它有右孩子结点，将右孩子结点进队。
		if (e->rchild != NULL)
		{
			Enqueue(&qu, e->rchild);
		}
	}
	return true;
}

完整代码即实现如下：

//用循环顺序队列实现二叉树的层序遍历
#include <stdio.h>
#include <stdlib.h>
#include<stdbool.h>
//{1}先实现循环顺序队列的构造
//(少用一个空间)
#define MAXSIZE 100//队列最大容量


//----------------------------------------------------------
typedef char TElemType;//二叉树中的结点存储char类型的数据

//{2}二叉树的结构实现
typedef struct BiNode
{
	TElemType data;//数据域
	struct BiNode* lchild, * rchild;//左，右孩子指针
}BiNode, * BiTree;
//-----------------------------------------------------------

typedef BiTree ElemType;//构造出来的队列用来存储指向树结点的指针

typedef struct queue
{
	ElemType* data;
	int front;
	int rear;
}queue;

//[1]初始化队列
bool Initqueue(queue *q)
{
	q->data =(ElemType*)malloc(sizeof(ElemType) * MAXSIZE);

	if (!q)
	{
		return false;
	}

	q->front = q->rear = 0;
	return true;
}


//[2]入队操作
bool Enqueue(queue* q,ElemType e)
{
	if ((q->rear + 1) % MAXSIZE == q->front)
	{
		return false;//队满
	}

	q->data[q->rear] = e;
	q->rear = (q->rear + 1) % MAXSIZE;
	return true;
}


//[3]出队操作
bool Dequeue(queue* q, ElemType* e)
{
	if (q->rear == q->front)
	{
		return false;//队空
	}

	*e = q->data[q->front];

	q->front = (q->front + 1) % MAXSIZE;
	return true;
}

//[4]判断队空
bool queueEmpty(queue* q)
{
	if (q->front == q->rear)
	{
		return true;
	}
	return false;
}





//{3}先序创建二叉树
bool CreateBiTree(BiTree* T)
{
	//[1]定义临时变量ch，用来存储每次输入的字符
	TElemType ch;
	scanf_s("%c", &ch);

	//[2]若输入为#，则建立空结点，并返回
	if (ch == '#')
	{
		(*T) = NULL;
	}
	//易错点1：输入空结点时，(*T) = NULL操作之后 应直接返回上一层，故if-else 语句块不能省略

	//[2]否则创建结点，并按先序遍历序列递归建立其左右孩子结点
	else
	{
		//<1>开辟子根结点空间(第一个结点为根结点)
		(*T) = (BiNode*)malloc(sizeof(BiNode));

		if (!(*T))
		{
			printf("内存分配失败！\n");
			exit(-1);//程序错误，退出程序
		}

		//<2>将当前字符 存入 当前根结点
		(*T)->data = ch;
		//<3>构造左子树
		CreateBiTree(&((*T)->lchild));
		//<4>构造右子树
		CreateBiTree(&((*T)->rchild));
		//易错点2：传入的应该是 左右孩子指针的地址，而不是 左右孩子指针本身。因为要修改左右孩子指针的值（指向创建的新结点）

	}
	return true;
}



//{4} 二叉树的层序遍历
// 注意：传入二叉树的根结点指针
bool LevelOrder(BiNode* b)
{
	//[1]创建并初始化一个队列
	queue qu;
	Initqueue(&qu);

	//[2]将根结点指针入队
	Enqueue(&qu, b);

	//[3]队不空时循环
	while (!queueEmpty(&qu))
	{
		//<1>从队列中出列一个结点指针（e），访问并输出它指向的树结点的值
		ElemType e;
		Dequeue(&qu, &e);
		printf("%c", e->data); // 输出当前结点的值
	    
	    //<2>若它有左孩子结点，将左孩子结点进队:
		if (e->lchild != NULL)
		{
			Enqueue(&qu, e->lchild);
		}

		//<3>若它有右孩子结点，将右孩子结点进队。
		if (e->rchild != NULL)
		{
			Enqueue(&qu, e->rchild);
		}
	}
	return true;
}





int main()
{
	BiTree T;
	CreateBiTree(&T);
	printf("层序遍历序列如下：");
	LevelOrder(T);
	printf("\n");
	return 0;
	return 0;
}

在这里插入图片描述
以模拟队列的二叉树实例为例：
先序建立二叉树应输入：abc##de###fg#h###
层序遍历二叉树的结果应为：abfcdgeh

2.8先序建立二叉树

按先序遍历序列建立二叉树的二叉链表(DRL)

2.8.1算法思路

  • （1）从键盘输入二叉树的结点信息，建立二又树的存储结构
  • （2）在建立二叉树的过程中按照二叉树先序方式建立

2.8.2二叉树序列的正确建立

  • （1）我们知道，对于一颗二叉树，我们至少要知道两个序列：
    前序和中序 或者 后序和中序，才能确定唯一的二叉树
    在这里插入图片描述
    显然这个先序序列的二叉树是不唯一的，如下图：
    在这里插入图片描述
    在这里插入图片描述
    那为了建立一颗唯一的二叉树，我们应该怎么办呢？
    方法就是：从二叉树中每个结点的空指针中引出一个虚结点，
    这里我们使用“#”来表示
    如下图：
    在这里插入图片描述
    在这里插入图片描述
    此时根据补充出来的虚结点的不同，这样两颗二叉树的序列就完全不一样了

  • （2）所以对于下图这样的二叉树，在先序建立二叉树时，用户应输入的序列是：

在这里插入图片描述

在这里插入图片描述
分析如下：
在这里插入图片描述

2.8.3实例建立过程详解

在这里插入图片描述

（1）输入A,不是#，建立根结点
在这里插入图片描述
(2)通过左孩子指针，输入B,不是#，建立根结点
在这里插入图片描述
(3)通过左孩子指针，输入C,不是#，建立根结点
在这里插入图片描述
(4)(5)
通过左孩子指针，输入#,返回上一层
通过右孩子指针，输入#,返回上一层
在这里插入图片描述
(6)刚才返回到第二层，通过右孩子指针，输入D,不是#，建立根结点
在这里插入图片描述
(7)通过左孩子指针，输入E,不是#，建立根结点
在这里插入图片描述
(8)(9)(10)(11)
通过左孩子指针，输入#,返回上一层
通过右孩子指针，输入G,不是#，建立根结点
通过左孩子指针，输入#,返回上一层
通过右孩子指针，输入#,返回上一层(此时回到了第四层)

返回第三层
在这里插入图片描述
(12)(13)（14）
通过右孩子指针，输入F,不是#，建立根结点
通过左孩子指针，输入#,返回上一层
通过右孩子指针，输入#,返回上一层（此时回到了第三层）

返回第二层
返回第一层
在这里插入图片描述
(15)通过右孩子指针，输入#,返回上一层（此时整树建立完毕，返回主函数）
在这里插入图片描述

2.8.4先序建立二叉树的算法分析：

bool CreateBiTree(BiTree *T)

注意1：传入指向二叉结点指针的二级指针，因为在建立二叉链表时需要 改变指针指向的内容
注意2：在递归建立二叉树时，需要判断是否为空结点，即输入字符为#表示空结点
易错点1：输入空结点时，(*T) = NULL操作之后 应直接返回上一层，故if-else 语句块不能省略
易错点2：传入的应该是 左右孩子指针的地址，而不是 左右孩子指针本身。因为要修改左右孩子指针的值（指向创建的新结点）

（1）定义临时变量ch，用来存储每次输入的字符
（2）若输入为#，则建立空结点，并返回
（3）否则创建结点，并按先序遍历序列递归建立其左右孩子结点
<1>开辟子根结点空间(第一个结点为根结点)
<2>将当前字符 存入 当前根结点
<3>构造左子树
<4>构造右子树

//5.先序建立二叉树
//注意1：传入指向二叉结点指针的二级指针，因为在建立二叉链表时需要 改变指针指向的内容
//注意2：在递归建立二叉树时，需要判断是否为空结点，即输入字符为#表示空结点
bool CreateBiTree(BiTree *T)
{
	//[1]定义临时变量ch，用来存储每次输入的字符
	TElemType ch;
	scanf_s("%c",&ch);

	//[2]若输入为#，则建立空结点，并返回
	if (ch == '#')
	{
		(*T) = NULL;
	}
	//易错点1：输入空结点时，(*T) = NULL操作之后 应直接返回上一层，故if-else 语句块不能省略

	//[2]否则创建结点，并按先序遍历序列递归建立其左右孩子结点
	else
	{
		//<1>开辟子根结点空间(第一个结点为根结点)
		(*T) = (BiNode*)malloc(sizeof(BiNode));

		if (!(*T))
		{
			printf("内存分配失败！\n");
			exit(-1);//程序错误，退出程序
		}

		//<2>将当前字符 存入 当前根结点
		(*T)->data = ch;
		//<3>构造左子树
		CreateBiTree(&((*T)->lchild));
		//<4>构造右子树
		CreateBiTree(&((*T)->rchild));
		//易错点2：传入的应该是 左右孩子指针的地址，而不是 左右孩子指针本身。因为要修改左右孩子指针的值（指向创建的新结点）

	}
	return true;
}

2.9先 中 后序遍历+先序建立整树完整代码如下：

输入实例：
在这里插入图片描述
在这里插入图片描述

#include<stdio.h>
#include<stdlib.h>

typedef char TElemType;//树中元素基本类型为char类型

#define bool int
#define true 1
#define false 0

//二叉树结点链式存储结构（二叉链表）
typedef struct BiNode
{
	TElemType data;//数据域
	struct BiNode* lchild, * rchild;//左，右孩子指针
}BiNode,*BiTree;
//BiNode：用来定义结点类型
//BiTree：用来定义树类型


二叉树结点链式存储结构（三叉链表）
//typedef struct TriTNode
//{
//	TElemType data;//数据域
//	struct TriNode* lchild, * parent,* rchild;//左孩子，双亲，右孩子指针
//}TirNode, * TirTree;
TirNode：用来定义结点类型
TirTree：用来定义树类型


//1.先序遍历二叉树(根左右)
//注意：传入指向根结点的一级指针，因为遍历并不改变数据结构
bool PreOrderTraverse(BiTree T)
{
	//[1]返回条件：子树为空，则返回true;
	if (T == NULL)
	return true;

	//[2]访问根结点
	printf("%c", T->data);

	//[3]递归遍历左子树
	PreOrderTraverse(T->lchild);

	//[4]递归遍历右子树
	PreOrderTraverse(T->rchild);
}


//2.中序遍历二叉树(左根右)
//注意：传入指向根结点的一级指针，因为遍历并不改变数据结构
bool InOrderTraverse(BiTree T)
{
	//[1]返回条件：子树为空，则返回true;
	if (T == NULL)
	return true;

	//[2]递归遍历左子树
	InOrderTraverse(T->lchild);

	//[3]访问根结点
	printf("%c", T->data);

	
	//[4]递归遍历右子树
	InOrderTraverse(T->rchild);
}


//3.后序遍历二叉树(左右根)
//注意：传入指向根结点的一级指针，因为遍历并不改变数据结构
bool PostOrderTraverse(BiTree T)
{
	//[1]返回条件：子树为空，则返回true;
	if (T == NULL)
	return true;

	//[2]递归遍历左子树
	PostOrderTraverse(T->lchild);

	//[3]递归遍历右子树
	PostOrderTraverse(T->rchild);

	//[4]访问根结点
	printf("%c", T->data);
}

//5.先序建立二叉树
//注意1：传入指向二叉结点指针的二级指针，因为在建立二叉链表时需要 改变指针指向的内容
//注意2：在递归建立二叉树时，需要判断是否为空结点，即输入字符为#表示空结点
bool CreateBiTree(BiTree *T)
{
	//[1]定义临时变量ch，用来存储每次输入的字符
	TElemType ch;
	scanf_s("%c",&ch);

	//[2]若输入为#，则建立空结点，并返回
	if (ch == '#')
	{
		(*T) = NULL;
	}
	//易错点1：输入空结点时，(*T) = NULL操作之后 应直接返回上一层，故if-else 语句块不能省略

	//[2]否则创建结点，并按先序遍历序列递归建立其左右孩子结点
	else
	{
		//<1>开辟子根结点空间(第一个结点为根结点)
		(*T) = (BiNode*)malloc(sizeof(BiNode));

		if (!(*T))
		{
			printf("内存分配失败！\n");
			exit(-1);//程序错误，退出程序
		}

		//<2>将当前字符 存入 当前根结点
		(*T)->data = ch;
		//<3>构造左子树
		CreateBiTree(&((*T)->lchild));
		//<4>构造右子树
		CreateBiTree(&((*T)->rchild));
		//易错点2：传入的应该是 左右孩子指针的地址，而不是 左右孩子指针本身。因为要修改左右孩子指针的值（指向创建的新结点）

	}
	return true;
}

int main()
{
	BiTree T;
	CreateBiTree(&T);
	printf("先序遍历序列如下：");
	PreOrderTraverse(T);
	printf("\n");
	printf("中序遍历序列如下：");
	InOrderTraverse(T);
	printf("\n");
	printf("后序遍历序列如下：");
	PostOrderTraverse(T);
	printf("\n");
	return 0;
}

在这里插入图片描述

标签：结点,遍历,层序,先序,序列,指针,二叉树
From： https://blog.csdn.net/2401_82676816/article/details/142148813

相关文章

  • 代码随想录算法训练营，9月13日 | 654.最大二叉树，617.合并二叉树，700.二叉搜索树中的搜索
    654.最大二叉树题目链接：654.最大二叉树文档讲解︰代码随想录(programmercarl.com)视频讲解︰最大二叉树日期：2024-09-13想法：根据昨天中后序列构造二叉树的经验，要找到数组中的最大值的位置，可以设置两个指针表示子树的范围（左闭右开）Java代码如下：classSolution{publicTreeNo......
  • 代码随想录算法 - 二叉树3
    题目1513.找树左下角的值给定一个二叉树的根节点root，请找出该二叉树的最底层最左边节点的值。假设二叉树中至少有一个节点。示例1:输入:root=[2,1,3]输出:1示例2:输入:[1,2,3,4,null,5,6,null,null,7]输出:7提示:二叉树的节点个数的范围是[1,104]-......
  • leetcode刷题day17|二叉树Part05（654.最大二叉树、617.合并二叉树、700.二叉搜索树中的
    654.最大二叉树构造树一般采用的是前序遍历，因为先构造中间节点，然后递归构造左子树和右子树。递归三步曲：1、传入参数，整数数组，数组的开始和结束，返回树的中间节点。2、终止条件：开始大于等于结束，即数组为空。3、递归逻辑：找到最大的元素，记录元素其下标，构建中间节点；递归构造......
  • 【数据结构】第八节：链式二叉树
    个人主页： NiKo数据结构专栏： 数据结构与算法 源码获取：Gitee——数据结构一、二叉树的链式结构typedefintBTDataType;typedefstructBinaryTreeNode{ BTDataTypedata; structBinaryTreeNode*left;//左子树根节点 structBinaryTreeNode*right;//右子......
  • MSSQL遍历数据库根据列值查询数据
    --受理编号declare@slbhvarchar(100),@searchColumnvarchar(100)--设置被查询列值set@slbh='201703160009'--设置搜索列名set@searchColumn='SLBH'declare@tableNamevarchar(50)declare@sqlnvarchar(max),@countintset@sql=N''setNOCOUNTON--优先输出表，......
  • DAY14 二叉树part04
    找树左下角的值513.找树左下角的值迭代法层序遍历classSolution{publicList<List<Integer>>reList=newArrayList<>();publicintfindBottomLeftValue(TreeNoderoot){check(root);intindex=reList.size()-1;......
  • 代码随想录算法训练营，9月12日 | 513.找树左下角的值，112. 路径总和，106.从中序与后序遍
    513.找树左下角的值题目链接：513.找树左下角的值文档讲解︰代码随想录(programmercarl.com)视频讲解︰找树左下角的值日期：2024-09-12想法：1.迭代：用层序遍历，遍历每层时记录下第一个节点的值，到最后一层就是要求的值；2.递归：根据最大的深度来找目标值。Java代码如下：//迭代classSolut......
  • 题解 力扣 LeetCode 105 从前序与中序遍历序列构造二叉树 C/C++
    题目传送门：105.从前序与中序遍历序列构造二叉树-力扣（LeetCode）https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/description/每次在中序遍历序列片段中找到前序遍历序列队首，这是该层的根节点该位置左侧是左子树，右侧是右子树再......
  • Java-数据结构-二叉树-基础 (oﾟ▽ﾟ)o
    文本目录：❄️一、树形结构：  ▶ 1、概念：▶ 2、特殊的概念： ▶ 3、树的表示形式：❄️二、二叉树：  ▶ 1、概念：   ▶2、两种特殊的二叉树：     ➷1）、满二叉树：      ➷ 2）、完全二叉树：  ▶3、二叉树的性质：    ➷ 1）性质一：  ......
  • 五、树和二叉树
    文章目录一、树的引入二、树的术语三、二叉树3.1二叉树的概念3.2二叉树的遍历3.3二叉树-查找指定结点3.3二叉树-删除结点3.4顺序存储二叉树3.5线索化二叉树3.5.1线索化二叉树应用案例3.5.2遍历线索化二叉树3.6二叉树的应用3.6.1堆排序（见`2022.4.5三、排序算......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99