#include<iostream.h>
//#include"mystring.h"
#include<stack>
//#include<queue.cpp>
//二叉链表结点的类定义
using namespace std;
template<class T>
class binarytreenode
{
//friend class binarytree<T>;
private:
T info;
binarytreenode<T> * left;
binarytreenode<T> * right;
public:
//binarytreenode()
binarytreenode(T ele){info=ele;left=NULL;right=NULL;}
binarytreenode(T ele,binarytreenode<T> * l,binarytreenode<T> * r){info=ele;left=l;right=r;}
T value()const;
binarytreenode<T> * leftchild()const;
binarytreenode<T> * rightchild()const;
void setleftchild(binarytreenode<T> *l);
void setrightchild(binarytreenode<T> *l);
void setvalue(T val);
};
/*template<class T>
binarytreenode::binarytreenode()
{
left=null;
right=null;
}
template<class T>
binarytreenode::binarytreenode(T ele)
{
info=ele;
left=NULL;
right=NULL;
}
template<class T>
binarytreenode::binarytreenode(T ele,binarytreenode<T> * l,binarytreenode<T> * r)
{
info=ele;
left=l;
right=r;
}*/
template<class T>
T binarytreenode<T>::value()const
{
return info;
}
template<class T>
binarytreenode<T> * binarytreenode<T>::leftchild()const
{
return left;
}
template<class T>
binarytreenode<T> * binarytreenode<T>::rightchild()const
{
return right;
}
template<class T>
void binarytreenode<T>::setleftchild(binarytreenode<T> * l)
{
left=l;
}
template<class T>
void binarytreenode<T>::setrightchild(binarytreenode<T> * r)
{
right=r;
}
template<class T>
void binarytreenode<T>::setvalue(T val)
{
info=val;
}
//二叉链表的类定义
template<class T>
class binarytree
{
private:
binarytreenode<T> * root;
public:
binarytree(){root=NULL;}
~binarytree(){deletebinarytree(root);}
binarytreenode<T> * Root(){return root;}
binarytreenode<T> * parent(binarytreenode<T> * current);
binarytreenode<T> * leftsibling(binarytreenode<T> * current);
binarytreenode<T> * rightsibling(binarytreenode<T> * current);
void creattree(T info);
void creattree(T info,binarytree<T> & lefttree,binarytree<T> & righttree);
// void creattree(mystring<char> a);
void deletebinarytree(binarytreenode<T> * root);
void preorder1(binarytreenode<T> * root); //保存当前结点的前序周游
void preorder(binarytreenode<T> * root); //保存当前结点右孩子的前序周游
void inorder(binarytreenode<T> * root);
void postorder(binarytreenode<T> * root);
void levelorder(binarytreenode<T> * root);
int deep(binarytreenode<T> * current); //求出一个结点的深度
void numofleaf(binarytreenode<T> * root,int & i); //叶子个数
//void high(binarytreenode<T> * root,int & i); //高度
void shadow(binarytreenode<T> * root); //镜面影射
void commonp(binarytreenode<T> * p,binarytreenode<T> * q); //求两结点的最近的共同祖先
};
//找双亲
template<class T>
binarytreenode<T> * binarytree<T>::parent(binarytreenode<T> * current)
{
using std::stack;
binarytreenode<T> * pointer=root;
stack<binarytreenode<T> *> astack;
if(root==null||current==null)
return null;
while(!astack.isempty()||pointer)
{
if(pointer)
{
if(pointer.left=current||pointer.right=current)
return pointer;
astack.push(poiter);
pointer=pointer.left;
}
else
{
pointer=astack.top();
astack.pop();
pointer=pointer.right;
}
}
}
//找左兄弟
template<class T>
binarytreenode<T> * binarytree<T>::leftsibling(binarytreenode<T> * current)
{
binarytreenode<T> * pointer=parent(current);
return pointer.left;
}
//找右兄弟
template<class T>
binarytreenode<T> * binarytree<T>::rightsibling(binarytreenode<T> * current)
{
binarytreenode<T> * pointer=parent(current);
return pointer.right;
}
//生成新树
template<class T>
void binarytree<T>::creattree(const T info)
{
root=new binarytreenode<T> (info);
//l=r=NULL;
}
//生成新树
template<class T>
void binarytree<T>::creattree(T info,binarytree<T> & lefttree,binarytree<T> & righttree)
{
root=new binarytreenode<T> (info,lefttree.root,righttree.root);
lefttree.root=righttree.root=NULL;
}
//用字符串生成新树
/*template<class T>
void binarytree<T>::creattree(mystring<char> a)
{
using std::stack;
stack<binarytreenode<T> *> astack;
root=new binarytreenode<T> (a[0]);
binarytreenode<T> * pointer=root;
int i;
for(i=1;a[i]!='\0';i++)
{
if(a[i]=='(')
astack.push('(');
else if(a[i]==')')
{
astack.top();
pointer=rightsibling(pointer);
}
else
{
pointer.left=new binarytreenode<T> (a[i]);
pointer=pointer->leftchild();
}
}
}*/
//删除树
/*template<class T>
void binarytree<T>::deletebinarytree(binarytreenode<T> * root)
{
if(root!=NULL)
{
deletebinarytree(root->leftchild());
deletebinarytree(root->rightchild());
delete root;
}
}
//保存当前结点的前序周游
template<class T>
void binarytree<T>::preorder1(binarytreenode<T> * root)
{
using std::stack;
binarytreenode<T> * pointer=root;
stack<binarytreenode<T> *> astack;
while(!astack.empty()||pointer)
{
if(pointer)
{
cout<<pointer->value()<<'\t';
astack.push(pointer);
pointer=pointer->leftchild();
}
else
{
pointer=astack.top();
astack.pop();
pointer=pointer->rightchild();
}
}
}
//保存当前结点右孩子的前序周游
template<class T>
void binarytree<T>::preorder(binarytreenode<T> * root)
{
using std::stack;
binarytreenode<T> * pointer=root;
stack<binarytreenode<T> *> astack;
astack.push(NULL);
while(!astack.empty()||pointer)
{
if(pointer)
{
cout<<pointer->value() << " ";
//getchar();
if(pointer->rightchild()!=NULL)
astack.push(pointer->rightchild());
pointer=pointer->leftchild();
}
else
{
pointer=astack.top();
astack.pop();
}
}
}
//中序周游
template<class T>
void binarytree<T>::inorder(binarytreenode<T> * root)
{
using std::stack;
binarytreenode<T> * pointer=root;
stack<binarytreenode<T> *> astack;
while(!astack.isempty()||pointer)
{
if(pointer)
{
astack.push(pointer);
pointer=pointer.left;
}
else
{
pointer=astack.top();
cout<<pointer.info<<'\t';
pointer=poiter.right;
}
}
}
//后序周游
template<class T>
void binarytree<T>::postorder(binarytreenode<T> * root)
{
using std::stack;
enum tags{left,right};
template<T>
class stackelement
{
public:
binarytreenode<T> * pointer;
tags tag;
}
stack<stackelement<T> * > astack;
stackelement<T> element;
binarytreenode<T> * pointer=root;
while(!astack.isempty()||pointer)
{
while(pointer)
{
element.pointer=pointer;
element.tag=left;
astack.push(element);
pointer=pointer.leftchild();
}
element=astack.top;
pointer=element.pointer;
if(element.tag==left)
{
element.tag==right;
astack.push(element);
pointer=pointer.rightchild();
}
else
{
cout<<pointer.value();
pointer=null;
}
}
}
//求一个结点的深度
template<class T>
int binarytree<T>::deep(binarytreenode<T> * current)
{
int i;
binarytreenode<T> * pointer=null;
while(pointer!=root)
{
pointer=parent(current);
i++;
current=pointer;
}
return i;
}
//求叶结点个数
template<class T>
void binarytree<T>::numofleaf(binarytreenode<T> * root,int & i)
{
binarytreenode<T> * pointer=root;
if(pointer.leftchild()==pointer.rightchild()==null)
i++;
else
{
numofleaf(pointer.leftchild(),i);
numofleaf(pointer.rightchild(),i);
}
}
/*template<class T>
int binarytree<T>::high(binarytreenode<T> * root,int & i)
{
binarytreenode<T> * pointer=root;
if(pointer.leftchild()==pointer.rightchild()==null)
i++;
}*/
//将一棵树镜面影射
template<class T>
void binarytree<T>::shadow(binarytreenode<T> * root)
{
binarytreenode<T> * temp=null;
binarytreenode<T> * pointer=root;
using std::queue;
queue<binarytreenode<T> *> aqueue;
if(pointer)
aqueue.push(pointer);
while(! aqueue.isempty())
{
pointer=aqueue.front();
temp=pointer.left;
pointer.left=pointer.right;
pointer.right=temp;
if(pointer.leftchild())
aqueue.push(pointer.leftchild());
if(pointer.rightchild())
aqueue.push(pointer.rightchild());
}
}
//求两结点的最近的共同祖先
/*template<class T>
binarytreenode<T> * binarytree<T>::commonp(binarytreenode<T> * p,binarytreenode<T> * q)
{
binarytreenode<T> * m=p,* n=q;
if(deep(m)<deep(n))
while(deep(m)<deep(n))
n=parent(n);
else
while(deep(m)>deep(n))
m=parent(m);
while(m!=n)
{
m=parent(m);
n=parent(n);
}
return m;
}*/
void main()
{
//int i,j;
binarytree<char> a[7];
a[1].creattree('c');
a[2].creattree('d');
a[3].creattree('+',a[1],a[2]);
a[4].creattree('b');
a[5].creattree('*',a[4],a[3]);
a[6].creattree('a');
a[7].creattree('+',a[6],a[5]);
/* a[7].preorder(a[7].Root());
cout << endl;
a[7].preorder1(a[7].Root());
cout << endl;*/
/* binarytree<char> B;
char AA[13]="+(a*(b+(cd)))";
char * A=AA;//利用嵌套括号表示法
mystring aa(A);
B.creattree(aa);
B.creattree(B.Root());
B.numofleaf(B.Root(),i);
B.high(B.Root(),i);
B.preorder(B.Root());
B.shadow(B.Root());*/
}
累死了编了这么多，希望采纳