Question

一棵n个结点的完全二叉树以向量（数组）作为存储结构，试设计非递归算法对该完全二叉树进行前序遍历

用java编写，谢谢！

Answer 1

#include<stdio.h>

#define ARRAY_MAX 12

int main()

{

int tree[ARRAY_MAX];

for(int i = 0;i < ARRAY_MAX;i++)

tree[i] = i+1;

int flag = 0;//记录当前叶子的遍历位置,0 刚遍历到这个叶子,1 已经遍历完成该叶子的左儿子,2 已经遍历完成该叶子的右儿子

int count = 1;//假设tree不为空

while(!(count == 1&&flag == 2))

{

if(flag == 0)

{

printf("%d ",tree[count-1]);

if(count*2 > ARRAY_MAX)

flag = 1;

else

count = count*2;

}

else if(flag == 1)

{

if(count*2+1 > ARRAY_MAX)

flag = 2;

else

{

count = count*2+1;

flag = 0;

}

}

else if(flag == 2)

{

if(count%2 == 0)

flag = 1;

else

flag = 2;

count = count/2;

}

}

getchar();

return 0;

}

以上代码Microsoft Visual C++ 6.0中编译通过，输出的数列为以下下二叉树的前序遍历

连5分都不给，真小气......

Answer 2

没有关系呀，你把二叉树的下标统统减一，然后修改下对应的二叉树的公式就行了，当然公式不能照搬，但是做到下标从零开始还是没问题的