一棵具有n个结点的完全二叉树以数组存储，试写一个非递归算法实现对该树的前序遍历

Question

如题所述

Answer 1

#include "stdafx.h"
#include <stack>
#include <iostream>
using namespace std;

int _tmain(int argc, _TCHAR* argv[])
{
//构建完全二叉树,层数是三，7个节点
int a[7] = {0,1,2,3,4,5,6};

//前序遍历，先访问左儿子，再访问自己，再访问右儿子
//左儿子的位置是自己游标*2+1，右儿子是自己的游标*2+2

//队列作为缓冲
stack<int> Temp;

Temp.push(0);//根节点

while(!Temp.empty())
{
int node = Temp.top();

if(2*node+1 <6)//有左儿子
{
Temp.push(2*node+1);
}
else
{
cout<<a[node]<<endl;
Temp.pop();

if(Temp.empty())
{
getchar();
return 0;
}

int parent = Temp.top();

cout<<a[parent]<<endl;

Temp.pop();

Temp.push(2*parent+2);

}
}

getchar();

return 1;
}

Answer 2

自己是前端，JS可能更熟，就用JS大概的写下
当中可能有错误，不过总体思路是OK的
var nodes=[];

var top;

for(var i =0 ; i < node;i++){

var node =[nodes[i]]

while(node.length){
var one = node.pop();
if(!top)top=one;
console.log(one.value);
if(one.l!==void 0){
one.push(node);
continue;
}else{
if(!one.length){
node.push(top)
continue;
}
if(one.r){
node.push(one.r)
}
}
}

top = void 0;

}

Answer 3

1:问问段锡强，2：问问我。3:随便void NRPreOrder(BiTree BT,*visit(ElemType)){ if (BT) { InitStack (S); Push(S,BT); while (!StackEmpty(S)) { Pop(S,p);visit(P->data); if(p->lchild)Push (S, p->lchild); if(p->lchild)Push (S, p->lchild); } }}