请利用栈的基本操作写出复制二叉树的非递归算法
收起
知与谁同
2018-07-18 10:31:26
1719
0
1
条回答
写回答
取消
提交回答
-
//非递归方法
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;
}
//递归方法
void copy_binary_tree(pbinary_tree_node bt,pbinary_tree_node &newbt)
{
if(bt!=NULL)
{
newbt=(pbinary_tree_node )malloc(sizeof(binary_tree_node));
newbt->data=bt->data;
copy_binary_tree(bt->lchild,newbt->lchild);
copy_binary_tree(bt->rchild,newbt->rchild);
}
else
newbt=NULL;
}
这个应该没问题了,
2019-07-17 22:54:53