复制一棵二叉树的非递归算法

本文主要是介绍复制一棵二叉树的非递归算法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

二叉链表类型定义：

typedef char TElemType;   // 设二叉树的元素为char类型
typedef struct BiTNode {TElemType data;BiTNode  *lchild, *rchild;
} BiTNode, *BiTree;

可用队列类型Queue的相关定义：

typedef BiTree QElemType; // 设队列元素为二叉树的指针类型
Status InitQueue(Queue &Q);
Status EnQueue(Queue &Q, QElemType e);
Status DeQueue(Queue &Q, QElemType &e);
Status GetHead(Queue Q, QElemType &e);
Status QueueEmpty(Queue Q);

实现函数如下：

void CopyBiTree(BiTree T, BiTree &TT)
/* 基于层次遍历的非递归复制二叉链表 */
{BiTree p1,p2;Queue Q1,Q2;if(!T){TT = NULL;return ;}TT = (BiTree)malloc(sizeof(BiTNode));InitQueue(Q1);InitQueue(Q2);EnQueue(Q1,T);EnQueue(Q2,TT);while(!QueueEmpty(Q1)){DeQueue(Q1,p1);DeQueue(Q2,p2);p2 -> data = p1 -> data;if(p1 ->lchild){//复制左子树EnQueue(Q1,p1 -> lchild);p2 -> lchild = (BiTree)malloc(sizeof(BiTNode));if(!p2 -> lchild){exit(OVERFLOW);}EnQueue(Q2,p2 -> lchild);}if(p1 ->rchild){//复制右子树EnQueue(Q1,p1 -> rchild);p2 -> rchild = (BiTree)malloc(sizeof(BiTNode));if(!p2 -> rchild){exit(OVERFLOW);}EnQueue(Q2,p2 -> rchild);}}
}

这篇关于复制一棵二叉树的非递归算法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---