二叉树的遍历

今天面试被问到不用递归遍历二叉树，当时只想着以前没用过，直接回答了不知道。回来路上想了一下，递归和栈是一样的，直接改成栈就好了啊，嗯，大概最后结束的判断条件要考虑一下，实在不行试试图的遍历。唉，不镇定啊，着急了。

void print_recursion(BinaryTreeNode * n){
  if(n == NULL){
    cout << "null" << endl;
  }
  else{
    cout << n->data;
    print_recursion(n->LeftChild);
    print_recursion(n->RightChild);
  }
}

void print_Norecursion(BinaryTreeNode *n){
  stack<BinaryTreeNode *> NodeStack;
  while(n!=NULL || !NodeStack.empty()){
    while(n){
      cout << n->data <<" ";
      NodeStack.push(n);
      n = n->LeftChild;
    }
    if(!NodeStack.empty()){
      n = NodeStack.top();
      NodeStack.pop();
      n = n->RightChild;
    }
  }
}

int main(int argc, char *argv[]){
  BinaryTreeNode* root;
  root = CreateTree();
  print_recursion(root);
  print_Norecursion(root);
}

./bitree
1
add 1
2
add 2
0
0
3
add 3
4
add 4
0
0
5
add 5
0
0
1 2 Null
Null
3 4 Null
Null
5 Null
Null
1 2 3 4 5