复制二叉树的非递归算法.算法思想和算法实现.

Question

二叉链表表示的二叉树，复制二叉树的非递归算法。算法思想和算法实现。

这个题目 求个代码。。

Answer 1

void Main()
{
BNode node = new BNode(){
value = "1",
lNode = new BNode(){
value = "1-1"
},
rNode = new BNode(){
value = "1-2",
lNode = new BNode() {
value = "1-2-1",
rNode = new BNode() {
value = "1-2-1-2"
}
},
rNode = new BNode() {
value = "1-2-2"
}
}
};

BNode clone = Clone(node); 
}

BNode Clone(BNode source) {
Stack<BNode> stack = new Stack<BNode>();
stack.Push(source);

BNode dest = new BNode();
Stack<BNode> stackDest = new Stack<BNode>();
stackDest.Push(dest);
while (stack.Count>0) {
//复制节点的值
BNode s = stack.Peek();
BNode d = stackDest.Peek();
d.value = s.value;

if (s.lNode != null) { //寻找左子树 作为下一个结点
stack.Push(s.lNode);
d.lNode = new BNode();
stackDest.Push(d.lNode);
} else if (s.rNode != null) { //没有就找右子树
stack.Push(s.rNode);
d.rNode = new BNode();
stackDest.Push(d.rNode);
} else { //全没有 跳转到父结点的右子树
while (true) {
stack.Pop();
stackDest.Pop();
if (stack.Count <= 0) break;

BNode p = stack.Peek();
if (p.rNode == s) { //已经使用过右结点 向上继续回溯
s = p;
}
else if (p.rNode != null) {
stack.Push(p.rNode);
d = stackDest.Peek();
d.rNode = new BNode();
stackDest.Push(d.rNode);
break;
} 
else s=p;
}
}
}
return dest;
}

// Define other methods and classes here
class BNode {
public object value;
public BNode lNode;
public BNode rNode;
}

算法思想的话就是构建两个栈用于回溯父结点...

其实递归算法隐藏了栈而已... 手动把这个栈构建出来就算成功了...

以上是一段C#代码示例   java代码应该复制粘贴就能用  C或者C++的话把BNode写成指针就可以使用...

Answer 2

Status CopyBiTree(BiTree &dest, BiTree &sour,const int size)
{//层次遍历二叉树的同时对二叉树进行复制

if (!sour)//空树
{
dest = NULL;
}
else
{
Queue *Q;
BiTreeNode** de = new BiTreeNode*[size];
if (!de)
{
exit(OVERFLOW);//内存溢出
}
int pde = 0;//指向待建立左子树根和右子树根的结点

dest->data = sour->data;
de[pde] = dest;//先对根结点的复制
InitQueue(Q);
Enqueue(Q, sour);
while (!IsQEmpty(Q))//当还没复制完
{
int i = 1;//指向生成的左子树根和右子树根应该放入的位置
                          //因为一个结点的孩子不会超过2个，所以这个值最大是2
BiTreeNode *p; 
Dequeue(Q, p);
if (p->Lchild)//放入左子树的同时复制左子树
{
Enqueue(Q, p->Lchild);//放入左子树
BiTreeNode *left = Buynode(p->Lchild->data);
de[pde]->Lchild = left;//建立左子树关系
de[pde + (i++)] = left;//尾插左子树
}
if (p->Rchild)
{
Enqueue(Q, p->Rchild);
BiTreeNode *right = Buynode(p->Rchild->data);
de[pde]->Rchild = right;
de[(pde++) + i] = right;//pde++到层次遍历的
                  //下一个结点
}
}
}
return OK;
}

算法的思想很简单，就是在对二叉树进行层次遍历的时候，对其进行复制。

遍历是必须的，因为要复制一棵二叉树，首先就是要对其进行遍历。

想象一下，在对源二叉树进行层次遍历的时候，要复制的二叉树也在进行层次遍历，当源二叉树遍历到某个结点时，要复制的二叉树上生成了相对应的结点，最终在遍历完源二叉树时，完成对要复制二叉树的复制。在层次遍历的时候，每个结点的左子树右子树的情况都是可以知道的，所以在相应复制的时候也能建立对应的左子树右子树。

算法仅供参考，未必优秀，不过想的时候，千万不要想复杂了，发散地想，很快就可以想到的。