《计算之魂》思考题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/96955.html
