二叉排序树构造过程_满二叉树和完全二叉树的区别图解

二叉排序树构造过程_满二叉树和完全二叉树的区别图解《计算之魂》思考题2.2——二叉排序树思考题2.2Q1. 修改中序遍历算法2.2,将它变成先序遍历或者后序遍历算法。Q2. (二叉排序树)有这样一串数字,5,2,8,0,10,7,18,20,30,12,15,1,将它们建成一颗二叉排序树。二叉排序树满足下

《计算之魂》思考题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,则时间复杂度为
O(N) 。   接下来,我们要思考构建二叉排序树的时间复杂度。这本质上是一个排序的问题。最差的情况,原序列是完全有序的,则构造出的二叉树深度与序列长度相等;最好的情况则是可以构造出一个平衡二叉树,则二叉树的高度为
logN (以2为底)。   所以,此算法的时间复杂度在
O(N^2)
O(NlogN) 之间。   这样构筑的二叉树,对其进行中序遍历,可以将已知的一串数字进行排序。   因本人的能力有限,分析和解答难免有错误和疏漏的地方,欢迎各位学友批评指正~

2024最新激活全家桶教程,稳定运行到2099年,请移步至置顶文章:https://sigusoft.com/99576.html

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请联系我们举报,一经查实,本站将立刻删除。 文章由激活谷谷主-小谷整理,转载请注明出处:https://sigusoft.com/75777.html

(0)
上一篇 2024年 8月 4日
下一篇 2024年 8月 4日

相关推荐

关注微信