数据结构—树和二叉树

5.树和二叉树

5.1树和二叉树的定义

树形结构（非线性结构）：结点之间有分支，具有层次关系。

5.1.1树的定义

树（Tree）是n（n≥0）个结点的有限集。

  • 若n=0，称为空树；
  • 若n＞0，则它满足如下两个条件：
    1. 有且仅有一个特定的称为根（Root）的结点；
    2. 其余结点可分为m（m≥0）个互不相交的有限集T1,T2,…Tm，其中每一个集合本身又是一棵树，并称为根的子树（SubTree）。

**树是n个结点的有限集。**显然，树的定义是一个递归的定义。

数据结构 二叉树的存储结构_线程二叉树| 数据结构_cumtb2002的博客-CSDN博客

树的其他表示形式：

img

5.1.2树的基本术语

img

  • **根结点：**非空树中无前驱结点的结点。

  • **结点的度：**结点拥有的子树数。

  • **树的度：**树内各结点的度的最大值。

  • **叶子结点：**度为0的点，也称为终端结点。

  • **分支结点：**度≠0的结点，也称为非终端结点。

  • **内部结点：**根结点以外的分支结点称为内部结点。

  • **双亲结点：**结点的子树的根称为该结点的孩子，该结点称为孩子的双亲。

  • **兄弟结点：**结点之前有共同的双亲结点称为兄弟结点。

  • **堂兄弟结点：**双亲在同一层的结点。

  • **结点的祖先：**从根到该结点所经分支上的所有结点。

  • **结点的子孙：**以某结点为根的子树中的任一结点。

  • **树的深度：**树中结点的最大层次。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-XagGN3sY-1691068168684)(https://ts1.cn.mm.bing.net/th/id/R-C.fe38e3b271e2321ef483becbb761c23b?rik=2QonkZPTVvq%2btg&riu=http%3a%2f%2fpic.baike.soso.com%2fp%2f20131206%2f20131206141836-722390134.jpg&ehk=mNDvDkeq8qFKHHsXCLhiWhru8%2fGKWK1lU%2f3sEGzBvh4%3d&risl=&pid=ImgRaw&r=0&sres=1&sresct=1)]

有序树：树中结点的各子树从左至右有次序（最左边的为第一个孩子）。

**无序树：**树中结点的各子树无次序。

**森林：**是m（m≥0）颗互不相交的树的集合。把根结点删除树就变成了森林。

​ 一棵树可以看成是一个特殊的森林。

​ 给森林中的各子树加上一个双亲结点，森林就变成了树。

树一定是森林，但森林不一定是树。

5.1.3树结构和线性结构的比较

线性结构树结构
第一个数据元素无前驱根结点（只有一个）无双亲
最后一个数据元素无后继叶子结点（可以有多个）无孩子
其他数据元素一个前驱，一个后继其他结点中间结点一个双亲，多个孩子
一对一一对多

5.1.4二叉树的定义

为什么要重点研究每结点最多只有两个“叉”的树？

  • 二叉树的机构最简单，规律性最强；
  • 可以证明，所有树都能转为唯一对应的二叉树，不失一般性。

普通树（多叉树）若不转化为二叉树，则运算很难实现

​ 二叉树在树结构的应用中起着非常重要的作用，因为对二叉树的许多操作算法简单，而任何树都可以与二叉树相互转换，这样就解决了树的存储结构及其运算中存在的复杂性。

二叉树是n（n≥0）个结点的有限集，它或者是空集（n=0），或者由一个根结点及两颗互不相交的分别称作这个根的左子树和右子树的二叉树组成。

特点：

  1. 每个结点最多有两孩子（二叉树中不存在度大于2的结点）。
  2. 子树有左右之分，其次序不能颠倒。
  3. 二叉树可以是空集合，根可以有空的左子树或空的右子树

注意：二叉树不是树的特殊情况，它们是两个概念。

​ 二叉树结点的子树要区分左子树和右子树，即使只有一颗子树也要进行区分，说明它是左子树，还是右子树。

​ 树当结点只有一个孩子时，就无须区分他是左还是右的次序。因此，二者是不同的。这是二叉树与树的最主要的区别。

二叉树的实现和操作 - 知乎

也就是二叉树每个结点位置或者说次序都是固定的，可以是空，但是不可以说它没有位置，而树的结点位置是相对于别的结点来说的，没有别的结点时，它就无所谓左右了。

二叉树的五种基本形态

【数据结构】--------二叉树的基本知识点总结_@make great efforts 的博客-CSDN博客

注意：虽然二叉树与树概念不同，但有关树的基本术语对二叉树都适用。

5.2树和二叉树的类型定义

CreateBiTree（&T，definition）

​ 初始条件：definition给出二叉树T的定义。

​ 操作结果：按definition构造二叉树T。

PreOrderTraverse（T）

​ 初始条件：二叉树T存在。

​ 操作结果：先序遍历T，对每个结点访问一次。

InOrderTraverse（T）

​ 初始条件：二叉树T存在。

​ 操作结果：中序遍历T，对每个结点访问一次。

POSTOrderTraverse（T）

​ 初始条件：二叉树T存在。

​ 操作结果：后序遍历T，对每个结点访问一次。

5.3二叉树的性质和存储结构

5.3.1二叉树的性质

  • 性质1：在二叉树的第 i 层上至多有 2i-1个结点（i≥1）。

    金融工程|CFA|二叉树期权定价模型（一） – FX投机者

  • 性质2：深度为 k 的二叉树至多有2k-1个结点（k≥1）。

    深度为k时至少有 k 个结点。

  • 性质3：对任何一颗二叉树T，如果其叶子数为n0，度为2的结点数为n2，则 n0=n2+1。

    总边数为B B = n - 1 或 B = n2 * 2 + n1 * 1

    总结点数为n n = n2 * 2 + n1 * 1 + 1 或者 n = n2 + n1 + n0

5.3.2两种特殊形式的二叉树

1、满二叉树

一棵深度为 k 且有 2k-1 个结点的二叉树称为满二叉树。

C#写算法之二叉树_HKW_hankangwen的博客-CSDN博客_c# 二叉树

特点：

  1. 每一层上的结点数都是最大结点数（即每层都满）。
  2. 叶子结点全部在最底层。

对满二叉树结点位置进行编号

  • 编号规则：从根结点开始，自上而下，自左而右。
  • 每一结点位置都有元素。

满二叉树在同样深度的二叉树中结点个数最多。

满二叉树在同样深度的二叉树中叶子结点个数最多。

2、完全二叉树

深度为k的具有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号为1~n的结点——对应时，称之为完全二叉树。

数据结构11.二叉树_Aemonair's 世界树．-CSDN博客

注意：在满二叉树中，从最后一个结点开始，连续去掉任意个结点，即是一颗完全二叉树。

​ 一定是连续的去掉！！！

特点：

  1. 叶子只可能分布在层次最大的两层上。
  2. 对任一结点，如果其右子树的最大层次为i，则其左子树的最大层次必为 i 或 i + 1。

满二叉树一定是完全二叉树，完全二叉树不一定满二叉树。

5.3.3完全二叉树的性质

  • **性质4：**具有 n 个结点的完全二叉树的深度为 [log2n] + 1。

    注意：[ x ]：称作x的底，表示不大于x的最大整数。

    表明了完全二叉树结点数n与完全二叉树深度k之间的关系。

  • 性质5：如果对一棵有n个结点的完全二叉树（深度为[ log2n ]+1）的结点按层序编号（从第1层到第[log2n]+1层，每层从左到右），则对任一结点 i （1≤ i ≤ n）有：

    1. 如果 i =1，则结点 i 是二叉树的根，无双亲；如果 i ＞1，则其双亲是结点 [i / 2]。
    2. 如果2i＞n，则结点i为叶子结点，无左孩子；否则，其左孩子是结点2i。
    3. 如果2i + 1＞n，则结点i无右孩子；否则，其右孩子是结点 2i +1。

    表明了完全二叉树中双亲结点编号与孩子结点编号之间的关系。

5.3.4二叉树的存储结构

二叉树的存储结构分为顺序存储结构以及链式存储结构（二叉链表，三叉链表）。

1、二叉树的顺序存储结构

实现：按满二叉树的结点层次编号，依次存放二叉树中的数据元素。

代码随想录

二叉树顺序存储表示：

#define MAXSIZE 100
typedef int SqBiTree[MAXSIZE];
SqBiTree bt;

二叉树基础（上）：什么样的二叉树适合用数组来存储？_t_z_l的博客-CSDN博客

二叉树的顺序存储缺点：

  • **最坏情况：**深度为k的且只有k个结点的单支树需要长度为2k-1的一维数组。

特点：

  1. 结点间关系蕴含在其存储位置中
  2. 浪费空间，适于存满二叉树和完全二叉树
2、二叉树的链式存储结构

二叉树基础（上）：什么样的二叉树适合用数组来存储？_t_z_l的博客-CSDN博客

二叉链表存储结构：

typedef struct BiNode {
	int data;
	struct BiNode* lchild, * rchild;//左右孩子
}BiNode,*BiTree;

二叉树基本概念与遍历_Xucc_x的博客-CSDN博客

在n个结点的二叉链表，有__n+1__个空指针域。

分析：必有2n个链域。除根结点外，每个结点有且仅有一个双亲，所以只会有 n-1 个结点的链域存放指针，指向非空子女结点。

空指针数目 = 2n -（n-1）=n+1

三叉链表

二叉树基本概念与遍历_Xucc_x的博客-CSDN博客

typedef struct TriTNode{
  int data;
  struct TriTNode *lichild,*parent,*rchild;
}TriTNode,*TriTree;

5.4遍历二叉树和线索二叉树

5.4.1遍历二叉树

遍历定义——顺着某一条搜索路径巡访二叉树中的结点，使得每个结点均被访问一次，而且仅被访问一次（又称周游）。

  • “访问”的含义很广，可以是对结点做各种处理，如：输出结点的信息，修改结点的数据值等，但要求这种访问不破坏原来的数据结构。

遍历目的——得到树中所有结点的一个线性排列。

遍历用途——它是树结构插入、删除、修改、查找和排序运算的前提，是二叉树一切运算的基础和核心。

1、遍历二叉树算法描述

遍历方法：依次遍历二叉树中的三个组成部分，便是遍历了整个二叉树。

二叉树的先序遍历、中序遍历、后序遍历、层次遍历-图文详解_stay_foolish12的博客-CSDN博客_先序遍历中序遍历后序遍历图解

Java二叉树的前序、中序、后序三种遍历 - 知乎

则遍历整个二叉树方案共有：

ABC、ACB、BAC、BCA、CAB、CBA六种。

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

​ ABC —— 先（根）序遍历，

​ BAC —— 中（根）序遍历，

​ BCA —— 后（根）序遍历。

先序遍历二叉树中序遍历二叉树后序遍历二叉树
若二叉树为空，则空操作； 否则若二叉树为空，则空操作； 否则若二叉树为空，则空操作； 否则
（1）访问根结点；（1）中序遍历左子树；（1）后序遍历左子树；
（2）先序遍历左子树；（2）访问根结点；（2）后序遍历右子树；
（3）先序遍历右子树。（3）中序遍历右子树。（3）访问根结点。

由二叉树的递归定义可知，遍历左子树和遍历右子树可如同遍历二叉树一样“递归”进行。

二叉树的实现和操作 - 知乎

2、根据遍历序列确定二叉树
  • 若二叉树中各结点的值均不相同，则二叉树结点的先序序列，中序序列和后序序列都是唯一的。
  • 由二叉树的先序序列和中序序列，或由二叉树的后序序列和中序序列可以确定唯一一棵二叉树。
3、遍历的算法思想
先序遍历（根左右）

若二叉树为空，则空操作；若二叉树非空，

​ 访问根结点（D）

​ 前序遍历左子树（L）

​ 前序遍历右子树（R）

bool PreOrderTraverse(BiTree T) {
	if (T == NULL) return true;//空二叉树
	else {
		visit(T);//访问根结点
		PreOrderTraverse(T->lchild);//递归遍历左子树
		PreOrderTraverse(T->rchild);//递归遍历右子树
	}
}

void Pre(BiTree T) {
	if (T != NULL) {
		printf("%d\t", T->data);
		Pre(T->lchild);
		Pre(T->rchild);
	}
}
中序遍历（左根右）

若二叉树为空，则空操作；若二叉树非空，

​ 中序遍历左子树（L）

​ 访问根结点（D）

​ 中序遍历右子树（R）

bool InOrderTraverse(BiTree T) {
	if (T == NULL) return true;
	else {
		InOrderTraverse(T->lchild);//递归遍历左子树
		visit(T);//访问根结点
		InOrderTraverse(T->rchild);//递归遍历右子树
	}
}
后序遍历（左右根）

若二叉树为空，则空操作；若二叉树非空，

​ 后序遍历左子树（L）

​ 后序遍历右子树（R）

​ 访问根结点（D）

bool PostOrderTraverse(BiTree T) {
	if (T == NULL) return true;
	else {
		PostOrderTraverse(T->lchild);//递归遍历左子树
		PostOrderTraverse(T->rchild);//递归遍历右子树
		visit(T);//访问根结点
	}
}
遍历算法的分析

如果去掉输出语句，从递归的角度看，三种算法是完全相同的，或者说这三种算法的访问路径是相同的，只是访问结点的时机不同。

二叉树的非递归遍历 - 知乎

从虚线的出发点到终点的路径上，每个结点都要经过 3 次。

第一次经过时访问 = 先序遍历

第二次经过时访问 = 中序遍历

第三次经过时访问 = 后序遍历

4、遍历二叉树的非递归算法
中序遍历非递归算法

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

基本思想：

  1. 建立一个栈；
  2. 根结点进栈，遍历左子树；
  3. 根结点出栈，输出根结点，遍历右子树
bool InOrderTraver(BiTree T) {
	BiTree p,q;
	SqStack S;
	InitStack(S);
	p = T;
	while (p||!StackEmpty(S))
	{
		if (p) {
			Push(S, p);
			p = p->lchild
		}
		else {
			Pop(S, q);
			printf("%c", q->data);
			p = q->rchild;
		}
	}
	return true;
}
二叉树的层次遍历

img

对于一颗二叉树，从根结点开始，按从上到下，从左到右的顺序访问每一个结点。每个结点仅仅访问一次。

**算法设计思路：**使用一个队列

  1. 将根结点进队；
  2. 队不空时循环：从队列中出列一个结点*p，访问它；
    • 若它有左孩子结点，将左孩子结点进队；
    • 若它有右孩子结点，将右孩子结点进队。

使用队列类型定义如下：

void LevelOrder(BTNode *b){
  BTNode *p;
  SqQueue *qu;
  InitQueue(qu);
  EnQueue(qu,b);//根结点指针进入队列
  while(!QueueEmpty(qu)){
    DeQueue(qu,p);//出队结点p
    printf("%c",p->data);
    if(p->lchild!=NULL)
      enQueue(qu,p->lchild);//有左孩子时将其进队
    if(p->rchild!=NULL)
      enQueue(qu,p->rchild);//有右孩子时将其进队
  }
}

5.4.2二叉树遍历算法的应用

1、二叉树的建立

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

例：已知先序序列为：ABCDEGF

（1）从键盘输入二叉树的结点信息，建立二叉树的存储结构；

（2）在建立二叉树的过程中按照二叉树先序方式建立。

二叉树先序递归建立_百度知道

对于上图所示二叉树，按下列顺序读入字符：

ABC##DE#G##F###

bool CreatBiTree(BiTree& T) {
	char* ch;
	scanf("%c", & ch);
	if (ch == "#") T = NULL;
	else {
		if (!(T = (BiNode*)malloc(sizeof(BiNode))))
			return false;
		T->data = ch;//生成根结点
		CreatBiTree(T->lchild);//构建左子树
		CreatBiTree(T->rchild);//构建右子树
	}
	return true;
}
2、复制二叉树

算法思想：

  1. 如果是空树，递归结束；
  2. 否则，申请新结点空间，复制根节点
    • 递归复制左子树
    • 递归复制右子树
int Copy(BiTree T, BiTree& NewT) {
	if (T == NULL) {
		NewT = NULL;
		return 0;
	}
	else {
		NewT = new BiNode;
		NewT->data = T->data;
		Copy(T->lchild, NewT->lchild);
		Copy(T->rchild, NewT->rchild);
	}
}
3、计算二叉树深度
  • 如果是空树，则深度为0；
  • 否则，递归计算左子树的深度记为m，递归计算右子树的深度记为n，二叉树的深度则为m与n的较大者加1。
int Depth(BiTree T) {
	if (T == NULL) return 0;//如果是空树返回0
	else {
		int m = Depth(T->lchild);
		int n = Depth(T->rchild);
		if (m > n) return(m + 1);
		else return(n + 1);
	}
}
4、计算二叉树结点总数
  • 如果是空树，则结点个数为0；
  • 否则，结点个数为左子树的结点个数 + 右子树的结点个数再 + 1
int NodeCount(BiTree T) {
	if (T == NULL)
		return 0;
	else
		return NodeCount(T->lchild) + NodeCount(T->rchild) + 1;
}
5、计算二叉树叶子结点数
  • 如果是空树，则叶子结点个数为0；
  • 否则，为左子树的叶子结点个数 + 右子树的叶子结点个数。
int LeafCount(BiTree T) {
	if (T == NULL)
		return 0;//如果是空树返回0
	if (T->lchild == NULL && T->rchild == NULL)
		return 1;//如果是叶子结点返回1
	else
		return LeafCount(T->lchild) + LeafCount(T->rchild);
}

5.4.3线索二叉树

线索化二叉树_findgeneralgirl的博客-CSDN博客

问题：为什么要研究线索二叉树？

​ 当用二叉链表作为二叉树的存储结构时，可以很方便地找到某个结点的左右孩子；但一般情况下，无法直接找到该结点在某种遍历序列中的前驱和后继结点。

提出的问题：如何寻找特定遍历序列中二叉树结点的前驱和后继？

解决方法：

  1. 通过遍历寻找——费时间
  2. 再增设前驱、后继指针域——增加了存储负担。
  3. 利用二叉链表中的空指针域。

回顾：二叉树链表中空指针域的数量：

  • 具有n个结点的二叉链表中，一共有2n个指针域；因为n个结点中有n-1个孩子，即2n个指针域中，有n-1个用来指示结点的左右孩子，其余n+1个指针域为空。

利用二叉链表中的空指针域：

​ 如果某结点的左孩子为空，则将空的左孩子指针域改为指向其前驱；如果某结点的右孩子为空，则将空的右孩子指针域改为指向其后继——这种改变指向的指针称为“线索”

​ 加上了线索的二叉树称为线索二叉树（Threaded Binary Tree）

​ 对二叉树按某种遍历次序使其改变为线索二叉树的过程叫线索化。

为了区分lchild和rchild指针到底是指向孩子的指针，还是指向前驱或者后继的指针，对二叉链表中每个结点增设两个标志域ltag和rtag，并约定：

​ ltag = 0 lchild指向该结点的左孩子

​ ltag = 1 lchild指向该结点的前驱

​ rtag = 0 rchild指向该结点的右孩子

​ rtag = 1 rchild指向该结点的后继

线索二叉树结点的结构为：

typedef struct BiThrNode {
	int data;
	int ltag, rtag;
	struct BiThrNode* lchild, * rchild;
}BiThrNode,*BiThrTree;

5.5树和森林

树（Tree）是n（n≥0）个结点的有限集。若n=0，称为空树；若n>0

  1. 有且仅有一个特定的称为根（Root）的结点；
  2. 其余结点可分为m（m≥0）个互不相交的有限集T1,T2,T3,…,Tm

森林：是m（m≥0）棵互不相交的树的集合。

5.5.1树的存储结构

1、双亲表示法

实现：定义结构数组存放树的结点，每个结点含两个域：

  • 数据域：存放结点本身信息。
  • 双亲域：指示本结点的双亲结点在数组中的位置。

数据结构-树_Dark_Song的博客-CSDN博客

C语言的类型描述：

typedef struct PTNode{
  TElemType data;
  int parent;//双亲位置域
}PTNode;

树结构：

#define MAXSIZE 100
typedef struct{
  PTNode nodes[MAXSIZE];
  int r,n;//根结点的位置和结点个数
}PTree;
2、孩子链表

把每个结点的孩子结点排列起来，看成是一个线性表，用单链表存储，则n个结点由n个孩子链表（叶子的孩子链表为空表）。而n个头指针又组成一个线性表，用顺序表（含n个元素的结构数组）存储。

树的存储结构：双亲表示法、孩子表示法、孩子兄弟法_wmy0217_的博客-CSDN博客_树的孩子表示法存储结构

C语言的类型描述：

孩子结点结构：child | next

typedef struct CTNode{
  int child;
  struct CTNode *next;
}*ChildPtr;

双亲结点结构：data | firstchild

typedef struct{
  TElemType data;
  ChildPtr firstchild;//孩子链表头指针
}CTBox;

树结构：

typedef struct{
  CTBox nodes[MAXSIZE];
  int n,r;//结点数和根结点的位置
}CTree;

特点：找孩子容易，找双亲难。

3、孩子兄弟表示法

也称为二叉树表示法，二叉链表表示法。

实现：用二叉链表作为树的存储结构，链表中每个结点的两个指针域分别指向其第一个孩子结点和下一个兄弟结点。

typedef struct CSNode{
  ElemType data;
  struct CSNode *firstchild,*nextsibling;
}CSNode,*CSTree;

树的存储结构：双亲表示法、孩子表示法、孩子兄弟法_wmy0217_的博客-CSDN博客_树的孩子表示法存储结构

5.5.2树与二叉树的转换

将树转化为二叉树进行处理，利用二叉树的算法来实现对树的操作。

  • 由于树和二叉树都可以用二叉链表作存储结构，则以二叉链表作为媒介可以导出树与二叉树之间的一个对应关系。
1、树转二叉树

树转二叉树转换步骤：兄弟相连留长子

  1. 加线：在兄弟之间加一连线。

  2. 抹线：对每个结点，除了其左孩子外，去除其与其余孩子之间的关系。

  3. 旋转：以树的根结点为轴心，将整数顺时针转45°。

    树、森林与二叉树的转换_Raise的博客-CSDN博客_森林转化为二叉树

2、二叉树转树

二叉树转树步骤：左孩右右连双亲，去掉原来右孩线

  1. 加线：若p结点是双亲结点的左孩子，则将p的右孩子，右孩子的右孩子…沿分支找到的所有右孩子，都与p的双亲用线连起来。
  2. 抹线：抹掉原二叉树中双亲与右孩子之间的连线。
  3. 调整：将结点按层次排列，形成树结构。

树、森林与二叉树的转换_Raise的博客-CSDN博客_森林转化为二叉树

5.5.3森林和二叉树的转化

1、森林转二叉树

森林转换成二叉树：树边二叉根相连

  1. 将各棵树分别转换成二叉树
  2. 将每棵树的根结点用线相连
  3. 以第一课树根结点为二叉树的根，再以根结点为轴心，顺时针旋转，构成二叉树型结构。

一般树与二叉树、森林与二叉树的转换_尕焱aYan的博客-CSDN博客

2、二叉树转森林

二叉树转换成森林：去掉全部右孩线，孤立二叉再还原。

  1. 抹线：将二叉树中根结点与其右孩子连线，及沿又分支搜索到的所有右孩子间连线全部抹掉，使之变成孤立的二叉树。

  2. 还原：将孤立的二叉树还原成树。

    树，森林，二叉树的互相转换_ice_time1的博客-CSDN博客

5.5.4树与森林的遍历

1、树的遍历

  • 先根（次序）遍历：

    若树不空，则先访问根结点，然后依次先根遍历各课子树。

  • 后根（次序）遍历：

    若树不空，则先依次后根遍历各棵子树，然后访问根结点。

  • 按层次遍历：

    若树不空，则自上而下自左而右访问树中每个结点。

2、森林的遍历

将森林看作三部分构成：

  1. 森林中第一棵树的根结点；
  2. 森林中第一棵树的子树森林；
  3. 森林中其他树构成的森林。

  • 先序遍历：依次从左至右对森林中的每一棵树进行先根遍历

    若森林不为空，则

    1. 访问森林中第一棵树的根结点；
    2. 先序遍历森林中第一棵树的子树森林；
    3. 先序遍历森林中（除第一棵树之外）其余树构成的森林。

  • 中序遍历：依次从左至右对森林中的每一颗树进行后根遍历

    若森林不为空，则

    1. 中序遍历森林中第一棵树的子树森林；
    2. 访问森林中第一棵树的根结点；
    3. 中序遍历森林中（除第一棵树之外）其余树构成的森林。

【数据结构】树：非二叉树（普通树）与森林的遍历_非二叉树的遍历_Steve_Stone的博客-CSDN博客

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

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

相关文章

文件传输软件的市场现状和未来趋势

文件传输软件的市场现状和未来趋势

文件传输软件是一种能够在不同计算机之间高效、便捷、安全地传送各种类型的文件的应用软件。它是计算机领域中的一项重要技术，涉及到网络通信、数据加密、文件管理等多个方面。随着互联网和移动互联网的发展，文件传输软件的市场需求也日益增大&#xff0…
阅读更多...
Linux 中使用 verdaccio 搭建私有npm 服务器

Linux 中使用 verdaccio 搭建私有npm 服务器

安装 Node Linux中安装Node 安装verdaccio npm i -g verdaccio安装完成 输入verdaccio,出现下面信息代表安装成功，同时输入verdaccio后verdaccio已经处于运行状态，当然这种启动时暂时的，我们需要通过pm2让verdaccio服务常驻 ygiZ2zec61wsg…
阅读更多...
iPhone苹果手机地震预警功能怎么开启？

iPhone苹果手机地震预警功能怎么开启？

iPhone苹果手机地震预警功能怎么开启？ 1、打开iPhone苹果手机设置； 2、在iPhone苹果手机设置内找到辅助功能； 3、在辅助功能内找到触控； 4、在iPhone苹果手机辅助功能触控内找到振动，如果是关闭状态请启； …
阅读更多...
看门狗文章

看门狗文章

1. iwdg.c #include "stm32f4xx.h" #include "iwdg.h"//prer：预分频值 //rlr：自动重装载值 void IWDG_Init(unsigned char prer,unsigned int rlr)//IWDG初始化 {IWDG_WriteAccessCmd(IWDG_WriteAccess_Enable);…
阅读更多...
你知道音频文件格式转换要用什么软件吗？今天就来分享给你

你知道音频文件格式转换要用什么软件吗？今天就来分享给你

你是否曾经遇到过这样的情况？你正在享受着一首心爱的歌曲，却突然发现它的音频格式不兼容你的设备或播放器？或者你需要将录音文件从一种格式转换成另一种，以便在不同场景中使用？音频格式转换软件就像是一个通向音乐自由…
阅读更多...
林大数据结构【2019】

林大数据结构【2019】

关键字： 哈夫曼树权值最小、哈夫曼编码、邻接矩阵时间复杂度、二叉树后序遍历、二叉排序树最差时间复杂度、非连通无向图顶点数（完全图）、带双亲的孩子链表、平衡二叉树调整、AOE网关键路径 一、判断 二、单选 三、填空 四、应用题 五、算…
阅读更多...
Windows搭建Snort环境及使用方式

Windows搭建Snort环境及使用方式

目录 0x01 前置环境0x02修改配置文件0x03 自测0x04 使用0x05 感言 0x01 前置环境 环境描述windows10snort2.9.2https://www.snort.org/downloads 先把上面环境下载好！ 需要注意的是安装npcap这个软件 0x02修改配置文件 软件安装目录：C:/Snort/ 配置文…
阅读更多...
视频添加字幕

视频添加字幕

1、依靠ffmpeg 命令 package zimu;import java.io.IOException;public class TestSrt {public static void main(String[] args) {String videoFile "/test/test1.mp4";String subtitleFile "/test/test1.SRT";String outputFile "/test/testout13…
阅读更多...
dy六神参数记录分析（立秋篇）

dy六神参数记录分析（立秋篇）

version： 23.9 X-SSSTUB: 搜索：x-tt-dt var hashMap Java.use("java.util.HashMap");hashMap.put.implementation function (a, b) {console.log("hashMap.put: ", a, b);return this.put(a, b);}https://codeooo.blog.csdn.n…
阅读更多...
河北泛域名https证书可以保护几个域名

河北泛域名https证书可以保护几个域名

什么是泛域名https证书呢？在众多https证书产品中总有几种特别的https证书——泛域名https证书、多域名https证书。通常一张https证书只能保护一个站点，如果想保护多个站点，只能一次给各个站点购买https证书，这种做法虽然解决了问题…
阅读更多...
华为云Classroom赋能—TooKit助力开发者上云

华为云Classroom赋能—TooKit助力开发者上云

对于资深程序员而言，IDE是必不可少的，它好比是剑客手中的宝剑，IDE帮助程序员更快更丝滑的去编程，同时插件就是这把剑上的各种Buff，为宝剑赋能，提供更好的升级打怪体验。 什么是Huawei Cloud Toolkit Huaw…
阅读更多...
STDF - 基于 Svelte 和 Tailwind CSS 打造的移动 web UI 组件库，Svelte 生态里不可多得的优秀项目

STDF - 基于 Svelte 和 Tailwind CSS 打造的移动 web UI 组件库，Svelte 生态里不可多得的优秀项目

Svelte 是一个新兴的前端框架，组件库不多，今天介绍一款 Svelte 移动端的组件库。 关于 STDF STDF 是一个移动端的 UI 组件库，主要用来开发移动端 web 应用。和我之前介绍的很多 Vue 组件库不一样，STDF 是基于近来新晋 js 框架 S…
阅读更多...
MySQL之深入InnoDB存储引擎——redo日志

MySQL之深入InnoDB存储引擎——redo日志

文章目录 一、为什么需要redo日志二、redo日志的类型1）简单的redo日志类型2）复杂的redo日志类型 三、Mini-Transaction四、redo日志的写入过程五、redo日志文件1、刷盘时机2、redo日志文件组 六、log sequence number1、lsn的引入2、flushed_to_disk_lsn…
阅读更多...
生活小妙招之UE custom Decal

生活小妙招之UE custom Decal

因为这几年大部分时间都在搞美术，所以博客相关的可能会鸽的比较多，阿巴阿巴 https://twitter.com/Tuatara_Games/status/1674034744084905986 之前正好看到一个贴花相关的小技巧，正好做一个记录，也在这个的基础上做一些小的拓展…
阅读更多...
GATK BaseRecalibratorSpark 过程中因Too many open files终止

GATK BaseRecalibratorSpark 过程中因Too many open files终止

Error： GATK BaseRecalibratorSpark 过程中因Too many open files终止 执行命令： nohup time ./gatk --java-options "-Xmx16G" BaseRecalibratorSpark -R ../../alignment/hg38/hg38.fa -I ../../alignment/bam/P368T.sorted.markdup.bam …
阅读更多...
【Ubuntu】Ubuntu 22.04 升级 OpenSSH 9.3p2 修复CVE-2023-38408

【Ubuntu】Ubuntu 22.04 升级 OpenSSH 9.3p2 修复CVE-2023-38408

升级原因 近日Openssh暴露出一个安全漏洞CVE-2023-38408，以下是相关资讯： 一、漏洞详情 OpenSSH是一个用于安全远程登录和文件传输的开源软件套件。它提供了一系列的客户端和服务器程序，包括 ssh、scp、sftp等，用于在网络上进行…
阅读更多...
[C++项目] Boost文档 站内搜索引擎(5): cpphttplib实现网络服务、html页面实现、服务器部署...

[C++项目] Boost文档 站内搜索引擎(5): cpphttplib实现网络服务、html页面实现、服务器部署...

在前四篇文章中, 我们实现了从文档文件的清理 到 搜索的所有内容: 项目背景: 🫦[C项目] Boost文档 站内搜索引擎(1): 项目背景介绍、相关技术栈、相关概念介绍…文档解析、处理模块parser的实现: 🫦[C项目] Boost文档 站内搜索引擎(2): 文档文本解析模块…
阅读更多...
Flutter（八）事件处理与通知

Flutter（八）事件处理与通知

1.原始指针事件处理 一次完整的事件分为三个阶段：手指按下、手指移动、和手指抬起，而更高级别的手势（如点击、双击、拖动等）都是基于这些原始事件的。 Listener 组件 Flutter中可以使用Listener来监听原始触摸事件 Listener({…
阅读更多...
C高级第四讲

C高级第四讲

1、思维导图 2、写一个shell函数，获取用户的uid和gid并使用变量接收 #!/bin/bash function get_id() {uidid -u ubuntugidid -g ubuntu } get_id echo "uid:$uid" echo "gid:$gid"运行结果 3、排序 冒泡排序 /* ------------------------…
阅读更多...
全网首档操作系统探访体验栏目“龙蜥+超级探访”震撼上线！看国产 OS 如何乘风破浪

全网首档操作系统探访体验栏目“龙蜥+超级探访”震撼上线！看国产 OS 如何乘风破浪

编者按：随着龙蜥社区规模的迅速壮大，为了更好的服务于生态伙伴和广大用户，龙蜥社区推出“全网首档操作系统探访体验节目”《龙蜥超级探访》，该栏目将带领大家走进龙蜥的生态伙伴和用户现场，共同揭示龙蜥与生态伙伴如何…
阅读更多...
最新文章

Copyright @ 2022~2023