二叉树基础总结

是一种特殊的二叉树，其特点是除最后一层外，每一层上的所有节点都有两个子节点。也就是说，如果一个二叉树的深度为K，且结点总数是(2^k) -1，则它就是满二叉树。满二叉树的每一层都包含最大数量的节点，因此在给定深度下，满二叉树具有最多的节点。满二叉树是完全二叉树的特例，完全二叉树是指除最后一层外，其他层的节点数达到最大，且最后一层的节点都集中在左边。在满二叉树中，因为每一层都已经满了，所以它也是一棵完全二叉树。

完全二叉树：

是由满二叉树而引出的概念。对于深度为k的有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时，这棵二叉树被称为完全二叉树。也就是说，如果对树中的结点按从上至下、从左到右的顺序进行编号，编号为i（1≤i≤n）的结点与满二叉树中编号为i的结点在二叉树中的位置相同，则这棵二叉树就是完全二叉树。

完全二叉树的特点包括：

叶子结点只能出现在最下层和次下层。

最下层的叶子结点集中在树的左部。

倒数第二层若存在叶子结点，一定在右部连续位置。

如果结点度为1，则该结点只有左孩子，即没有右子树。

同样结点数目的二叉树，完全二叉树深度最小。

需要注意的是，满二叉树一定是完全二叉树，但完全二叉树不一定是满二叉树。另外，完全二叉树第i层至多有2^(i-1)个节点，共i层的完全二叉树最多有2^i - 1个节点。

严格二叉树（Strict Binary Tree）：

是二叉树的一种特殊类型，它的特点是每个非终端节点（非叶子节点）都有且仅有两个子节点。也就是说，在严格二叉树中，不存在只有一个子节点或没有子节点的非终端节点。严格二叉树与满二叉树和完全二叉树有所不同。满二叉树要求除最后一层外，每一层上的所有节点都有两个子节点，而严格二叉树则只要求非终端节点有两个子节点，对叶子节点没有要求。完全二叉树则要求除最后一层外，其他层的节点数达到最大，且最后一层的节点都集中在左边，而严格二叉树则没有这个要求。

平衡二叉树（Balanced Binary Tree）：

是一种特殊的二叉树，其特点是在进行插入、删除等操作后，依然能保持树的平衡性，即任何节点的两个子树的高度差的绝对值不超过1。平衡二叉树有多种实现方式，如AVL树和红黑树等。平衡二叉树的重要性在于它能够保证在最坏情况下，查找、插入和删除操作的时间复杂度都是O(log n)，这对于处理大量数据非常有效。如果没有平衡性，最坏情况下二叉树可能退化为链表，导致时间复杂度变为O(n)。

二叉搜索树（Binary Search Tree）：

又称二叉查找树或二叉排序树，是一种经典的数据结构。它具有以下性质：

若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值。

若任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值。

任意节点的左、右子树也分别为二叉搜索树。

二叉搜索树既可以高效地进行插入、查询和删除操作，又具有数组和链表的特点。在二叉搜索树中，查找、插入和删除的时间复杂度都与树的高度成正比，因此在最理想的情况下，这些操作的时间复杂度都是O(logN)。然而，如果二叉搜索树退化为链表，那么这些操作的时间复杂度将变为O(N)。

为了保持二叉搜索树的平衡，避免退化为链表，可以采用平衡二叉搜索树（Balanced Binary Search Tree）的数据结构，如AVL树、红黑树等。这些数据结构通过旋转和重新平衡操作来保持树的平衡，从而确保操作的时间复杂度始终接近O(logN)。

线段树：

线段树是二叉树搜索树的一种。

线段树总结-CSDN博客

最小生成树：

最小生成树（Minimum Spanning Tree, MST）是一个在图论中经常出现的问题，它主要在一个连通的加权无向图中找到一棵包含所有顶点的树，同时使得所有边的权值之和最小。这里的“生成树”是指一个连通无向图的所有顶点构成的极小连通子图，它包含原图中的所有顶点，但只有足以构成一棵树的n-1条边。

最小生成树-CSDN博客

存储结构（顺序存储和链式存储）

顺序存储

二叉树的顺序存储结构通常使用数组来实现。在顺序存储结构中，二叉树中的每个节点按照完全二叉树的顺序存储在一个数组中。完全二叉树的特性使得这种存储方式成为可能，因为在完全二叉树中，除了最后一层之外，其他层的节点数都是满的，并且最后一层的节点都集中在左边。

