1．已知具有n 个结点的完全二叉树采用顺序存储结构存储在向量BT[1..n]中，结点的数据元素
发布时间:2016-11-07 17:06
财富值2
1个回答
这个问题没有完全吧，是这个题目吗：
已知具有n个结点的完全二叉树采用顺序存储结构存储在向量BT[1..n]中，结点的数据元素为字符类型，请阅读下列算法，并回答问题： 假设向量BT中的内容为： A B C D E F BT 1 2 3 4 5 6 写出执行f31(BT,6)后的输出结果；
题目有两个个关键的地方：完全二叉树，顺序存储。
因此对于一棵有 n 个节点的完全二叉树有下面的性质：
对任一节点 (1<=i<=n)
1) 如果 i=1 ，它是根节点，无父亲，如果 i>1 ,它的 父亲是 i/2 (向下取整)
2) 如果 2*i>n ,则节点 i没有左孩子，否则它的左孩子是 2*i
3) 若果 2*i+1>n 节点 i没有右孩子，否则右孩子是 2i+1
例如 BT[1...6] = [A,B,C,D,E,F] ,则利用上面的性质有：
节点 A(i=1) 有左孩子 B(i=2*1=2) 和右孩子 C(i=2*1+1=3)
节点 B(i=2) 有左孩子 D(i=2*2=4) 和右孩子 E(i=2*2+1=5)
节点 C(i=3) 有左孩子 F(i=2*3=6),因为 2*3+1=7>n=6 ,节点 C 没有右孩子
节点 DEF 都为叶子节点，没有左孩子也没有右孩子
二叉树形状为（建议考到记事本看，否则可能不对齐）：
A(1)
/
/
B(2) C(3)
/ /
/ /
D(4) E(5) F(6)
(1)假设向量BT中的内容为：
A B C D E F
BT 1 2 3 4 5 6
写出执行f31(BT,6)后的输出结果；
解：函数 f31 为按先序遍历二叉树，根据二叉树形状，
很容易知道先序遍历为：ABDECF
发布于 2016-11-07 17:48
查看更多
