微信小程序在线玩,十堰seo优化报价,做问卷调查的网站,塘下网站建设数据结构中的树与二叉树#xff0c;是在建立非线性数据结构方面极为重要的两个概念。它们不仅能够模拟出生活中各种实际问题的复杂关系#xff0c;还常被用于实现搜索、排序、查找等算法#xff0c;甚至成为一些大型软件和系统中的基础设施。 无论你是初学者还是进阶者… 数据结构中的树与二叉树是在建立非线性数据结构方面极为重要的两个概念。它们不仅能够模拟出生活中各种实际问题的复杂关系还常被用于实现搜索、排序、查找等算法甚至成为一些大型软件和系统中的基础设施。 无论你是初学者还是进阶者本文将为你提供简单易懂、实用可行的知识点帮助你更好地掌握树和二叉树在数据结构和算法中的重要性进而提升算法解题的能力。接下来让我们开启数据结构与算法的奇妙之旅吧。 目录
树和森林的概念
树的常考性质
二叉树的定义及其性质
二叉树的表示
二叉树遍历 树和森林的概念
树的定义树是一种非线性的数据结构它由节点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的树至少有hm-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个(n0)结点的完全二叉树的高度h为 或 常见考点2对于完全二叉树可以由结点数 n 推出度为 0、1和2的结点个数为、和 回顾重点其主要内容整理成如下内容 二叉树的表示
在数据结构中二叉树可以通过数组表示和链表存储表示两种方式来实现。下面分别对这两种表示方式进行简述 数组表示 数组表示是将二叉树的节点按照某种方式存储在一个一维数组中。一般情况下数组可以按照层次遍历的顺序存储二叉树的节点。假设根节点存储在数组下标为0的位置那么对于任意一个节点的索引 i其左子节点的索引为 2i1右子节点的索引为 2i2。如果某个位置为空可以使用特定的空值表示。 数组表示的优点 数组表示的优点是存储简单通过数组索引可以快速访问到任意节点。缺点是当二叉树的形状发生改变时需要重新调整数组的大小可能涉及到大量的元素移动。 #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;
}
二叉树遍历
遍历按照某种次序把所有结点都访问一遍。根据二叉树的递归特性要么是个空二叉树要么就是由“根结点左子树右子树”组成的二叉树 根据二叉树的三种遍历规则相关的具体案例如下 再进行具体的练习一遍 回顾重点其主要内容整理成如下内容 二叉树的层序(次)遍历 其相应的代码实现如下 由遍历序列构造二叉树 回顾重点其主要内容整理成如下内容
