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