1.已知具有n 个结点的完全二叉树采用顺序存储结构存储在向量BT[1..n]中,结点的数据元素 财富值2

2016-11-07 17:06发布

1条回答
CappuccinoYL
1楼 · 2016-11-07 17:48.采纳回答

这个问题没有完全吧,是这个题目吗:

已知具有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

一周热门 更多>