旅游网站的网页设计素材,网络工程师做什么的,广州市线下教学,wordpress修改器文章目录 5.1 树的基本概念5.1.1 树的定义5.1.2 森林的定义5.1.3 树的术语5.1.4 树的表示 5.2 二叉树5.2.1 二叉树1. 定义2. 特点3. 性质引理5.1#xff1a;二叉树中层数为i的结点至多有 2 i 2^i 2i个#xff0c;其中 i ≥ 0 i \geq 0 i≥0。引理5.2#xff1a;高度为k的二叉… 文章目录 5.1 树的基本概念5.1.1 树的定义5.1.2 森林的定义5.1.3 树的术语5.1.4 树的表示 5.2 二叉树5.2.1 二叉树1. 定义2. 特点3. 性质引理5.1二叉树中层数为i的结点至多有 2 i 2^i 2i个其中 i ≥ 0 i \geq 0 i≥0。引理5.2高度为k的二叉树中至多有 2 k 1 − 1 2^{k1}-1 2k1−1个结点其中 k ≥ 0 k \geq 0 k≥0。引理5.3设T是由n个结点构成的二叉树其中叶结点个数为 n 0 n_0 n0度数为2的结点个数为 n 2 n_2 n2则有 n 0 n 2 1 n_0 n_2 1 n0n21。 4. 满二叉树5. 完全二叉树 5.2.2 二叉树顺序存储5.2.3 二叉树链接存储特点C语言实现 5.1 树的基本概念
5.1.1 树的定义
一棵树是结点的有限集合T 若T非空则 有一个特别标出的结点称作该树的根记为root(T)其余结点分成若干个不相交的非空集合T1, T2, …, Tm (m0)其中T1, T2, …, Tm又都是树称作root(T)的子树。 T 空时为空树记作root(T)NULL。
5.1.2 森林的定义
5.1.3 树的术语
父亲parent、儿子child、兄弟sibling、后裔descendant、祖先ancestor度degree、叶子节点leaf node、分支节点internal node结点的层数路径、路径长度、结点的深度、树的深度
参照前文【数据结构】树与二叉树一树森林的基本概念父亲、儿子、兄弟、后裔、祖先、度、叶子结点、分支结点、结点的层数、路径、路径长度、结点的深度、树的深度
5.1.4 树的表示
【数据结构】树与二叉树二树的表示C语言树形表示法、嵌套集合表示法、嵌套括号表示法 、凹入表示法
5.2 二叉树
5.2.1 二叉树
1. 定义 二叉树是一种常见的树状数据结构它由结点的有限集合组成。一个二叉树要么是空集被称为空二叉树要么由一个根结点和两棵不相交的子树组成分别称为左子树和右子树。每个结点最多有两个子结点分别称为左子结点和右子结点。
2. 特点 二叉树的特点是每个结点最多有两个子结点并且子结点的位置是有序的即左子结点在前右子结点在后。这种有序性使得二叉树在搜索、排序等算法中有广泛的应用。 在二叉树中根结点是整个树的起始点通过根结点可以访问到整个树的其他结点。每个结点都可以看作是一个独立的二叉树它的左子树和右子树也是二叉树。 二叉树可以是空树也可以是只有根结点的树或者是由多个结点组成的树。每个结点可以包含一个数据元素以及指向左子结点和右子结点的指针。 二叉树的形状可以各不相同它可以是平衡的或者不平衡的具体取决于结点的分布情况。在二叉树中每个结点的左子树和右子树都是二叉树因此可以通过递归的方式来处理二叉树的操作。
3. 性质
引理5.1二叉树中层数为i的结点至多有 2 i 2^i 2i个其中 i ≥ 0 i \geq 0 i≥0。
引理5.2高度为k的二叉树中至多有 2 k 1 − 1 2^{k1}-1 2k1−1个结点其中 k ≥ 0 k \geq 0 k≥0。
引理5.3设T是由n个结点构成的二叉树其中叶结点个数为 n 0 n_0 n0度数为2的结点个数为 n 2 n_2 n2则有 n 0 n 2 1 n_0 n_2 1 n0n21。
详细证明过程见前文【数据结构】树与二叉树三二叉树的定义、特点、性质及相关证明
4. 满二叉树
5. 完全二叉树
满二叉树、完全二叉树性质及证明【数据结构】树与二叉树四满二叉树、完全二叉树及其性质
5.2.2 二叉树顺序存储 二叉树的顺序存储是指将二叉树中所有结点按层次顺序存放在一块地址连续的存储空间中详见 【数据结构】树与二叉树五二叉树的顺序存储初始化插入结点获取父节点、左右子节点等 顺序存储方式的优点是节省了存储空间同时访问结点也非常快速因为可以通过数组索引直接访问结点而不需要进行指针的跳转。然而顺序存储方式也有一些限制 空间浪费对于非完全二叉树顺序存储方式可能会浪费大量存储空间。因为顺序存储方式需要使用连续的存储空间来存储所有结点而非完全二叉树中存在许多空缺的位置这些位置将被浪费掉。 动态性差顺序存储方式需要提前确定二叉树的最大结点个数对于结点数不确定或者动态变化的情况下顺序存储方式不太适用。如果二叉树的结点数超过了预先分配的存储空间就需要重新分配更大的存储空间并进行数据迁移这会增加额外的开销。 插入和删除操作复杂对于顺序存储方式插入和删除操作比较复杂。当需要插入或删除一个结点时需要进行数据的移动和调整以保持完全二叉树的性质。这会导致较高的时间复杂度和额外的操作开销。 因此对于非完全二叉树或者需要频繁进行插入和删除操作的情况链式存储方式更为灵活和高效。
5.2.3 二叉树链接存储 二叉树的链接存储系指二叉树诸结点被随机存放在内存空间中结点之间的关系用指针说明。在链式存储中每个二叉树结点都包含三个域数据域Data、左指针域Left和右指针域Right用于存储结点的信息和指向子结点的指针。具体结点的结构如下所示
struct BinaryTreeNode {DataType Data; // 数据域存放结点的信息BinaryTreeNode* Left; // 左指针域指向左子结点BinaryTreeNode* Right; // 右指针域指向右子结点
};在二叉树的链接存储中存在一个指向根结点的指针通常称为根指针。根指针用于访问整个二叉树。如果二叉树为空根指针将被设置为NULL即空指针。 叶结点是没有子结点的结点因此叶结点的左指针域和右指针域都会存放NULL表示没有左子结点和右子结点。 在包含n个结点的二叉树的链接存储中需要2n个指针域。其中n-1个指针域用于指示结点的左子结点和右子结点剩余的n1个指针域为空。这是因为树中的每个结点除了根结点都有一个父结点而父结点与子结点之间有两个指针域左指针域和右指针域相连所以总共需要2n个指针域。但是根结点没有父结点因此只有n-1个指针域用于指示结点的左子结点和右子结点。这个结论可以通过引理5.3E n-1**来证明。
特点
每个结点通过指针域与其左子结点和右子结点建立联系形成二叉树的结构。通过这种链接方式可以方便地遍历和操作二叉树。链式存储方式的优点是灵活性高适用于各种类型的二叉树无需提前确定结点个数适用于动态变化的情况。同时链式存储方式不要求连续的存储空间每个结点可以在内存中的任意位置通过指针的连接来表示结点之间的逻辑关系。然而链式存储方式也存在一些缺点。相比于顺序存储方式链式存储需要额外的指针开销每个结点都需要额外的指针域来存储指向子结点的指针。此外访问结点需要通过指针的跳转相对于顺序存储方式来说可能会稍微降低访问效率。
C语言实现
#include stdio.h
#include stdlib.h// 二叉树结点的定义
struct Node {char data;struct Node* left;struct Node* right;
};// 创建新结点
struct Node* createNode(int data) {struct Node* newNode (struct Node*)malloc(sizeof(struct Node));if (newNode NULL) {printf(Memory allocation failed!\n);exit(1);}newNode-data data;newNode-left NULL;newNode-right NULL;return newNode;
}int main() {// 创建一棵二叉树struct Node* root createNode(a);root-left createNode(b);root-right createNode(c);root-left-left createNode(d);root-left-right createNode(e);root-left-right-left createNode(f);root-left-right-right createNode(g);return 0;
}