对于任意一个在数组中的位置为i的节点，其左孩子节点的位置可以通过计算 2i+1 得到，其右孩子节点的位置可以通过计算 2i+2 得到。同样地，对于任意一个位置为j的孩子节点，其父节点的位置可以通过计算 (j-1)/2 得到。

优点：

顺序存储结构的优点是可以快速地访问任意节点，因为每个节点都有一个固定的数组索引。

缺点：

这种存储方式的缺点也很明显，即它可能会浪费存储空间。因为在二叉树中，如果节点数较少，那么数组中的很多位置可能都是空的。此外，对于非完全二叉树，这种存储方式也无法直接表示。

总的来说，顺序存储结构适用于完全二叉树或者节点数较多的二叉树。对于其他类型的二叉树，或者节点数较少的二叉树，链式存储结构可能是一个更好的选择。

链式存储

链式存储结构，又称为链接存储结构，是一种数据的存储方式。

在这种结构中，每个数据元素（通常称为节点）除了包含自身的信息（称为信息域）外，还包含指向其逻辑关系中的下一个节点的指针（称为指针域）。因此，每个节点都通过其指针域与其逻辑关系中的下一个节点相连。这种存储方式不要求逻辑上相邻的元素在物理位置上也相邻，因此它没有顺序存储结构所具有的弱点。

链式存储结构的主要特点包括：

存储密度比顺序存储结构小，因为每个节点都需要额外的存储空间来存储指向下一个节点的指针。
插入和删除操作灵活，节点可以被插入到链表的任何位置，包括首、中、末，而且不需要移动其他节点中的指针。
链表的大小可以按需伸缩，是一种动态存储结构，因此在增加或删除元素时性能更高。
查找节点时的效率相对较低，因为只能从第一个节点开始逐个查找，直到找到所需的节点。

总的来说，链式存储结构是一种非常有用的数据结构，特别适用于需要频繁进行插入和删除操作的情况。然而，由于其查找效率相对较低，因此在需要频繁查找的情况下可能不是最佳选择。

二叉树的遍历

二叉树的每个节点都只会被访问一次。

二叉树有一个前驱和两个后继。

二叉树的遍历顺序有4种，分别是：前序遍历，中序遍历，后序遍历和层序遍历。

前序遍历

先访问根节点，再访问左右子树。

运动轨迹如下：

代码实现（递归）：

void Tree(Tree* root) {
	if (root == NULL) {
		return;
	}
	printf("%d", root->data);
	Tree(root->L_ch);
	Tree(root->R_ch);
}

中序遍历

先访问左子树，再访根节点，最后访问右子树。

运动轨迹如下：

代码实现（递归）：

void Tree(Tree* root) {
	if (root == NULL) {
		return;
	}
    Tree(root->L_ch);
	printf("%d", root->data);
	Tree(root->R_ch);
}

后序遍历

先左子树，再右子树，最后根节点。

运动轨迹如下：

代码实现（递归）：

void Tree(Tree* root) {
	if (root == NULL) {
		return;
	}
    Tree(root->L_ch);
    Tree(root->R_ch);
	printf("%d", root->data);
}

层次遍历：

（哈哈，其实不是很复杂，所以我还是先在这篇博客里面补充一下概念吧）

二叉树的层次遍历，也称为广度优先遍历，其顺序是从二叉树的第一层（根节点）开始，从上至下逐层遍历，同一层中则按照从左到右的顺序对节点逐个访问。在进行层次遍历的时候，一般会使用一个队列结构来辅助实现。具体过程如下：

首先将根节点入队。

然后开始一个循环，循环条件为队列不为空。在每次循环中，先取出队首元素并访问，然后将其左孩子和右孩子（如果存在）依次入队。

重复上述步骤，直到队列为空，此时所有节点都已访问完毕，层次遍历结束。

层次遍历的顺序是逐层遍历，同一层中从左到右的顺序。

二叉树的遍历题目（持续更新版）

二叉树的遍历题型-CSDN博客

树的定义：

深度和高度：

二叉树

由来

二叉树种类：

满二叉树：

完全二叉树：

严格二叉树（Strict Binary Tree）：

平衡二叉树（Balanced Binary Tree）：

二叉搜索树（Binary Search Tree）：

线段树：

最小生成树：

存储结构（顺序存储和链式存储）

顺序存储

优点：

缺点：

链式存储

链式存储结构的主要特点包括：

二叉树的遍历

前序遍历

代码实现（递归）：

中序遍历

代码实现（递归）：

后序遍历

代码实现（递归）：

层次遍历：

二叉树的遍历题目（持续更新版）

相关推荐

最近更新

热门阅读