数据结构基础--------【二叉树基础】

二叉树基础

二叉树是一种常见的数据结构，由节点组成，每个节点最多有两个子节点，左子节点和右子节点。二叉树可以用来表示许多实际问题，如计算机程序中的表达式、组织结构等。以下是一些二叉树的概念：

1. 二叉树的深度：从根节点到叶子节点的最长路径的长度称为二叉树的深度，也称为高度。
2. 二叉树的度：一个节点拥有的子节点数量称为该节点的度。二叉树的度为2，即每个节点最多只有两个子节点。
3. 二叉树的遍历：二叉树的遍历是指按照一定顺序访问树中的所有节点。常用的遍历方式有前序遍历、中序遍历和后序遍历。
4. 二叉查找树：二叉查找树是一种特殊的二叉树，它的左子树中所有节点的值都小于根节点的值，而右子树中所有节点的值都大于根节点的值。

二叉树的定义：

	struct TreeNode{
		int val;
		TreeNode* left;
		TreeNode* right;
		TreeNode(int x):val(x),left(nullptr),right(nullptr) {}
	}
1
2
3
4
5
6

1. 二叉树的基本操作：包括二叉树的创建、遍历、搜索等。
2. 二叉查找树的实现及应用：包括二叉查找树的创建、插入、删除、查找等操作。
3. 平衡二叉树：为了解决二叉查找树在某些情况下退化为链表的问题，出现了平衡二叉树，如 AVL 树和红黑树等。
4. 线段树：线段树是一种特殊的二叉树，用于解决区间查询的问题，如区间最大值、区间和等。
5. 树状数组：树状数组也是一种特殊的二叉树，用于解决前缀和、区间和等问题。

1基础介绍

1.基础术语

结点的度：结点的字数个数，比如二叉树的度为2（一个节点最多有2个字数个数）。
树的度：数的所有结点中最大的度数。
叶结点：度为0的结点。
父结点，子结点，兄弟结点（具有同一个父结点的各结点）。
路径和路径的长度：从结点n1到nk,路径所包含的边的个数为路径的长度。
祖先结点，子孙结点。
结点的层次：规定根结点在1层，然后后面的结点层次都依次加一。
树的深度：树中国所有结点的最大层次是这棵树的深度。
二叉树T：一个有穷的结点集合，二叉树的子树有左右顺序之分。

2.二叉树的定义

二叉树T：一个有穷的结点集合，二叉树的子树有左右顺序之分
特殊的二叉树：斜二叉树，满二叉树，完全二叉树（连续结点）

3.二叉树的性质

①个二叉树第i层的最大结点数为: 2^(i-1),（i≥1）
②深度为k的二叉树有最大结点总数为:(2^k)-1, k≥1。(1+2 ^1+2 ^2 …2 ^i )
③0对任何非空二叉树T，若n0表示叶结点的个数、n2是度为2的非叶结点个数，那么两者满足关系n0=n2 +1。
（n0+n1+n2-1） = 0n0+n1+2n2

4.二叉树的遍历

根据遍历结点的顺序，分为前序遍历（NLR）,中序遍历（LNR）,后续遍历（LRN）。树的遍历复杂度为o(n)。
所以看树的前序数组第一个是根结点，后续遍历数组最后一个是根结点，再把该根结点拿到中序遍历数组中去比对就可以划分左右子树。

4.1 前序遍历

如果二叉树为空，什么都不做，否则：
1）访问根节点；
2）先序遍历左子树
3）先序遍历右子树*/
void PreOrder(BiTree T){
    if(T!= null){
        vist(T);//访问根结点N
        PreOrder(T->lchild);//访问左子树L 递归
        PreOrder(T->rchild);//访问右子树R
    }
}
1
2
3
4
5
6
7
8
9
10
11


4.2 中序遍历

/*inorder:
如果二叉树为空，什么都不做，否则：
1）中遍历左子树
2）访问根节点；
3）中序遍历右子树*/
void InOrder(BiTree T){
    if(T!= null){
        InOrder(T->lchild);//访问左子树L 递归
        vist(T);//访问根结点N
        InOrder(T->rchild);//访问右子树R
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

4.3 后序遍历

/*Postorder:
如果二叉树为空，什么都不做，否则：
1）后序遍历左子树
2）后序遍历右子树
3）访问根节点；*/

void PostOrder(BiTree T){
    if(T!= null){
        PostOrder(T->lchild);//访问左子树L 递归
        PostOrder(T->rchild);//访问右子树R
        vist(T);//访问根结点N
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

4.4层序遍历

2.遍历基础

1.DFS（Depth First Search）:递归法得到最终的数组（深度优先算法）

其过程简要来说是对每一个可能的分支路径深入到不能再深入为止，如果遇到死路就往回退，回退过程中如果遇到没探索过的支路，就进入该支路继续深入，每个节点只能访问一次。

深度优先搜索应用：先序遍历，中序遍历，后序遍历。二叉树的前序、中序、后序遍历，本质上可以认为是深度优先遍历。是一种回溯思想。

2.BFS（Breadth First Search）:迭代法实现层序遍历，每次遍历二叉树的某一层。
它并不考虑结果的可能位置，彻底地搜索整张图，直到找到结果为止。基本过程，BFS是从根节点开始，沿着树(图)的宽度遍历树(图)的节点。如果所有节点均被访问，则算法中止。一般用队列数据结构来辅助实现算法。

广度优先搜索应用：层序遍历、最短路径、求二叉树的最大高度、由点到面遍历图、拓扑排序

在我们解题过程中二叉树有两种主要的形式：满二叉树和完全二叉树。

二叉树分类

满二叉树

如果一棵二叉树只有度为0的结点和度为2的结点，并且度为0的结点在同一层上，则这棵二叉树为满二叉树。
如图所示：

这棵二叉树为满二叉树，也可以说深度为k，有2^k-1个节点的二叉树。

完全二叉树

在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层（h从1开始），则该层包含 1~ 2^(h-1) 个节点。（连续）

平衡二叉搜索树

平衡二叉搜索树：又被称为AVL（Adelson-Velsky and Landis）树，且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

如图：

最后一棵 不是平衡二叉树，因为它的左右两个子树的高度差的绝对值超过了1。

二叉搜索树

前面介绍的树，都不用管数值的，而二叉搜索树是要参考数值的，二叉搜索树是一个有序树。
若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
它的左、右子树也分别为二叉排序树
下面这两棵树都是搜索树：

二叉搜索树中序遍历是从小到大的有序数组。

C++中map、set、multimap，multiset的底层实现都是平衡二叉搜索树，所以map、set的增删操作时间时间复杂度是logn，注意我这里没有说unordered_map、unordered_set，unordered_map、unordered_set底层实现是哈希表。

（文章部分参考代码随想录,链接: link