二进制搜索树如何创建？ [英] How binary search tree is created?

问题描述

假设我要说一个数组

  1 5 4 6 8 9 10 22 17 7 9 3 
  

我想从该数组创建一个二进制搜索树。我需要算法来理解这一点。

我已经阅读了与BST相关的其他内容，例如有序遍历 预购 后置订单，树木漫步，插入删除等

本书没有提供如何创建BST。在这里需要帮助

解决方案

如果您不关心树是否平衡，则很简单：

1. 将树的第一个元素作为头部。


2. 在数组上迭代。如果元素大于节点，则向左（重复左边的孩子的步骤），否则向右（重复右边孩子的步骤）。


3. 如果左边/右边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:

1. put the first element of the tree as the head.
2. 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).
3. 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.

这篇关于二进制搜索树如何创建？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！