前序遍历

template
void BinTree::PreOrder(BinTreeNode*subTree){
//前序遍历以subTree为根的树
if(subTree!=NULL){
cout<data<leftChild);
PreOrder(subTree->rightChild);
}
}

中序遍历

template
void BinTree::InOrder(BinTreeNode*subTree){
//中序遍历以subTree为根的树
if(subTree!=NULL){//NULL是递归终止条件
InOrder(subTree->leftChild);//中序遍历左子树
cout<data<rightChild);//中序遍历右子树
}
}

后序遍历

template
void BinTree::PostOrder(BinTreeNode*subTree){
//后序遍历以subtree为根的树
if(subTree!=NULL){
PostOrder(subTree->leftChild);
PostOrder(subTree->rightChild);
cout<data<<endl;
}
}

已知中序排列，和先序排列，可以还原二叉树，并推出后序排列。
已知中序排列，和后序排列，可以还原二叉树，并推出先序排列。
但是已知先序排列和后序排列，可能无法唯一确定二叉树。

层次序遍历，需要用到队列

template
void BinTree::LevelOrder(BinTreeNode*subTree) {
//层次序遍历以subTree为根的二叉树
Queue*>Q;//定义队列
BinTreeNode*p=subTree;
Q.EnQueue(p);//根结点入队
while(!Q.IsEmpty()){//队列不空
Q.DeQueue(p);
cout<data;
if(p->leftChild!=NULL) Q.EnQueue(p->leftChild);//左子入队
if(p->rightChild!=NULL) Q.EnQueue(p->rightChild);//右子入队
}
}

遍历看完后，接下来是遍历的应用以及遍历思想的应用

前序遍历的应用——复制构造函数与复制函数

template
BinTree::BinTree(const BinTree&s){
//复制构造函数
root=Copy(s.root);
}
template
BinTreeNode* BinTree::Copy(BinTreeNode*orignode){
//返回一个指针，它给出一个以orignode为根的二叉树的副本
if(orignode==NULL) return NULL;
BinTreeNode*temp=new BinTreeNode;//创建根结点
temp->data=orignode->data;
temp->leftChild=Copy(orignode->leftChild);
temp->rightChild=Copy(orignode->rightChild);
return temp;
}

前序遍历的应用——判断两颗二叉树是否相等

template
bool equal(BinTreeNode*a,BinTreeNode*b){
//为BinTree类的友元函数
if(a==NULL&&b==NULL) return true;
if(a!=NULL&&b!=NULL&&a->data==b->data&&equal(a->leftChild,b->leftChild)&&equal(a->rightChild,b->rightChild)) return true;
else return false;
}

前序遍历的应用——利用前序遍历建立二叉树

约定以输入序列中不可能出现的值作为空结点的值以结束递归，此值在RefValue中，如#
template
void BinTree::CreatBinTree(ifstream& in,BinTreeNode*&subTree){
//以递归的方式建立二叉树
T item;
if(!in.eof()){//未读完，读入并建树
in>>item;
if(item!=RefValue){
subTree->data=item;
CreatBinTree(in,subTree->leftChild);//递归建立左子树
CreatBinTree(in,subTree->rightChild);//递归建立右子树
}
else subTree=NULL;
}
}

后序遍历的应用——计算结点的个数

template
int BinTree::Size(BinTreeNode*subTree) const{
//计算以subTree为根的二叉树的结点的个数
;//递归结束
+Size(subTree->leftChild)+Size(subTree->rightChild);
}

后序遍历的应用——计算树的高度

template
int BinTree::Height(BinTreeNode*subTree) const{
//计算以subTree为根的二叉树的高度
;
+max(Height(subTree->leftChild),Height(subTree->rightChild));
}