2016-11-07 17:06发布
这个问题没有完全吧,是这个题目吗:
已知具有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 FBT 1 2 3 4 5 6写出执行f31(BT,6)后的输出结果;解:函数 f31 为按先序遍历二叉树,根据二叉树形状,很容易知道先序遍历为:ABDECF
最多设置5个标签!
这个问题没有完全吧,是这个题目吗:
已知具有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
一周热门 更多>