出一组数据:10、18、3、4、9、13、15、2、21、7、8,将它们生成一棵二叉排序树,所需的关键码的比较次数为具体怎么做...
来源：学生作业帮助网 编辑：六六作业网 时间：2024/12/20 04:26:07
出一组数据:10、18、3、4、9、13、15、2、21、7、8,将它们生成一棵二叉排序树,所需的关键码的比较次数为具体怎么做...
出一组数据:10、18、3、4、9、13、15、2、21、7、8,将它们生成一棵二叉排序树,所需的关键码的比较次数为
具体怎么做...
出一组数据:10、18、3、4、9、13、15、2、21、7、8,将它们生成一棵二叉排序树,所需的关键码的比较次数为具体怎么做...
10
/ \
3 18
/ \ / \
2 4 13 21
\ \
9 15
/
7
\
8
插入的结果如上
其实二叉排序树很简单,他必须满足一个条件,即父节点的值大于左边孩子的值,且小于右边孩子的值.
每次插入的时候,都必须于当前节点比较,如果大于当前节点,则与右子节点进行比较,如果小于当前节点,则与左子节点比较,一直比较下去,直到不存在左子节点或右子节点,则把新节点插入到不存在的位置.
如
第1步：插入10 不用比较,10为根节点
树：10
第2步：插入18 从根节点开始与10 比较(总比较次数1),比10大,所以接着与10的右子节点比较,由于10没有右子节点,因此把18 插入到10 的右子节点中
树：10
\
18
第3步：插入3 从根节点开始与10 比较(总比较次数2),比10小,所以接着与10的左子节点比较,由于10没有左子节点,因此把3 插入到10 的左子节点中
树：10
/ \
3 18
第4步：插入4 从根节点开始与10 比较,比10小,所以接着与10的左子节点比较(总比较次数3),10的左子节点为3,与3做比较(总比较次数3),比3大,接着与3的右子节点比较,由于3没有右子节点,因此把4 插入到3 的右子节点中.
树：10
/ \
3 18
\
4
.
后面的希望你自己做,验证下自己了解了没.
10
/ \
3 18
/ \ / \
2 4 13 21
\ \
9 15
/
7
\
...
全部展开
10
/ \
3 18
/ \ / \
2 4 13 21
\ \
9 15
/
7
\
8
插入的结果如上
其实二叉排序树很简单，他必须满足一个条件，即父节点的值大于左边孩子的值，且小于右边孩子的值。
每次插入的时候，都必须于当前节点比较，如果大于当前节点，则与右子节点进行比较，如果小于当前节点，则与左子节点比较，一直比较下去，直到不存在左子节点或右子节点，则把新节点插入到不存在的位置。
如
第1步： 插入10 不用比较，10为根节点
树： 10
第2步： 插入18 从根节点开始与10 比较(总比较次数1)，比10大，所以接着与10的右子节点比较，由于10没有右子节点，因此把18 插入到10 的右子节点中
树： 10
\
18
第3步： 插入3 从根节点开始与10 比较(总比较次数2)，比10小，所以接着与10的左子节点比较，由于10没有左子节点，因此把3 插入到10 的左子节点中
树： 10
/ \
3 18
第4步： 插入4 从根节点开始与10 比较，比10小，所以接着与10的左子节点比较(总比较次数3)，10的左子节点为3，与3做比较(总比较次数3)，比3大，接着与3的右子节点比较，由于3没有右子节点，因此把4 插入到3 的右子节点中。
树： 10
/ \
3 18
\
4
.......
后面的希望你自己做，验证下自己了解了没。
答案是25
收起