6.46.c

来自「部分高校使用anyview编程测试数据结构习题,此代码为数据结构题集(c语言版)」· C语言 代码 · 共 49 行

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)
/* 基于层次遍历的非递归复制二叉链表 */
{
  Queue Q1,Q2;
  struct BiTNode *p,*q;
  InitQueue(Q1);InitQueue(Q2);
  if(T){
      EnQueue(Q1,T);
      TT=(BiTNode*)malloc(sizeof(BiTNode));
      EnQueue(Q2,TT);
      while(!QueueEmpty(Q1))
        {
         DeQueue(Q1,p);
         DeQueue(Q2,q);
         q->data=p->data;     
         if(p->lchild)
           {q->lchild=(BiTNode*)malloc(sizeof(BiTNode));
            EnQueue(Q1,p->lchild);         
            EnQueue(Q2,q->lchild);
            }
         if(p->rchild)
           {q->rchild=(BiTNode*)malloc(sizeof(BiTNode));     
            EnQueue(Q1,p->rchild);
            EnQueue(Q2,q->rchild);
           }
      } //while
  }//if
}