wordpress写的文章代码显示方式,百度关键词优化服务,wordpress文章列表调用描述,网站砍价活动怎么做一、二叉树的基本概念 二叉树是数据结构中的重要概念#xff0c;每个节点最多有两个子树#xff0c;分别为左子树和右子树。这种结构具有明确的层次性和特定的性质。
二叉树有五种基本形态#xff1a;
空二叉树#xff1a;没有任何节点。只有一个根结点的二叉树#xff…一、二叉树的基本概念 二叉树是数据结构中的重要概念每个节点最多有两个子树分别为左子树和右子树。这种结构具有明确的层次性和特定的性质。
二叉树有五种基本形态
空二叉树没有任何节点。只有一个根结点的二叉树仅有一个节点作为整个树的根。只有左子树根节点仅存在左子树右子树为空。只有右子树根节点仅存在右子树左子树为空。完全二叉树除最后一层外每一层的节点数都是最大的最后一层的节点尽可能靠左排列。 完全二叉树具有一些特点例如叶子结点只可能出现在层序最大的两层上并且某个结点的左分支下子孙的最大层序与右分支下子孙的最大层序相等或大 1。此外满二叉树也是一种特殊的二叉树除了叶结点外每一个结点都有左右子叶且叶子结点都处在最底层。平衡二叉树则是左右两个子树的高度差的绝对值不超过 1并且左右两个子树都是一棵平衡二叉树。 二叉树作为一种数据结构在实际问题中具有广泛的应用。许多实际问题抽象出来的数据结构往往是二叉树形式因为二叉树的存储结构及其算法都较为简单。例如在计算机科学中的搜索算法、排序算法等领域二叉树都发挥着重要的作用。 尽管二叉树与树有许多相似之处但二叉树不是树的特殊情形。树中结点的最大度数没有限制而二叉树结点的最大度数为 2树的结点无左、右之分而二叉树的结点有左、右之分。 二、二叉树的特殊类型
一满二叉树 满二叉树是一种特殊形态的二叉树。定义为除最后一层无任何子节点外每一层上的所有结点都有两个子结点叶子结点都在最下层没有度为 1 的结点。其特点包括
每层的结点数都达到最大所有叶子结点必须在同一层上。如果一颗树深度为 h最大层数为 k它的叶子数是 2^(h - 1)第 k 层的结点数是 2^(k - 1)总结点数是 2^k - 1总节点数一定是奇数。
二完全二叉树 完全二叉树是由满二叉树引出来的。对于深度为 K 的有 n 个结点的二叉树当且仅当其每一个结点都与深度为 K 的满二叉树中编号从 1 至 n 的结点一一对应时称之为完全二叉树。其特点如下
叶子结点只可能在最大的两层上出现。若 i≤⌊n/2⌋则结点 i 为分支结点否则为叶子结点。对于最大层次中的叶子结点都依次排列在该层最左边的位置上。若有度为 1 的结点则只可能有一个且该结点只有左孩子而无右孩子。按层序编号后一旦出现某结点为叶子结点或只有左孩子则编号大于 i 的结点均为叶子结点。若 n 为奇数则每个分支结点都有左孩子和右孩子若 n 为偶数则编号最大的分支结点只有左孩子没有右孩子其余分支结点左、右孩子都有。
三平衡二叉树
平衡二叉树又被称为 AVL 树具有以下定义及性质
它是一棵空树或它的左右两个子树的高度差的绝对值不超过 1并且左右两个子树都是一棵平衡二叉树。平衡二叉树的常用实现方法有红黑树、AVL、替罪羊树、Treap、伸展树等。在平衡二叉搜索树中高度一般都良好地维持在 Ologn大大降低了操作的时间复杂度。常见的算法有红黑树、AVL、Treap、伸展树等。红黑树可以在 O (log n) 时间内做查找插入和删除AVL 树中任何节点的两个儿子子树的高度最大差别为一n 个结点的 AVL 树最大深度约 1.44log2nTreap 是一棵二叉排序树它的左子树和右子树分别是一个 Treap同时满足堆的性质伸展树能在 O (log n) 内完成插入、查找和删除操作。
三、二叉树的性质
二叉树具有多种重要性质这些性质对于理解和操作二叉树至关重要。
一节点总数与深度关系 对于一棵深度为 k 的二叉树最多具有 个结点最少有 k 个结点。这是因为每一层的节点数是上一层的两倍深度为 k 的满二叉树的节点总数为 。而对于非满二叉树其节点总数会小于这个值但至少有 k 个结点因为每一层至少有一个结点。
二叶子结点与度为 2 的结点关系 对于任何一棵二叉树如果其叶结点数为 度为 2 的结点数为 则有 。证明如下如果 表示度为 0即叶子结点的结点数用 表示度为 1 的结点数 表示度为 2 的结点数n 表示整个完全二叉树的结点总数则有 。根据二叉树和树的性质可知 所有结点的度数之和加 1 等于结点总数。根据两个等式可知 即 也即 。
三完全二叉树的深度性质 具有 n个结点的完全二叉树的深度为 ⌊log2n⌋ 1。证明根据性质 2深度为 k的二叉树最多有 2^k - 1个结点且完全二叉树的定义是与同深度的满二叉树前边的编号相同即它们的结点总数n 位于 k层和 k-1层的满二叉树容量之间即 2^{k - 1} - 1 n 2^k - 1之间或 2^{k - 1} n 2^k两边同时取对数得k - 1 log2(n) k 又因层数为整数故log2(n)k - 1 即 k log2(n)1。 这些性质在实际应用中非常有用例如在计算二叉树的节点数量、判断二叉树的结构特点等方面。了解这些性质可以帮助我们更好地理解和使用二叉树这种数据结构。
四、二叉树的存储结构
一顺序存储结构 顺序存储结构是指用一组地址连续的存储单元依次自上而下、自左至右存储完全二叉树上的结点元素。对于完全二叉树来说顺序存储是十分合适的因为完全二叉树的节点可以按照层次编号依次存储在数组中通过节点的编号可以快速确定其在数组中的位置进而方便地找到其双亲、左右孩子节点。 在完全二叉树的顺序存储中数组的下标与节点的编号有直接对应关系。例如对于一个深度为 的完全二叉树其节点总数最多为 。如果节点编号从 开始那么根节点存储在数组下标为 的位置节点 的左孩子存储在下标为 的位置右孩子存储在下标为 的位置节点 的双亲节点存储在下标为 的位置。 然而顺序存储结构也有明显的优缺点。优点包括索引计算简单通过节点在数组中的索引可以快速计算出其父节点、左子节点和右子节点的索引不需要进行指针操作提高了访问效率存储紧凑相比于链式存储顺序存储不需要额外的指针空间节省了存储空间遍历方便由于节点在数组中的顺序与遍历顺序一致可以方便地进行层次遍历、前序遍历、中序遍历和后序遍历等操作。 缺点主要有空间浪费如果二叉树是一棵稀疏树即节点较少那么顺序存储会造成大量的空间浪费因为数组中会有很多位置被空节点占据插入和删除操作复杂由于顺序存储需要保持二叉树的完全二叉树结构插入和删除节点时需要进行大量的数据搬移操作效率较低高度限制顺序存储的数组长度是固定的因此对于高度较大的二叉树可能会导致数组长度不够无法存储完整的二叉树。
二链式存储结构
1.二叉链表 二叉链表是二叉树的一种常见链式存储结构。在二叉链表中每个节点包含三个域数据域、左指针域和右指针域。当左孩子或右孩子不存在时相应指针域值为空。 二叉链表的特点是除了指针外二叉链比较节省存储空间。占用的存储空间与树形没有关系只与树中节点个数有关。在二叉链中找一个节点的孩子很容易但找其双亲不方便。 二叉链表适用于各种类型的二叉树尤其是那些非完全二叉树。在实际应用中二叉链表常用于二叉树的遍历、查找、插入和删除等操作。例如在二叉树的遍历中可以通过递归或非递归的方式遍历二叉链表实现对二叉树中每个节点的访问。
2.三叉链表 三叉链表是二叉树链式存储结构的另一种形式。三叉链表与二叉链表的主要区别在于它的节点比二叉链表的节点多一个指针域该域用于存储指向本节点双亲的指针。 在三叉链表中每个结点由四个域组成其中data、lchild 以及 rchild 三个域的意义与二叉链表结构相同。这种存储结构既便于查找孩子结点又便于查找双亲结点。但是相对于二叉链表存储结构而言它增加了空间开销。 三叉链表适用于需要频繁查找双亲节点的场景。例如在某些算法中需要快速找到某个节点的双亲节点进行操作此时三叉链表就可以发挥其优势。不过由于其增加了空间开销在空间有限的情况下需要权衡使用。
五、二叉树的遍历方式
一先序遍历 先序遍历的顺序是根左右即先访问根节点再访问左子树最后访问右子树。
在 C 语言中先序遍历可以通过递归和非递归两种方式实现。
1.递归实现
// 前序遍历二叉树的函数假设 BiTree 是一个二叉树类型
void preOrder(BiTree T) {// 如果当前节点不为空if (T! NULL) {// 调用 visit 函数访问当前节点visit 函数应该是一个自定义的用于处理节点的函数visit(T);// 递归遍历左子树preOrder(T-lchild);// 递归遍历右子树preOrder(T-rchild);}// 函数返回结束遍历return;
}
2.非递归实现借助栈实现先将根节点入栈当栈不为空时取出栈顶元素并访问然后将其右孩子和左孩子依次入栈如果存在。
// 非递归实现前序遍历二叉树的函数假设 BiTree 是一个二叉树类型
void preOrderNonRecursive(BiTree T) {// 创建一个栈Stack stack;// 初始化栈initStack(stack);// 将根节点入栈push(stack, T);// 当栈不为空时循环while (!isEmpty(stack)) {// 弹出栈顶元素BiTree node pop(stack);// 如果弹出的节点不为空if (node! NULL) {// 访问该节点visit(node);// 先将右子树入栈因为先访问左子树后访问右子树push(stack, node-rchild);// 再将左子树入栈push(stack, node-lchild);}}
}
二中序遍历
中序遍历的顺序是左根右即先访问左子树再访问根节点最后访问右子树。
C 语言实现方式如下
1.递归实现
// 中序遍历二叉树的函数假设 BiTree 是一个二叉树类型
void midOrder(BiTree T) {// 如果当前节点不为空if (T! NULL) {// 先递归遍历左子树midOrder(T-lchild);// 访问当前节点visit(T);// 再递归遍历右子树midOrder(T-rchild);}// 函数返回结束遍历return;
}
2.非递归实现借助栈实现从根节点开始将其所有左孩子依次入栈直到左孩子为空。然后弹出栈顶元素并访问接着将其右孩子作为新的根节点重复上述过程。
// 非递归实现中序遍历二叉树的函数假设 BiTree 是一个二叉树类型
void midOrderNonRecursive(BiTree T) {// 创建一个栈Stack stack;initStack(stack);// 设置当前节点为传入的根节点BiTree node T;// 当当前节点不为空或者栈不为空时循环while (node! NULL ||!isEmpty(stack)) {if (node! NULL) {// 当前节点不为空时将其入栈并将当前节点移动到左子节点push(stack, node);node node-lchild;} else {// 当前节点为空说明左子树已遍历完从栈中弹出一个节点node pop(stack);// 访问该节点visit(node);// 将当前节点移动到右子节点node node-rchild;}}
}
三后序遍历
后序遍历的顺序是左右根即先访问左子树再访问右子树最后访问根节点。
C 语言代码实现
1.递归实现
// 后序遍历二叉树的函数假设 BiTree 是一个二叉树类型
void afterOrder(BiTree T) {// 如果当前节点不为空if (T! NULL) {// 先递归遍历左子树afterOrder(T-lchild);// 再递归遍历右子树afterOrder(T-rchild);// 最后访问当前节点visit(T);}// 函数返回结束遍历return;
}
2.非递归实现借助栈实现需要额外使用一个辅助栈来记录遍历顺序。先将根节点入栈然后依次将其右孩子和左孩子入栈如果存在。当栈为空时遍历结束。最后将辅助栈中的元素依次弹出并访问得到后序遍历结果。
// 非递归实现后序遍历二叉树的函数假设 BiTree 是一个二叉树类型
void afterOrderNonRecursive(BiTree T) {// 创建两个栈 stack1 和 stack2Stack stack1, stack2;// 初始化 stack1initStack(stack1);// 初始化 stack2initStack(stack2);// 将根节点入栈 stack1push(stack1, T);// 当 stack1 不为空时循环while (!isEmpty(stack1)) {// 从 stack1 弹出一个节点BiTree node pop(stack1);// 将弹出的节点入栈 stack2push(stack2, node);// 如果当前节点的左子树不为空将左子树入栈 stack1if (node-lchild! NULL) {push(stack1, node-lchild);}// 如果当前节点的右子树不为空将右子树入栈 stack1if (node-rchild! NULL) {push(stack1, node-rchild);}}// 当 stack2 不为空时循环while (!isEmpty(stack2)) {// 从 stack2 弹出一个节点并访问visit(pop(stack2));}
}
四层次遍历 层次遍历是从上层至下层同层自左至右遍历。借助队列实现先将根节点入队然后当队列不为空时取出队首元素并访问接着将其左孩子和右孩子依次入队如果存在直到队列为空。
C 语言代码如下
// 层次遍历二叉树的函数假设 BiTree 是一个二叉树类型
void levelOrder(BiTree T) {// 创建一个队列Queue queue;// 初始化队列initQueue(queue);// 将根节点入队enqueue(queue, T);// 当队列不为空时循环while (!isEmptyQueue(queue)) {// 从队列中取出一个节点BiTree node dequeue(queue);// 如果取出的节点不为空if (node! NULL) {// 访问该节点visit(node);// 将该节点的左子节点入队enqueue(queue, node-lchild);// 将该节点的右子节点入队enqueue(queue, node-rchild);}}
}
六、二叉树的应用场景 二叉树在计算机科学领域有广泛的应用场景以下是对其在不同领域的具体介绍
一哈夫曼编码 哈夫曼编码是一种使用二叉树特别是赫夫曼树实现的数据压缩方法。它通过构建一个带权路径长度最短的二叉树即最优二叉树来提高数据传输的有效性。具体步骤如下
首先将待编码的文章当成一个字符串遍历这个字符串中所有的字符并且统计每一个字符出现的次数。根据字符出现的次数对字符进行排序。选取排序后出现次数最少的两个字符加入哈夫曼树并将两个字符的出现次数取值相加合并成为一个中间节点。中间节点仅记录两个节点取值的加和但是不记录任何字符。将中间节点加入字符排序序列中删除已经使用过的节点对序列重新排序重复步骤 2 - 4构建过程中产生的中间节点也算作在内。当所有的字符和中间节点全部合成完毕时序列中只剩余一个节点就是哈夫曼树的根节点哈夫曼树创建完毕。 接着为每一个存储字符的节点分配哈夫曼编码从根节点开始向下寻找每一个叶子节点如果向左孩子方向走一步则记 0如果向右孩子方向走一步则记 1重复上述步骤直到遍历完成整个哈夫曼树为止最终得到根节点通往每一个叶子节点的路径字符串就是这个叶子节点对应字符的哈夫曼编码。 例如一篇文章经过哈夫曼编码后完全由 0 和 1 构成且每一篇文章因为内容的不同即使是相同的字符所对应的哈夫曼编码也是不同的。所以即使单纯得到一篇文章的密文结构没有得到对应的哈夫曼编码表也是无法进行解密的。哈夫曼树和哈夫曼编码在密码学当中具有非常高的学术研究价值。
二海量数据并发查询 在处理大量动态数据时二叉排序树二叉查找树因其既有链表的好处也有数组的好处能够在处理大批量的动态数据时提供高效的查询性能。这种数据结构在复杂度为 O (K LgN) 的情况下对于海量数据的并发查询非常有用。 例如在一些需要处理大量实时数据的系统中如金融交易系统、网络流量监测系统等二叉排序树可以快速地对数据进行查找和插入操作满足系统对数据处理的实时性要求。
三数据结构实现 C STL 中的 set/multiset、map 以及 Linux 虚拟内存的管理都是通过红黑树实现的。红黑树能够在查找、插入和删除操作中保持相对平衡提供高效的查找效率最大查找 / 删除 / 插入操作的时间复杂度为 O (logk)。 红黑树是一种自平衡的二叉查找树它在插入和删除操作后通过旋转和翻色自动调整结构以保持平衡从而保证了查找、插入和删除操作的效率。在内存中的有序数据存储中红黑树可以快速地进行增删操作且由于内存存储不涉及 I/O 操作红黑树的性能优势更加明显。此外红黑树还适用于实现 Key - Value 对的数据结构通过键值对进行查找适用于需要快速查找特定键值对应的值的应用场景。
四文件系统 B - Tree 和 B - Tree 在文件系统中有着重要的应用特别是在目录管理上。它们能够高效地处理大量的数据并提供快速的查找、插入和删除操作这对于文件系统的性能至关重要。 B 树只在叶节点存储数据而非叶子节点只存储索引信息。这种结构使得 B 树能够更好地适应磁盘读取方式因为在磁盘上读取一条记录的成本非常高。B 树的叶节点形成了一个链表可以很容易地实现范围查询非常适合需要高效处理大量数据的系统。此外B 树相比 B 树有更好的空间利用率和查询性能更适合用作大型数据库的索引结构。B 树的所有数据记录都存储在叶子节点上且叶子节点同时还维护了一条双向链表这提高了范围查询的效率。因此B 树在需要处理大量范围查询和排序操作的场景中表现出色如文件系统等。
五路由搜索引擎 路由器使用二叉树结构进行路由表的查找这种结构能够快速地根据目的地址查找最佳的路由路径从而提高网络通信的效率。 例如在互联网中路由器需要根据数据包的目的地址快速地选择最佳的路由路径将数据包转发到正确的目的地。二叉树结构可以有效地组织路由表使得路由器能够快速地进行查找和决策提高网络通信的效率和可靠性。
