《计算之魂》思考题2.2——二叉排序树 思考题2.2 Q1. 修改中序遍历算法2.2，将它变成先序遍历或者后序遍历算法。 Q2. （二叉排序树）有这样一串数字，5，2，8，0，10，7，18，20，30，12，15，1，将它们建成一颗二叉排序树。二叉排序树满足下面的条件： （1）如果左子树不为空，则左子树上所有的节点的值均小于树的根节点的值。同样，如果右子树不为空，则右子树上所有节点的值均大于树的根节点的值。 （2）左右子树本身也是二叉排序树。 对于上述数字，我们在建立二叉排序树时，先把第一个数字5放在根节点，然后扫描第二个数字2，由于它比根节点的数字5小，因此我们将它放在左子树中。接下来我们扫描第三个数字8，由于它比根节点的数字5大，因此我们将它放在右子树中。重复上述过程，我们可以建成完整的二叉排序树。请完成下面三个小问题： i：写一个算法完成上述操作。 ii：这个算法的复杂度是多少？ iii：用何种遍历方法得到的结果恰好把上面的一串数字排好序？ 一、思考过程 Q1容易实现，只要将遍历的优先级做一定的调整，便可以将中序遍历改为先序遍历和后序遍历。 Q2依然可以利用递归的思想进行解答。 （1）扫描第一个数字，作为根节点； （2）如果数据序列未扫描结束，则扫描下一个数据。该数字与根节点比较，若小于根节点，则与左子树比较，当左子树为空时，将数字插入到当前根节点左子树的位置；若大于根节点，则与右子树比较，当右子树为空时，将该数字插入到当前根节点右子树的位置。 （3）反复执行步骤（2），直至序列中所有的数字遍历完毕。 二、解题过程 用下面的伪代码表示二叉树的数据结构。 1、二叉树的前序遍历和后序遍历 树的深度优先遍历（中序遍历） 先序遍历 后序遍历 2、二叉排序树 计算这个算法的时间复杂度。 首先，我们要考虑遍历整个数据序列的时间复杂度。若序列长度为N，则时间复杂度为
。 接下来，我们要思考构建二叉排序树的时间复杂度。这本质上是一个排序的问题。最差的情况，原序列是完全有序的，则构造出的二叉树深度与序列长度相等；最好的情况则是可以构造出一个平衡二叉树，则二叉树的高度为 （以2为底）。 所以，此算法的时间复杂度在 和 之间。 这样构筑的二叉树，对其进行中序遍历，可以将已知的一串数字进行排序。 因本人的能力有限，分析和解答难免有错误和疏漏的地方，欢迎各位学友批评指正~
2024最新激活全家桶教程，稳定运行到2099年，请移步至置顶文章：https://sigusoft.com/99576.html
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。 文章由激活谷谷主-小谷整理,转载请注明出处：https://sigusoft.com/90600.html
