请教一个binary search tree和heap的问题。 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

请教一个binary search tree和heap的问题。

请教一个binary search tree和heap的问题。# JobHunting - 待字闺中

C*n2009-11-01 07:11

1 楼

问个很基本的问题。
假定某个binary search tree和max heap都是有输入一些数字序列所构成，
那么是不是binary search tree跟输入数字的顺序无关，只可能有一种binary search
tree,
但max heap(或min heap)则跟输入数字的顺序有关，同样的几个数字，输入顺序不同所
形成的max heap也不一样？

a*s2009-11-01 07:11

2 楼

都有关

C*n2009-11-01 07:11

3 楼

是吗？
那如果我看到书上一个现成的binary search tree,
请问该按什么顺序输入这些数字才能使得所生成的binary search tree跟书上的那个一
样呢?

【在 a**********s 的大作中提到】

: 都有关

a*s2009-11-01 07:11

4 楼

就是的, 如果无关, 那还问你这个干吗?

【在 C**********n 的大作中提到】

: 是吗？
: 那如果我看到书上一个现成的binary search tree,
: 请问该按什么顺序输入这些数字才能使得所生成的binary search tree跟书上的那个一
: 样呢?

C*n2009-11-01 07:11

5 楼

那你能说一下怎样输入这些数字才能使得生成的binary search tree跟我想要的那个一
样呢?

【在 a**********s 的大作中提到】

: 就是的, 如果无关, 那还问你这个干吗?

s*l2009-11-01 07:11

6 楼

Preorder traversal

【在 C**********n 的大作中提到】

: 那你能说一下怎样输入这些数字才能使得生成的binary search tree跟我想要的那个一
: 样呢?

g*y2009-11-01 07:11

7 楼

很多种输入方法。一种是按照已知tree的pre-order输入

【在 C**********n 的大作中提到】

: 那你能说一下怎样输入这些数字才能使得生成的binary search tree跟我想要的那个一
: 样呢?

C*n2009-11-01 07:11

8 楼

thanks a lot.

【在 g*******y 的大作中提到】

: 很多种输入方法。一种是按照已知tree的pre-order输入

S*Y2009-11-01 07:11

9 楼

all are related
preOrder traversal or level order traveral

search

【在 C**********n 的大作中提到】

: 问个很基本的问题。
: 假定某个binary search tree和max heap都是有输入一些数字序列所构成，
: 那么是不是binary search tree跟输入数字的顺序无关，只可能有一种binary search
: tree,
: 但max heap(或min heap)则跟输入数字的顺序有关，同样的几个数字，输入顺序不同所
: 形成的max heap也不一样？

C*n2009-11-01 07:11

10 楼

呵呵，
那给定一些数字，我想构造一个Max heap或Min heap，
那按level order traveral能否构找出我想要的那个Max heap?

【在 S**Y 的大作中提到】

: all are related
: preOrder traversal or level order traveral
:
: search

S*Y2009-11-01 07:11

11 楼

the "level order traversal" of a heap is the order of the array inside the h
eap. Of course you can copy the array...

【在 C**********n 的大作中提到】

: 呵呵，
: 那给定一些数字，我想构造一个Max heap或Min heap，
: 那按level order traveral能否构找出我想要的那个Max heap?

C*n2009-11-01 07:11

12 楼

what do you mean the order of the array inside the heap？

h

【在 S**Y 的大作中提到】

: the "level order traversal" of a heap is the order of the array inside the h
: eap. Of course you can copy the array...