已知二叉树采用二叉链表结构存储，请设计将二叉树s复制给二叉树t的非递归算法

要将二叉树 `s` 复制到二叉树 `t` 中，并且采用非递归的方式完成，可以利用队列（Queue）这种数据结构辅助操作。以下是具体的步骤说明： ### 算法思路 1. **初始化**：首先检查如果 `s` 树为空，则直接令 `t = NULL`；否则创建一个新的节点作为 `t` 的根节点，并将其值设置为与 `s` 的根节点相同的值。 2. **队列准备**：使用两个队列分别存放源树 `s` 和目标树 `t` 的当前待处理节点指针。将两棵树的根节点入队。 3. **逐层复制**： - 当队列不为空时循环执行以下步骤： - 取出两个队首元素，分别为 `p_s` 和 `p_t`； - 如果 `p_s->left != NULL` 则创建新的左孩子节点并赋值给 `p_t->left`，然后把这两个新节点加入各自对应的队列。 - 类似地对右孩子进行上述操作。 4. 结束条件：当所有层次均遍历完毕后退出循环即可得到完整的拷贝结果——即此时`t`就是`s`的一份深副本。 此方法通过广度优先搜索实现了整棵二叉树的所有结点及其连接关系的完整复制过程。 --- #### 示例代码片段 (伪代码) ```cpp void CopyTree(BiNode *rootS, BiNode *& rootT){ if(rootS == NULL) { rootT = NULL; return ; } // 初始化 queue<BiNode*> qS,qT; // 定义两个队列用于存储 s 和 t 节点 rootT=new BiNode(); // 创建根节点 rootT->data=rootS->data; rootT->lchild=NULL; rootT->rchild=NULL; qS.push(rootS); qT.push(rootT); while(!qS.empty()){ BiNode* ps=qS.front(); BiNode* pt=qT.front(); qS.pop(); qT.pop(); if(ps->lchild!=NULL){ // 检查是否有左子节点 pt->lchild=new BiNode(); // 新建对应位置的新节点 pt->lchild->data=ps->lchild->data; pt->lchild->lchild=NULL; pt->lchild->rchild=NULL; qS.push(ps->lchild); // 将左右孩子的信息存进各自的队列里继续后续判断 qT.push(pt->lchild); } if(ps->rchild!=NULL){ // 同理检查有无右子节点 pt->rchild=new BiNode(); pt->rchild->data=ps->rchild->data; pt->rchild->lchild=NULL; pt->rchild->rchild=NULL; qS.push(ps->rchild); qT.push(pt->rchild); } } } ``` 以上展示了如何借助队列实现一种高效的、基于层级顺序（BFS）的方式来完成从一棵指定形态下的原始二叉树向另一棵空置状态的目标二叉树之间的内容迁移工作。