二叉树的实现
这是我复习的第三部分，二叉树的实现，这次需要的代码比较少，所以把主函数贴出来了，注释也很清晰，所以大家直接看代码吧：
//树
#ifndef?BINNODE_H
#define?BINNODE_H
template<class?Elem>
class?BinNode{
public:
virtual?Elem&?val()?=?0;
virtual?void?setVal(const?Elem&)?=?0;
virtual?void?setVal(?BinNode<Elem>*?b)?=?0;
virtual?BinNode*?left()?const?=?0;
virtual?void?setLeft(BinNode*)?=?0;
virtual?BinNode*?right()?const?=?0;
virtual?void?setRight(BinNode*)?=?0;
virtual?bool?isLeaf()?=?0;
};
#endif
?
//建树操作
#ifndef?BINNODEPTR_H
#define?BINNODEPTR_H
#include?"BinNode.h"
template?<class?Elem>
class?BinNodePtr:public?BinNode<Elem>{
private:
Elem?it;
BinNodePtr*?lc;
BinNodePtr*?rc;
public:
BinNodePtr(){lc?=?rc?=?NULL;}
BinNodePtr(Elem?e,BinNodePtr*?l?=?NULL,BinNodePtr*?r?=?NULL){
it?=?e;?lc?=?l;?rc?=?r;
}
~BinNodePtr(){}
Elem&?val(){
return?it;
}
void?setVal(const?Elem&?e){
it?=?e;
}
void?setVal(?BinNode<Elem>*?b){
?
}
inline?BinNode<Elem>*?left()const{return?lc;}
void?setLeft(BinNode<Elem>*?b){lc?=?(BinNodePtr*)b;}
????inline?BinNode<Elem>*?right()const{return?rc;}
void?setRight(BinNode<Elem>*?b){rc?=?(BinNodePtr*)b;}
bool?isLeaf(){
return?(lc==NULL)&&(rc==NULL);
}
};
#endif?BINNODEPTR_H
?
?
//树，这里实现了树的几种方法
//
//（1）前序遍历（DLR），首先访问根结点，然后遍历左子树，最后遍历右子树。简记根?-?左?-?右。
//
//（2）中序遍历（LDR），首先遍历左子树，然后访问根结点，最后遍历右子树。简记左?-?根?-?右。
//
//（3）后序遍历（LRD），首先遍历左子树，然后遍历右子树，最后访问根结点。简记左?-?右?-?根。
#include<iostream>
using?namespace?std;
#include"BinNode.h"
#include"BinNodePtr.h"
template?<class?Elem>
//建树
//??????????a
//?????????/?\
//????????b???c
//???????/?\???\
//??????d???e???f
//建立此二叉树的方法为：(abd??e??c?f??)
BinNode<Elem>*?CreateBinTree(){
BinNode<Elem>*?t;
char?ch;
if?((ch?=?getchar())?==?‘?‘)
{
//如果是空格表示空，后面没有节点了；
return?NULL;
}
else
{
//输入值
t?=?new?BinNodePtr<Elem>(ch);
//左孩子
t->setLeft(CreateBinTree<Elem>());
//右孩子
t->setRight(CreateBinTree<Elem>());
}
return?t;
}
template?<class?Elem>
//复制该树
BinNode<Elem>*?CopyBinTree(BinNode<Elem>*?p){
BinNode<Elem>*?t;
t=?new?BinNodePtr();
t->setVal(p->val());
if?(t->val()==NULL)return?NULL;
else
{
t->setLeft(CopyBinTree<Elem>(p->left()));
t->setRight(CopyBinTree<Elem>(p->right()));
}
return?t;
}
template?<class?Elem>
//输出单个节点
void?visit(BinNode<Elem>*?subroot){
cout<<subroot->val();
}
template?<class?Elem>
//前序
void?preorder(BinNode<Elem>*?subroot){
if(subroot?==?NULL)?return;
visit(subroot);//根
preorder(subroot->left());//左
preorder(subroot->right());//右
}
template?<class?Elem>
//中序
void?inorder(BinNode<Elem>*?subroot){
if(subroot?==?NULL)?return;
inorder(subroot->left());//左
visit(subroot);//根
inorder(subroot->right());//右
?
}
//后序遍历
template?<class?Elem>
void?backorder(BinNode<Elem>*?subroot){
if?(subroot?==?NULL)?return;
backorder(subroot->left());//左
backorder(subroot->right());//右
visit(subroot);//根
?
}
template?<class?Elem>
//左右孩子互换
//我们仍然举一个例子
//??????????a
//?????????/?\
//????????b???c
//???????/?\???\
//??????d???e???f
void?swithOrder(BinNode<Elem>*?subroot){
//如果要置换的树是空的，结束
if(subroot==NULL)?return;
visit(subroot);
//声明一个空间，用来临时存放节点
BinNode<Elem>*?t;
char?ch=‘?‘;
t?=?new?BinNodePtr<Elem>(ch);
//t临时存放右边节点
//??????????a
//?????????/?\
//????????b???c
//???????/?\???\
//??????d???e???f
//t?=?b{d?e}
t=subroot->left();
//用右边的节点覆盖左边节点
//??????????a
//?????????/?\
//????????c???c
//?????????\???\
//??????????f???f
//t?=?b{d?e}
subroot->setLeft(subroot->right());
//把t付给右边节点
//??????????a
//????????/???\
//???????c?????b
//????????\????/\
//?????????f??d??e?
subroot->setRight(t);
//递归，最终结果为
//??????????a
//????????/???\
//???????c?????b
//??????/??????/\
//?????f??????e??d?
swithOrder(subroot->left());
swithOrder(subroot->right());
}
int?main(){
cout?<<?"请输入：abd（空格）（空格）e（空格）（空格）c（空格）f（空格）（空格）（回车）"?<<?endl;
BinNode<char>*?tree;
tree?=?CreateBinTree<char>();
inorder<char>(tree);
cout<<endl;
swithOrder<char>(tree);
????cout<<endl;
inorder<char>(tree);
cout?<<?endl;
backorder<char>(tree);
????cout<<endl;
system("pause");
}
?
原文：http://448230305.iteye.com/blog/2193726