复制二叉树代码出现的问题
复制二叉树，请问哪里出问题了？
源.cpp
#include<iostream>//cout,cin
#include<string>
using namespace std;
#include"bitree.h"
#include"SqQueue.h"
#include"SqStack.h"
//测试参考数据
string fbt = "a b d # # e # # c f # # g # #"; // 满二叉树最后一层每个叶结点后有两个#
string cbt = "a b d # # e # # c # #"; // 完全二叉树每个叶结点后有两个#
string gbt = "a b # d # # c e # # #"; // 一般二叉树
string obt = "a b c d # # # # #"; // 左斜树1
void dispmenu()
{
cout << "\n功能选择（1-3，0退出！）" << endl;
cout << "1-创建二叉树\n";
cout << "2-显示二叉树\n";
cout << "3-复制二叉树\n";
cout << "0-退出\n";
}
template<class DT>
BTNode<DT>* CopyBiTree(BTNode<DT>* bt)
{
BTNode<DT>* nt;
if (bt == NULL)
return NULL;
else
{
nt = new BTNode<DT>;
nt->data = bt->data;
nt->lchild = CopyBiTree(bt->lchild);
nt->rchild = CopyBiTree(bt->rchild);
}
return bt;
}
void main()
{
int level;
BTNode<char>* bt;
int y = 100, x = 350;
system("cls");
int choice;
do
{
dispmenu();
cout << "Enter choice(1-3,0退出):";
cin >> choice;
switch (choice)
{
case1:
cout << "测试参考数据：" << endl;
cout << "满二叉树：" << fbt << endl;
cout << "完全二叉树：" << cbt << endl;
cout << "一般二叉树：" << gbt << endl;
cout << "左斜二叉树：" << obt << endl;
cout << "\n请按先序序列的顺序输入二叉树,#为空指针域标志：" << endl;
CreateBiTree(bt);
cout << "创建的二叉树为：" << endl;
level = 1;
DispBiTree(bt, level);
break;
case 2:
cout << "\n二叉树：" << endl;
level = 1;
DispBiTree(bt, level);
break;
case 3:
cout << "\n复制的二叉树为：" << CopyBiTree(bt) << endl;
break;
case 0:
DestroyBiTree(bt);
cout << "\n运行结束Bye-Bye!" << endl;
break;
default:
cout << "无效选择，请重新选择！\n";
break;
}
} while (choice != 0);
return ;
}
bitree.h
#include"SqStack.h"
#include"SqQueue.h"
template <class DT>
struct BTNode // 结点定义
{
DT data ; //数据域
BTNode* lchild; //指向左子树的指针
BTNode* rchild; //指向右子树的指针
};
//算法5.1 先序遍历递归算法
template <class DT>
void PreOrDerBiTree(BTNode<DT> *bt)
{
if(bt!=NULL)
{
cout<<bt->data<<' '; //输出结点上的数据
PreOrDerBiTree(bt->lchild); //递归的调用前序遍历左子树
PreOrDerBiTree(bt->rchild); //递归的调用前序遍历右子树
}
//return;
}
//算法5.2 中序遍历递归算法
template <class DT>
void InOrDerBiTree(BTNode<DT> *bt)
{
if(bt!=NULL)
{
InOrDerBiTree(bt->lchild); //递归的调用中序遍历左子树
cout<<bt->data<<' '; //输出结点上的数据
InOrDerBiTree(bt->rchild); //递归的调用中序遍历右子树
}
//return;
}
//算法5.3 后序遍历递归算法
template <class DT>
void PostOrDerBiTree(BTNode<DT> *bt)
{
if(bt!=NULL)
{
PostOrDerBiTree(bt->lchild); //递归的调用后序遍历左子树
PostOrDerBiTree(bt->rchild); //递归的调用后序遍历右子树
cout<<bt->data<<' '; //输出结点上的数据
}
//return;
}
//算法5.4 层序遍历算法
template<class DT>
void LevelBiTree(BTNode<DT> *bt)
{
SqQueue<DT>Q; // 创建一个队
int m=20;
InitQueue(Q,m);
BTNode<DT>* p;
p=bt;
if(p) EnQueue(Q,p); // 树非空，入队
while (!QueueEmpty(Q)) // 队非空
{
DeQueue(Q,p); // 出队
cout<<p->data; // 访问
if(p->lchild!=NULL) // 有左孩子
EnQueue(Q, p->lchild); // 左孩子入队
if(p->rchild!=NULL) // 有右孩子
EnQueue(Q, p->rchild); // 右孩子入队
}
DestroyQueue(Q); // 销毁队列
}
//算法5.5 先序非遍历递归算法
template <class DT>
void PreOrderBiTree_N(BTNode<DT> *bt)
{
SqStack<DT> S; // 创建栈
int m=20;
InitStack(S, m);
BTNode<DT>* p;
p=bt;
while (p!=NULL || !StackEmpty(S)) // 树非空或栈非空
{
while(p!=NULL) // 结点非空
{
cout<<p->data<<' '; // 访问结点
Push(S,p); // 入栈
p=p->lchild; // 转左子树
}
if(!StackEmpty(S)) // 栈非空
{
Pop(S,p); // 出栈
p=p->rchild; // 转出栈结点的右子树
}
}
DestroyStack(S); //销毁栈
}
//算法5.6 中序非遍历递归算法
template <class DT>
void InOrderBiTree_N(BTNode<DT> *bt)
{
SqStack<DT> S; // 创建一个栈
int m=20;
InitStack(S, m);
BTNode<DT>* p;
p=bt;
while (p!=NULL || !StackEmpty(S)) // 结点非空或栈非空
{
while(p!=NULL) // 结点非空
{
Push(S,p); // 出栈
p=p->lchild; // 转出栈结点右子树
}
if(!StackEmpty(S)) // 栈非空
{
Pop(S,p); // 出栈
cout<<p->data<<' '; // 访问出栈结点
p=p->rchild; // 转出栈结点的右子树
}
}
DestroyStack(S); // 销毁栈
}
//算法5.7 后序非遍历递归算法
template <class DT>
void PostOrderBiTree_N(BTNode<DT> *bt)
{ // 1. 初始化
SqStack<DT> S; // 创建一个栈
int m=20;
InitStack(S, m);
BTNode<DT>* p;
BTNode<DT>* r;
p=bt;
bool flag; // 顶点操作标志
do
{
while(p) // 结点非空
{
Push(S,p); // 结点入栈
p=p->lchild; // 转左子树
}
r=NULL; // 指向刚被访问点，初值为空
flag=true; // true表示处理栈顶结点
while(!StackEmpty(S) && flag) // 栈非空且当前处理的是栈顶结点
{
GetTop(S,p); // 获取栈顶元素
if(p->rchild==r) // 如果当前结点是栈元素的右孩子
{
cout<<p->data<<' '; // 访问栈顶元素
Pop(S,p); // 出栈
r=p; // r指向被访问结点
}
else // 否则
{
p=p->rchild; // 转栈顶元素右孩子
flag=false; // 当前点为非栈顶结点
}
}
}while(!StackEmpty(S)); // 栈非空，循环
cout<<endl;
DestroyStack(S); // 销毁栈
}
//算法5.8 创建二叉树
template <class DT>
void CreateBiTree(BTNode<DT> *&bt)
{
char ch;
cin>>ch; // 输入根结点的数据
if(ch=='#') // # 表示指针为空，说明树为空
bt=NULL ;
else
{
bt=new BTNode<DT>; // 申请内存
if(!bt)
{
cout<<"申请内存失败！"<<endl;
exit(-1); // 申请内存失败退出
}
bt->data=ch;
CreateBiTree(bt->lchild); // 创建根结点左子树
CreateBiTree(bt->rchild); // 创建根结点右子树
}
return;
}
//算法5.9 销毁二叉树
template <class DT>
void DestroyBiTree(BTNode<DT> *&bt)
{
if(bt) // 树非空
{
DestroyBiTree(bt->lchild); // 销毁左子树
DestroyBiTree(bt->rchild); // 销毁右子树
delete bt;
}
}
//算法5.10 结点查找
template<class DT>
BTNode<DT>* Search(BTNode<DT> * bt, DT e) // 查找值为e的元素
{
BTNode<DT> *p;
if(bt==NULL) // 结点为空，返回
return NULL;
else if(bt->data==e) // 找到，返回结点指针
return bt;
else // 结点值不为e
{
p=Search(bt->lchild,e); // 在左子树上查找
if(p!=NULL) // 找到
return p; // 返回结点指针
else // 未找到
return Search(bt->rchild,e); // 转右子树上查找
}
}
//算法5.11 求树深
template <class DT>
int Depth(BTNode<DT> *bt)
{
int hl,hr;
if(bt==NULL) // 树空
return 0; // 深度为0
else // 树非空
{
hl=Depth(bt->lchild); // 求左子树深度
hr=Depth(bt->lchild); // 求右子树深度
if(hl>hr) // 左子树高
return hl+1; // 树高为左子树高加1
else return hr+1; // 左子树高,树高为左子树高加1
}
}
//算法5.12 结点计数
template <class DT>
int NodeCount(BTNode<DT> *bt)
{
if(bt==NULL) // 空树，结点数为0
return 0;
else // 非空树，结点数为左、右子树结点数的和加1
return NodeCount(bt->lchild)+NodeCount(bt->rchild)+1;
}
template <class DT>
void DispBiTree(BTNode<DT> * bt,int level) // 显示树
{
if(bt) // 空二叉树不显示
{ DispBiTree(bt->rchild,level+1); // 显示右子树
cout<<endl; // 显示新行
for(int i=0;i<level-1;i++)
cout<<" "; // 确保在第level列显示节点
cout<<bt->data; // 显示节点
DispBiTree(bt->lchild,level+1); // 显示左子树
cout<<endl;
}//if
}
SqQueue.h
//队列工具
template <class DT>
struct SqQueue // 顺序队类
{
BTNode<DT>* *base; // 队列首址
int front; // 队头指针
int rear; // 队尾指针
int queuesize; // 队容量
};
//【算法3.14】 初始化队列
template <class DT>
void InitQueue(SqQueue<DT> &Q, int m)
{
Q.base=new BTNode<DT>*[m]; // 申请队列空间
if(Q.base==NULL) // 申请空间失败
{
cout<<"未创建成功！";
exit (1); // 退出
}
Q.front=Q.rear=0; // 设置队列属性
Q.queuesize=m;
}
//算法3.15】 销毁列列
template <class DT>
void DestroyQueue(SqQueue<DT> &Q)
{
delete [] Q.base; // 释放队列空间
Q.front=Q.rear=0; // 设置队列属性
Q.queuesize=0;
}
//【算法3.16】 入队
template<class DT>
bool EnQueue(SqQueue<DT> &Q,BTNode<DT>* e)
{
if((Q.rear+1)%Q.queuesize==Q.front) // 队满
return false; // 返回false
Q.base[Q.rear]=e; // 出队
Q.rear=(Q.rear+1)% Q.queuesize; // 修改队列属性
return true; // 返回true
}
//【算法3.17】 出队
template<class DT>
bool DeQueue(SqQueue<DT> &Q,BTNode<DT>* &e)
{
if(Q.front==Q.rear) // 队空
return false;
e=Q.base[Q.front];
Q.front=(Q.front+1)%Q.queuesize;
return true; // 删除成功，返回true
}
// 测队空
template<class DT>
bool QueueEmpty(SqQueue<DT> Q)
{
if(Q.front==Q.rear) // 队空
return true; // 返回true
else // 队不空
return false; // 返回false
}
SqStack.h
//栈
template <class DT>
struct SqStack // 顺序栈
{
BTNode<DT>* *base; // 栈首址
int top; // 栈顶指针
int stacksize; // 栈容量
};
//【算法3.1】 初始化栈
template <class DT>
void InitStack(SqStack<DT> &S, int m)
{
S.base=new BTNode<DT>* [m]; // 申请栈空间
if(S.base==NULL)
{
cout<<"未创建成功！";
exit (1);
}
S.top=-1; // 空栈
S.stacksize=m; // 栈容量为m
}
//算法3.2】 销毁栈
template <class DT>
void DestroyStack(SqStack<DT> &S)//析构函数
{
delete [] S.base; //释放栈空间
S.top=-1;
S.stacksize=0;
}
//【算法3.3】
template<class DT>
bool Push(SqStack<DT> &S,BTNode<DT>* e)
{
if(S.top==S.stacksize-1) // 栈满，不能插入
return false;
S.top++;
S.base[S.top]=e;
return true; // 插入成功，返回true
}
//【算法3.4】 出栈
template<class DT>
bool Pop(SqStack<DT> &S,BTNode<DT>* &e)
{
if(S.top==-1) //栈空
return false;
e=S.base[S.top];
S.top--;
return true; // 出栈成功，返回true
}
template<class DT> // 获取栈元素
bool GetTop(SqStack<DT> &S,BTNode<DT>* &e)
{
if(S.top==-1) // 栈空，返回false
return false;
e=S.base[S.top]; // 取栈元素
return true; // 返回true
}
// 测栈空
template<class DT>
bool StackEmpty(SqStack<DT> S)
{
if(S.top==-1) // 栈空，返回true
return true;
else // 栈非空，返回false
return false;
}
SqStack.h没有include Bitree.h，所以 BTNode 这些没有识别