復制二叉樹（非遞歸實現）

復制二叉樹（非遞歸實現）:

pbinary_tree_node copy_binary_tree(pbinary_tree_node bt)
{//先序遍歷輸出一顆樹的全部結點值1,2,3
 stack<pbinary_tree_node> stack_left,stack_right;
 pbinary_tree_node newbt;
 if (bt!=NULL)
 {
  //new root
  newbt=new binary_tree_node;
  newbt->data=bt->data;

  //travel bt and travel newbt at the same time
  stack_left.push(bt);
  stack_right.push(newbt);

  while (!stack_left.empty())
  {
   pbinary_tree_node pleft=stack_left.top();
   pbinary_tree_node pright=stack_right.top();
   stack_left.pop();
   stack_right.pop();
   if (pleft->rchild!=0)
   {
    stack_left.push(pleft->rchild);
    pright->rchild=new binary_tree_node;
    pright->rchild->data=pleft->rchild->data;
    stack_right.push(pright->rchild);
   }
   if (pleft->lchild!=0)
   {
    stack_left.push(pleft->lchild);
    pright->lchild=new binary_tree_node;
    pright->lchild->data=pleft->lchild->data;
    stack_right.push(pright->lchild);
   }
  }
 }
 return newbt;
}

這個算法使用了兩個棧，一個棧用來遍歷原來的二叉樹，另一個棧一邊創建新的二叉樹，一邊同第一個棧同步，保存遍歷時的軌跡。