数据结构中的树与二叉树,是在建立非线性数据结构方面极为重要的两个概念。它们不仅能够模拟出生活中各种实际问题的复杂关系,还常被用于实现搜索、排序、查找等算法,甚至成为一些大型软件和系统中的基础设施。
无论你是初学者还是进阶者,本文将为你提供简单易懂、实用可行的知识点,帮助你更好地掌握树和二叉树在数据结构和算法中的重要性,进而提升算法解题的能力。接下来让我们开启数据结构与算法的奇妙之旅吧。
目录
树和森林的概念
树的常考性质
二叉树的定义及其性质
二叉树的表示
二叉树遍历
树和森林的概念
树的定义:树是一种非线性的数据结构,它由节点(node)和边(edge)组成。树的基本概念是以层次结构来组织和表示数据。
在树中,有一个特殊的节点被称为根节点(root),它是树的顶层节点,所有其他节点都直接或间接地与根节点相连。除了根节点外,每个节点可以有零个或多个子节点(child),子节点又可以有自己的子节点,形成了树的分支结构。没有子节点的节点被称为叶节点(leaf)或叶子节点,它们位于树的最底层。节点之间的连接称为边,边描述了节点之间的关系。每个节点可以有零条到多条边连接到其子节点。任意两个节点之间都存在唯一的路径,通过路径可以从一个节点到达另一个节点。
树的结构具有以下特点:
- 一个树可以由零个或多个节点组成。
- 有且只有一个根节点,它是树的起点。
- 每个节点可以有零个或多个子节点。
- 节点之间通过边相连,形成层次结构。
- 每个节点除了根节点外,都有且只有一个父节点。
树的基本术语:
结点之间的关系描述
根节点(Root Node):树的顶层节点称为根节点。根节点是树的起点,它没有父节点,其他所有节点都直接或间接地与根节点相连。
祖先节点(Ancestor Node):对于一个节点,它的所有上级节点(包括父节点、父节点的父节点等等)都被称为该节点的祖先节点。
子孙节点(Descendant Node):对于一个节点,它的所有下级节点(包括子节点、子节点的子节点等等)都被称为该节点的子孙节点。
父节点(Parent Node):一个节点的直接上一级节点称为其父节点。每个节点都可以有零个或多个子节点,但只能有一个父节点(除了根节点)。
子节点(Child Node):一个节点直接连接的下一级节点称为其子节点。一个节点可以有零个或多个子节点。
兄弟节点(Sibling Node):具有相同父节点的节点称为兄弟节点。兄弟节点在同一层级上。
叶节点(Leaf Node):也称为叶子节点,是没有子节点的节点,位于树的最底层。
层级(Level):根节点在第一层,其直接子节点在第二层,以此类推。一个节点所在的层级数即为该节点的层级。
结点、树的属性描述
节点值(Node Value):每个节点都可以携带一个值或数据,表示该节点所代表的实际含义或信息。
节点深度(Node Depth):节点深度指的是该节点到根节点的路径长度,即从根节点到该节点所经过的边的数量。根节点的深度为0。
节点高度(Node Height):节点高度指的是该节点到其最远叶节点的路径长度,即从该节点到达最远叶节点所经过的边的数量。叶节点的高度为0。
子树(Subtree):对于一个树中的节点,可以以该节点为根构成的子树称为该节点的子树。
树的大小(Tree Size):指的是树中包含的所有节点的总数。
树的高度(Tree Height):指的是树中任意节点的高度的最大值。也可以理解为从根节点到最远叶节点的路径长度的最大值。
有序树、无序树
有序树(Ordered Tree):有序树是指树中的子节点之间存在明确的顺序关系。在有序树中,每个子节点都有一个明确定义的位置,在遍历和表示树的时候需要按照顺序来考虑。例如,家谱树中的兄弟姐妹一般按照他们出生的先后顺序排列。
无序树(Unordered Tree):无序树是指树中的子节点之间没有明确的顺序关系。在无序树中,所有子节点都是平等的,没有先后之分。例如,文件系统中的目录结构就是一种无序树,其中的各个子目录之间没有特定的顺序。
有序树和无序树的区别在于子节点的排列方式。在有序树中,子节点的顺序很重要,会影响到树的结构和含义;而在无序树中,子节点的顺序并不重要,只需要知道它们是该节点的子节点即可。
森林
森林(Forest)是指由多棵树(Tree)组成的集合。简单来说,森林可以看作是多个独立的树的集合。
森林的特点在于其中的树之间是相互独立的,彼此之间没有直接的连接或关系。每棵树都可以独立地进行遍历和操作。
需要注意的是,森林和树的层次结构是不同的概念。树是一种层次结构,它具有唯一的根节点和从根节点到其他节点的确定路径;而森林则是多个独立的树的集合,在森林中任意两棵树之间没有直接的联系。
树的抽象数据类型:
树的抽象数据类型定义了对树进行操作的基本操作集合,包括以下常见操作:
1)创建树:创建一个空的树数据结构。
2)插入节点:在树中插入一个新节点,并建立节点之间的关系。
3)删除节点:从树中删除指定的节点,并调整节点之间的关系。
4)遍历树:按照特定的顺序访问树中的节点,例如先序遍历、中序遍历、后序遍历等。
5)查找节点:在树中查找指定的节点。
6)获取树的属性:获取树的高度、节点个数、根节点等属性信息。
树的抽象数据类型并不关注具体的实现方式,而是定义了可以对树进行的操作以及这些操作的预期行为。
回顾重点,其主要内容整理成如下内容:
树的常考性质
常见考点1:结点数 = 总度数 + 1
常见考点2:度为m的树、m叉树的区别
常见考点3:度为m的树第i层至多有 个结点 (i 1),同理m叉树第i层至多有 个结点 (i 1):
常见考点4:高度为h的m叉树至多有 个结点。
常见考点5:高度为h的m叉树至少有h个结点。高度为h度为m的树至少有h+m-1个结点。
常见考点6:具有n个结点的m叉树的最小高度为
高度最小的情况——所有结点都有m个孩子:
回顾重点,其主要内容整理成如下内容:
二叉树的定义及其性质
二叉树定义:
二叉树是n(n0)个结点的有限集合,其有以下两种情况:
1)为空二叉树,即 n = 0 的时候
2)由一个根结点和两个互不相交的被称为根的左子树和右子树组成。左子树和右子树又分别是一颗二叉树。
特点:每个结点至多只有两颗子树;左右子树不能颠倒。
二叉树的五种状态:
几个特殊的二叉树:
满二叉树:所有叶节点都在同一层,并且所有非叶节点都有两个子节点的二叉树称为满二叉树。
完全二叉树:除了最后一层节点之外,所有节点都拥有两个子节点,并且最后一层的节点都向左对齐的二叉树称为完全二叉树。
二叉排序树:(比如找关键字为60的结点)
平衡二叉树:树上任一结点的左子树和右子树的深度之差不超过1。
回顾重点,其主要内容整理成如下内容:
二叉树的常考性质:
常见考点1:设非空二叉树中度为0、1和2的结点个数分别为 ,则
叶子结点比二分支结点多一个
常见考点2:二叉树第i层至多有 个结点(i1);m叉树第i层至多有 个结点(i1)
常见考点3:高度为h的二叉树至多有 个结点(满二叉树)
高度为h的m叉树至多有 个结点
完全二叉树的常考性质:
常见考点1:具有n个(n>0)结点的完全二叉树的高度h为
或
常见考点2:对于完全二叉树,可以由结点数 n 推出度为 0、1和2的结点个数为、和
回顾重点,其主要内容整理成如下内容:
二叉树的表示
在数据结构中,二叉树可以通过数组表示和链表存储表示两种方式来实现。下面分别对这两种表示方式进行简述:
数组表示:
数组表示是将二叉树的节点按照某种方式存储在一个一维数组中。一般情况下,数组可以按照层次遍历的顺序存储二叉树的节点。假设根节点存储在数组下标为0的位置,那么对于任意一个节点的索引 i,其左子节点的索引为 2i+1,右子节点的索引为 2i+2。如果某个位置为空,可以使用特定的空值表示。
数组表示的优点:
数组表示的优点是存储简单,通过数组索引可以快速访问到任意节点。缺点是当二叉树的形状发生改变时,需要重新调整数组的大小,可能涉及到大量的元素移动。
#include <stdio.h>
#include <stdlib.h>
// 二叉树节点结构体
struct TreeNode {
int val;
struct TreeNode* left;
struct TreeNode* right;
};
// 构建二叉树的数组表示
struct TreeNode* build_binary_tree(int arr[], int size) {
struct TreeNode** tree = malloc(sizeof(struct TreeNode*) * size);
for (int i = 0; i < size; i++) {
if (arr[i] != -1) {
struct TreeNode* node = malloc(sizeof(struct TreeNode));
node->val = arr[i];
node->left = NULL;
node->right = NULL;
tree[i] = node;
} else {
tree[i] = NULL;
}
}
for (int i = 0; i < size; i++) {
if (tree[i] != NULL) {
if (2 * i + 1 < size)
tree[i]->left = tree[2 * i + 1];
if (2 * i + 2 < size)
tree[i]->right = tree[2 * i + 2];
}
}
struct TreeNode* root = tree[0];
free(tree);
return root;
}
// 测试代码
int main() {
int arr[] = {1, 2, 3, 4, 5, 6, 7};
int size = sizeof(arr) / sizeof(arr[0]);
struct TreeNode* root = build_binary_tree(arr, size);
// 输出测试结果
printf("root: %d\n", root->val);
printf("left child of root: %d\n", root->left->val);
printf("right child of root: %d\n", root->right->val);
return 0;
}
链表存储表示:
链表存储表示是使用链表的方式来表示二叉树。每个节点包含一个指向其父节点的指针,一个指向其左子节点的指针,一个指向其右子节点的指针。
链表存储表示的优点:
链表存储表示的优点是可以灵活地插入、删除节点而不需要移动其他节点,适用于频繁变化的二叉树结构。缺点是访问某个节点需要从根节点开始遍历,效率相对较低。
#include <stdio.h>
#include <stdlib.h>
// 二叉树节点结构体
struct TreeNode {
int val;
struct TreeNode* left;
struct TreeNode* right;
};
// 构建二叉树的链表存储表示
struct TreeNode* build_binary_tree(int arr[], int size) {
if (size == 0) {
return NULL;
}
struct TreeNode* root = malloc(sizeof(struct TreeNode));
root->val = arr[0];
root->left = NULL;
root->right = NULL;
struct TreeNode** queue = malloc(sizeof(struct TreeNode*) * size);
int front = 0;
int rear = 0;
queue[rear++] = root;
int i = 1;
while (i < size) {
struct TreeNode* node = queue[front++];
// 处理左子节点
if (arr[i] != -1) {
node->left = malloc(sizeof(struct TreeNode));
node->left->val = arr[i];
node->left->left = NULL;
node->left->right = NULL;
queue[rear++] = node->left;
}
i++;
// 处理右子节点
if (i < size && arr[i] != -1) {
node->right = malloc(sizeof(struct TreeNode));
node->right->val = arr[i];
node->right->left = NULL;
node->right->right = NULL;
queue[rear++] = node->right;
}
i++;
}
free(queue);
return root;
}
// 测试代码
int main() {
int arr[] = {1, 2, 3, 4, 5, 6, 7};
int size = sizeof(arr) / sizeof(arr[0]);
struct TreeNode* root = build_binary_tree(arr, size);
// 输出测试结果
printf("root: %d\n", root->val);
printf("left child of root: %d\n", root->left->val);
printf("right child of root: %d\n", root->right->val);
return 0;
}
二叉树遍历
遍历:按照某种次序把所有结点都访问一遍。根据二叉树的递归特性要么是个空二叉树,要么就是由“根结点+左子树+右子树”组成的二叉树
根据二叉树的三种遍历规则,相关的具体案例如下:
再进行具体的练习一遍:
回顾重点,其主要内容整理成如下内容:
二叉树的层序(次)遍历:
其相应的代码实现如下:
由遍历序列构造二叉树:
回顾重点,其主要内容整理成如下内容: 文章来源:https://www.toymoban.com/news/detail-716709.html
文章来源地址https://www.toymoban.com/news/detail-716709.html
到了这里,关于数据结构--》解锁数据结构中树与二叉树的奥秘(一)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!