回帖
#include\"BTree.h\"
#include\"SeqQueue.cpp\"
template<class T>
void BTree<T>::SetFlag()
{
cin>>flag;
}
template<class T>
bool BTree<T>::IsEmpty()const
{
return root==NULL;
}
template<class T>
bool BTree<T>::Root(T& x)const
{
if(root){
x=root->element;
return true;
}
return false;
}
/*template<class T>
void BTree<T>::MakeTree(const T& e,BTree<T>&left,BTree<T>&right)
{
BTNode<T>* p;
p=new BTNode<T>(e,left.root,right.root);
left.root=right.root=0;//释放空间
root=p;
}*/
template<class T>
void BTree<T>::InputPerfTr(istream& in)
{
BTNode<T> *p;
T a;
SeqQueue<BTNode<T>*> node(20);
node.EnQueue(root);
cout<<\"按层次输入数据(输入\\"\"<<flag<<\"\\"结束):\"<<endl;
in>>a;
while(a!=flag){
p=node.Front()=new BTNode<T>(a);
node.DeQueue();
in>>a;
node.EnQueue(p->lchild);
node.EnQueue(p->rchild);
}
}
template<class T>
void BTree<T>::InputAnyTr(istream& in)
{
BTNode<T> *p;
T a;int b;
SeqQueue<BTNode<T>*> node(20);
node.EnQueue(root);
cout<<\"以(数据 属性)格式按层次输入数据:\"<<endl;
cout<<\"属性:0:无孩子 1:只有左孩子 2:只有右孩子 3:有两个孩子:\"<<endl;
in>>a>>b;
while(!node.IsEmpty()){
p=node.Front()=new BTNode<T>(a);
node.DeQueue();
in>>a>>b;
switch(b){
case 3:node.EnQueue(p->lchild);
case 2:node.EnQueue(p->rchild);break;
case 1:node.EnQueue(p->lchild);break;
case 0:
default:break;
}
}
}
template<class T>
void BTree<T>::Output(ostream& out)
{
cout<<\"请选择遍历顺序:\"<<endl;
cout<<\"<1,先序 2,中序 3,后序 4,按层次 0,所有顺序 其他键返回>:\";
int a;cin>>a;
switch(a){
case 1:out<<\" 先序:\";
PreOrder(root);out<<endl;break;
case 2:out<<\" 中序:\";
InOrder(root);out<<endl;break;
case 3:out<<\" 后序:\";
PostOrder(root);out<<endl;break;
case 4:out<<\"按层次:\";
PostOrder(root);out<<endl;break;
case 0:
out<<\" 先序:\";PreOrder(root);out<<endl;
out<<\" 中序:\";InOrder(root);out<<endl;
out<<\" 后序:\";PostOrder(root);out<<endl;
out<<\"按层次:\";PostOrder(root);
default:out<<endl;break;
}
}
/*template<class T>
void BTree<T>::BreakTree(T& e,BTree<T>&left,BTree<T>&right)
{
BTNode<T>* p=root;
if(p){
e=p->element;
left.root=p->lchild;
right.root=p->rchild;
}
delete p;
}*/
template<class T>
int BTree<T>::Height(BTNode<T>* t)
{
if(!t)return 0;
static int lh=1,rh=1;
if(t->lchild)lh+=Height(t->lchild);
if(t->rchild)rh+=Height(t->rchild);
return lh>rh?lh:rh;
}
template<class T>
int BTree<T>::LeafNum(BTNode<T>* t)
{
if(!t)return 0;
static int l=0;//在递归调用中这样的赋值执行几次?
if(!t->lchild&&!t->rchild)return 1;
if(t->lchild)l+=LeafNum(t->lchild);
if(t->rchild)l+=LeafNum(t->rchild);
return l;
}
template<class T>
void BTree<T>::Copy(BTNode<T>* r,BTNode<T>* t)
{
if(r!=t){
delete r;
r=new BTNode<T>(t->element);
if(t->lchild)Copy(r->lchild,t->lchild);
if(t->rchild)Copy(r->lchild,t->lchild);
}
}
template<class T>
void BTree<T>::PermuteLR(BTNode<T>* t)
{
BTNode<T> *temp;
if(!t)return;
if(t->lchild||t->rchild){
temp=t->lchild;
t->lchild=t->rchild;
t->rchild=temp;
if(t->lchild)PermuteLR(t->lchild);
if(t->rchild)PermuteLR(t->rchild);
}
}
template<class T>
void BTree<T>::PreOrder(BTNode<T>* t)
{
if(t){
cout<<t<<\" \";
if(t->lchild)PreOrder(t->lchild);
if(t->rchild)PreOrder(t->rchild);
}
}
template<class T>
void BTree<T>::InOrder(BTNode<T>* t)
{
if(t){
if(t->lchild)InOrder(t->lchild);
cout<<t<<\" \";
if(t->rchild)InOrder(t->rchild);
}
}
template<class T>
void BTree<T>::PostOrder(BTNode<T>* t)
{
if(t){
if(t->lchild)PostOrder(t->lchild);
if(t->rchild)PostOrder(t->rchild);
cout<<t<<\" \";
}
}
template<class T>
void BTree<T>::LayerOrdor(BTNode<T>* t)
{
SeqQueue<BTNode<T>*> node(30);
BTNode<T> *p=t;
node.EnQueue(p);
while(!node.Isempty()){
p=node.Front();
node.DeQueue();
cout<<p<<\" \";
if(p->lchild)node.EnQueue(p->lchild);
if(p->rchild)node.EnQueue(p->rchild);
}
}
template<class T>
void BTree<T>::DestroyBTree(BTNode<T>* t)
{
if(t){
if(t->lchild)DestroyBTree(t->lchild);
if(t->rchild)DestroyBTree(t->rchild);
delete t;//delete t以后,t这个指针还存在吗?
}
}
template<class T>
istream& operator>>(istream& in,BTree<T>& b)
{
int a;
cout<<\"选择要输入的二叉树的类型:0:完全二叉树 1:一般二叉树\"<<endl;
cin>>a;
if(a==0){
cout<<\"设定输入停止符号:\";
b.SetFlag();
b.InputPerfTr(in);
}
else if(a==1)
b.InputAnyTr(in);
else return in;
return in;
}
template<class T>
ostream& operator<<(ostream& out,BTree<T>& b)
{
b.Output(out);
return out;
}
#include\"iostream.h\"
template<class T> class BTree;
template<class T>
class BTNode
{
public:
BTNode(){lchild=rchild=0;}
BTNode(const T& e)
{
element=e;
lchild=rchild=0;
}
BTNode(const T& e,BTNode<T>* l,BTNode<T>* r)
{
element=e;
lchild=l;
rchild=r;
}
private:
T element;
BTNode<T> *lchild,*rchild;
friend class BTree<T>;
friend ostream& operator<<(ostream& out,BTNode<T>& a);
};
template<class T>
ostream& operator<<(ostream& out,BTNode<T>& a)
{
out<<a.element<<\" \";
return out;
}
#include\"BTNode.h\"
template<class T>
class BTree
{
public:
BTree(){root=NULL;}//创建一颗空树
BTree(T c){flag=c;root=NULL;}//指定输入结束标志
~BTree(){DestroyBTree(root);}//释放一棵树
void SetFlag();//设定输入结束标志
bool IsEmpty()const;//判空
bool Root(T& x)const;//返会根节点
int Height(){return Height(root);}//计算树的高度
int LeafNum(){return LeafNum(root);}//计算树中叶子个数
BTree<T> operator=(BTree<T> &bt)//复制一棵树
{
flag=bt.flag;
Copy(root,bt.root);
return *this;
}
void PermuteLR(){PermuteLR(root);}//置换左右子树
protected:
T flag;//输入结束标志
BTNode<T>* root;
private:
//void MakeTree(const T& e,BTree<T>&left,BTree<T>&right);
void InputPerfTr(istream& in);
void InputAnyTr(istream& in);
void Output(ostream& out);
//void BreakTree(T& e,BTree<T>&left,BTree<T>&right);
int Height(BTNode<T>* t);
int LeafNum(BTNode<T>* t);
void Copy(BTNode<T>* r,BTNode<T>* t);
void PermuteLR(BTNode<T>* t);
void PreOrder(BTNode<T>* t);//前序遍历
void InOrder(BTNode<T>* t);//中序遍历
void PostOrder(BTNode<T>* t);//后序遍历
void LayerOrdor(BTNode<T>* t);//按层次遍历
void DestroyBTree(BTNode<T>* t);
friend istream& operator>>(istream& in,BTree<T>&);
friend ostream& operator<<(ostream& out,BTree<T>&);
};
#include\"BTree.cpp\"
void main()
{
BTree<char> a,b;
char ch;
cout<<\"Input the Tree Of A:\"<<endl;
cin>>a;
cout<<\"The Tree Of A Is:\"<<endl<<a;
a.Root(ch);
cout<<\" Root:\"<<ch<<endl;
cout<<\"Leaves:\"<<a.LeafNum()<<endl;
cout<<\"Height:\"<<a.Height()<<endl;
cout<<endl;
cout<<\"Input the Tree Of B:\"<<endl;
cin>>b;
cout<<\"The Tree Of B Is:\"<<endl<<b;
b.Root(ch);
cout<<\" Root:\"<<ch<<endl;
cout<<\"Leaves:\"<<b.LeafNum()<<endl;
cout<<\"Height:\"<<b.Height()<<endl;
cout<<endl;
a=b;
cout<<\"The Tree Of A After \\"A=B\\" Is:\"<<endl;
cout<<a;
cout<<\"Leaves:\"<<a.LeafNum()<<endl;
cout<<\"Height:\"<<a.Height()<<endl;
cout<<endl;
a.PermuteLR();
cout<<\"The Tree Of A After Permuted Is:\"<<endl;
cout<<a;
cout<<endl;
}
[此贴子已经被作者于2006-7-6 18:52:38编辑过]