C++高级数据结构之二叉查找树怎么实现

本文小编为大家详细介绍“C++高级数据结构之二叉查找树怎么实现”，内容详细，步骤清晰，细节处理妥当，希望这篇“C++高级数据结构之二叉查找树怎么实现”文章能帮助大家解决疑惑，下面跟着小编的思路慢慢深入，一起来学习新知识吧。此数据结构由结点组成，结点包含的链接可以为空（null）或者指向其他结点。在二叉树中，每个结点只能有一个父结点（只有一个例外，也就是根结点，它没有父结点），而且每个结点都只有左右两个链接，分别指向自己的左子结点和右子结点。每个结点的两个链接都指向了一棵独立的子二叉树或空链接。在二叉查找树中，每个结点还包含了一个键和一个值，键之间也有顺序之分以支持高校的查找。定义：一棵二叉查找树（BST）是一棵二叉树，
其中每个结点都含有一个Comparable的键（以及相关联的值）
且每个结点的键都大于其左子树中的任意结点的键而小于右子树的任意结点的键。以int类型为键，string类型为值的二叉查找树的API如下：我们嵌套定义一个私有类来表示二叉查找树上的一个结点免费云主机域名。每个结点都含有一个键、一个值、一条左链接、一条右链接和一个结点计数器。左链接指向一棵由小于该结点的所有键组成的二叉查找树，右链接指向一棵由大于该结点的所有键组成的二叉查找树。变量N给出了以该结点为根的子树的结点总数。实现：一棵二叉查找树代表了一组键（及其相应的值）的集合，而同一个集合可以用多棵不同的二叉查找树表示。如果我们将一棵二叉查找树的所有键投影到一条直线上，保证一个结点的左子树中的键出现在它的左边，右子树中的键出现在它的右边，那么我们一定可以得到一条有序的键列。一般来说，在符号表中查找一个键可能得到两种结果。如果含有该键的结点存在于表中，我们的查找就命中了，然后返回相应的值。否则查找未命中（并返回null）。根据数据表示的递归结构我们马上就能得到，在二叉查找树中查找一个键的递归算法：如果树是空的，则查找未命中；如果被查找的键和根结点的键相等，查找命中，否则我们就（递归地）在适当的子树中继续查找。如果被查找的键较小就选择左子树，较大则选择右子树。二叉查找树插入的实现难度和查找差不多。如果树是空的，就返回一个含有该键值对的新结点；如果被查找的键小于根结点的键，继续在左子树中搜索插入该键，否则在右子树中插入该键。二叉查找树得以广泛应用的一个重要原因就是它能够保持键的有序性，因此它可以作为实现有序符号表API中的众多方法的基础。这使得符号表的用例不仅能够通过键还能通过键的相对顺序来访问键值对。如果根节点的左链接为空，那么一棵二叉查找树中最小的键就是根结点；如果左链接非空，那么树中的最小键就是左子树中的最小键，显示可以由递归操作实现。找出最大键的方法也是类似的，只不过是变为查找右子树而已。最小键最大键如果给定的键key小于二叉查找树的根结点的键，那么小于等于key的最大键floor(key)一定在根结点的左子树中；如果给定的键key大于二叉查找树的根结点，那么只有当根结点右子树中存在小于等于key的结点时，小于等于key的最大键才会出现在右子树中，否则根结点就是小于等于key的最大键。这段描述说明了floor()方法的递归实现，同时也递推地证明了它能够计算出预期的结果。将“左”变为“右”（同时将小于变为大于）就能够得到ceiling()的算法。向下取整向上取整二叉查找树的选择操作和基于切分的数组选择操作类似。我们在二叉查找树中的每个结点中维护的子树结点计数器变量N就是用来支持此操作的。rank()方法是select()方法的逆方法，它会返回给定键的排名。它的实现和select()类似：如果给定的键和根结点的键相等，我们返回左子树中的结点总数t；如果给定的键小于根结点，我们会返回该键在左子树中的排名（递归计算）；如果给定的键大于根结点，我们会返回t+1（根结点）加上它在右子树中的排名（递归计算）。要实现能够返回给定范围键的keys()方法，我们首先需要一个遍历二叉查找树的基本方法，为中序遍历。要说明这个方法，我们先看看如何能够将二叉查找树中的所有键按照顺序打印出来。要做到这一点，我们应该先打印出根结点的 左子树中的所有键（根据二叉查找树的定义它们应该都小于根结点的键），然后打印出根结点的键，最后打印出根结点的右子树中的所有键（根据二叉查找树的定义它们应该都大于根结点的键）。二叉查找树中最难实现的方法就是delete()方法，即从符号表中删除一个键值对。在此之前，我们先考虑deleteMin()方法（删除最小键所对应的键值对）。对于deleteMin()，我们要不断深入根节点的左子树直至遇见一个空链接，然后将指向该结点的右子树（只需要在递归调用中返回它的右链接即可）。此时它会被垃圾收集器清理掉。我们给出的标准递归代码在删除结点后会正确地设置它的父结点的链接并更新它到根结点的路径上的所有结点的计数器的值。deletemax()方法的实现和deletemin()完全类似，相应地，只需删除右子树最右端结点，然后返回其最右端结点的左子树即可。将指向即将被删除的结点的链接保存为t;将x指向它的后继结点min(t.right);将x的右链接（原本指向一棵所有结点都大于x.key的二叉查找树）指向deleteMin(t.right)，也就是在删除后所有结点仍然都大于x.key的子二叉查找树；将x的左链接（本为空）设为t.left（其下所有的键都小于被删除的结点和它的后继结点）。实现：我见过二叉查找树，但它的实现没有使用递归。这两种方式各有哪些优缺点？
答：一般来说，递归的实现更容易验证其正确性，而非递归的实现效率更高。创建树的键为：
1 2 3 4 5 6 7 8 9 10
创建树的大小为：10
键3所对应的值为：C
最小键为：1
最大键为: 10
小于等于11的最大键是：10
大于等于0的最小键是: 1
排名为5的键是：5
键7的排名是：7
键值在3-8之间的键有：
3 4 5 6 7 8
删除最小键和最大键后的键值为：
2 3 4 5 6 7 8 9
删除键4后的键值为：
2 3 5 6 7 8 9
Process finished with exit code 0读到这里，这篇“C++高级数据结构之二叉查找树怎么实现”文章已经介绍完毕，想要掌握这篇文章的知识点还需要大家自己动手实践使用过才能领会，如果想了解更多相关内容的文章，欢迎关注百云主机行业资讯频道。

相关推荐: MySQL分库分表实例分析

这篇“MySQL分库分表实例分析”文章的知识点大部分人都不太理解，所以小编给大家总结了以下内容，内容详细，步骤清晰，具有一定的借鉴价值，希望大家阅读完这篇文章能有所收获，下面我们一起来看看这篇“MySQL免费云主机域名分库分表实例分析”文章吧。数据库架构演变刚…