依次插入结点法生成二叉排序树是什么意思?

来源：千锋教育

发布人：xqq

时间： 2023-10-14 13:44:59

一、依次插入结点法生成二叉排序树

依次插入结点法生成二叉排序树是指利用逐点插入法建立一组序列对应的二叉排序树。例如利用逐点插入法建立序列（50，72，43，，85，75，20， 35，45，64，30）对应的二叉排序树。

1、名列前茅个数字50，作为根节点
（所有数字都要先跟50比，大的放右侧，小的放左）
2、第二个数字72和50比，大于50，分叉分到右侧
3、第三个数字43跟50比，小于50，分叉分到左侧
4、85先跟50比，应该归到右侧，但是右侧已经有了一个72了，85位置跟72重复了，所以要把冲突的位置作为节点继续分叉，因此跟72比较以后，85大于72，分叉到72的右侧
5、75同理，先跟50比，应该在右，再跟72比，在右，再跟85比，在左
6、20跟50比，放到左侧，左侧有了43，因此位置重复，要把43作为节点继续分叉，20小于43，因此放在43分叉后的左侧
7、35跟50比，放到左侧，但是有了43，继续分叉，应该放在43分叉后的左侧，但是这个位置有了20，所以要以20为节点继续分叉，分叉后大于20，放在20下方的右侧。
8、45跟50比，小于50，放在左侧，左侧有了43，继续分叉，因为大于43，因此放在43的右侧，跟20一排
9、64和30同理类推，最终答案图示如下：
。。。。。。。。。 50
。。。。。。。 / 。。。 \
。。。。。。43 。。。。72

延伸阅读：

二、二叉排序树

二叉排序树（Binary Sort Tree或 Binary Search Tree）又称二叉查找树，可以用来实现数据的快速查找，也方便数据的插入、删除等工作，因此适用于数据的动态查找。

二叉排序树是一棵二叉树，其左子树上的元素都小于树根，右子树上的元素都大于树根，所有的子树也满足这个性质。

要想实现二叉排序树的查找，需要事先已经建立了二叉排序树。其原理很简单，如果已知一个数组，则首先把数组的名列前茅个元素存储到树根。读入第二个元素的时候需要和树根进行比较，比树根小则存到左子树，否则存到右子树。读入第三个元素时，依旧先和树根进行比较，如果大于树根元素，则存入右子树，否则就与当前左子树树根进行比较，小的话则存入左子树的左子树。以后读入其它元素也是如此操作，就可以创建一棵二叉排序树。

声明：本站稿件版权均属千锋教育所有，未经许可不得擅自转载。