本文介绍了二进制搜索树如何创建?的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!
问题描述
假设我要说一个数组
1 5 4 6 8 9 10 22 17 7 9 3
我想从该数组创建一个二进制搜索树。我需要算法来理解这一点。
我已经阅读了与BST相关的其他内容,例如有序遍历
预购
后置订单
,树木漫步
,插入删除
等
本书没有提供如何创建BST。在这里需要帮助
解决方案
如果您不关心树是否平衡,则很简单:
- 将树的第一个元素作为头部。
- 在数组上迭代。如果元素大于节点,则向左(重复左边的孩子的步骤),否则向右(重复右边孩子的步骤)。
- 如果左边/右边child是空值,在其中插入新值。
保证生成二叉搜索树-只是不平衡。 >
Suppose i am having an array say
1 5 4 6 8 9 10 22 17 7 9 3
I want to create a binary search tree from this array. I need algorithm to understand that.
I have read rest other things related to BST like inorder traversal
preorder
postorder
, tree walk
, insertion deletion
etc
Book has not provided how to create BST. Need help here
解决方案
if you do not care about the tree being balanced it is simple:
- put the first element of the tree as the head.
- iterate over the array. if an element is bigger than the node take a left(repeat the step for the left child) otherwise take a right(repeat the step for the right child).
- if the left/right child is a null insert your new value there.
guaranteed to produce a binary search tree - just not a balanced one.
这篇关于二进制搜索树如何创建?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!