3.txt

清华大学出版社严蔚敏编著数据结构习题答案

6.46③  编写复制一棵二叉树的非递归算法。

要求实现下列函数：
void CopyBiTree(BiTree T, BiTree &TT);
/* 基于层次遍历的非递归复制二叉链表 */

二叉链表类型定义：
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)
/* 基于层次遍历的非递归复制二叉链表 */
{
 QElemType p1,p2;
 LinkQueue Q1,Q2;
 InitQueue(Q1);
 InitQueue(Q2);
 if(!(TT=(BiTNode*)malloc(sizeof(BiTNode))))exit(OVERFLOW);
 EnQueue(Q1,T);
 EnQueue(Q2,TT);
 while(!QueueEmpty(Q1)){
    DeQueue(Q1,p1);
    DeQueue(Q2,p2);
    if(p1)p2->data=p1->data;
    else TT=T;
    if(p1->lchild){
        if(!(p2->lchild=(BiTNode*)malloc(sizeof(BiTNode)))) exit(0);
        EnQueue(Q1,p1->lchild);
        EnQueue(Q2,p2->lchild);
        }
        if(p1->rchild){
            if(!(p2->rchild=(BiTNode*)malloc(sizeof(BiTNode))))exit(0);
            EnQueue(Q1,p1->rchild);
            EnQueue(Q2,p2->rchild);
        }
    }
}