环球网站建设,网站程序设计,重庆合川企业网站建设联系电话,如何创建一个平台文章目录 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 二叉树链接存储5.2.4 二叉树的遍历 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 森林的定义 一个森林是0棵或多棵不相交非空树的集合通常是一个有序的集合。换句话说森林由多个树组成这些树之间没有交集且可以按照一定的次序排列。在森林中每棵树都是独立的具有根节点和子树树与树之间没有直接的连接关系。 森林是树的扩展概念它是由多个树组成的集合。在计算机科学中森林也被广泛应用于数据结构和算法设计中特别是在图论和网络分析等领域。
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.3一棵非空高度为 k ( k ≥ 0 ) k( k≥0) k(k≥0)的满二叉树(perfect binary tree)是有 2 k 1 − 1 2^{k1}-1 2k1−1个结点的二叉树。
5. 完全二叉树 定义5.4一棵包含 n n n个节点、高度为 k k k的二叉树 T T T当按层次顺序编号 T T T的所有节点对应于一棵高度为 k k k的满二叉树中编号由1至 n n n的那些节点时 T T T被称为完全二叉树complete binary tree。
满二叉树、完全二叉树性质及证明【数据结构】树与二叉树四满二叉树、完全二叉树及其性质
5.2.2 二叉树顺序存储 二叉树的顺序存储是指将二叉树中所有结点按层次顺序存放在一块地址连续的存储空间中详见 【数据结构】树与二叉树五二叉树的顺序存储初始化插入结点获取父节点、左右子节点等 顺序存储方式的优点是节省了存储空间同时访问结点也非常快速因为可以通过数组索引直接访问结点而不需要进行指针的跳转。然而顺序存储方式也有一些限制 空间浪费对于非完全二叉树顺序存储方式可能会浪费大量存储空间。因为顺序存储方式需要使用连续的存储空间来存储所有结点而非完全二叉树中存在许多空缺的位置这些位置将被浪费掉。 动态性差顺序存储方式需要提前确定二叉树的最大结点个数对于结点数不确定或者动态变化的情况下顺序存储方式不太适用。如果二叉树的结点数超过了预先分配的存储空间就需要重新分配更大的存储空间并进行数据迁移这会增加额外的开销。 插入和删除操作复杂对于顺序存储方式插入和删除操作比较复杂。当需要插入或删除一个结点时需要进行数据的移动和调整以保持完全二叉树的性质。这会导致较高的时间复杂度和额外的操作开销。 因此对于非完全二叉树或者需要频繁进行插入和删除操作的情况链式存储方式更为灵活和高效。
5.2.3 二叉树链接存储
【数据结构】树与二叉树六二叉树的链式存储
5.2.4 二叉树的遍历
今天写不完了占坑~
