二叉树遍历算法的应用

二叉树的建立：按先序遍历序列建立二叉树的二叉链表
（1）从键盘输入二叉树的结点信息，建立二叉树的存储结构
（2）在建立二叉树的过程中按照二叉树先序方式建立
算法：
Status CreateBiTree(BiTree &T){
scanf(&ch);
if(ch==”#”) T=NULL;
else{
if(!(T=(BiTNode *) malloc(sizeof(BiTNode))))
exit(OVERFLOW);
T->data = ch;//生成根结点
CreateBiTree(T->lchild);//构造左子树
CreateBiTree(T->rchild);//构造右子树
}
return OK;
}

复制二叉树
如果是空树，递归结束
否则，申请新结点空间，复制根结点
①递归复制左子树
②递归复制右子树
int Copy(BiTree t, BiTree & NewT){
if(T=NULL){ //如果是空树返回0
NewT =NULL; return 0;
}
else{
NewT =new BiTNode; NewT->data = T->data;
Copy(T->IChild, NewT ->Ichild);
Copy(T->rChild, NewT ->Ichild);
}
}

计算二叉树的深度
如果是空树，则深度为0
否则，递归计算左子树的深度记作m，递归计算右子树的深度记为n，二叉树的深度则为m与n的较大者加1
int Depth(BiTree T){
if(T=NULL){ return 0; //如果是空树返回0}
else{
m=Depth(T->lChild);
n=Depth(T->rChild);
if(m>n) return(m+1)；
else return(n+1);
}
}

计算二叉树结点总数
如果是空树，则结点个数为0
否则，结点个数为左子树的结点个数+右子树的结点个数+1
int NodeCount(BiTree T){
if(T=NULL)
return 0
else
return NodeCount(T->lChild)+NodeCount(T->rChild)+1;
}

计算二叉树叶子结点数
如果是空树，则结点个数为0
否则，结点个数为左子树的叶子结点个数+右子树的叶子结点个数
int LeadCount(BiTree T){
if(T=NULL)
return 0
if(T->lchild ==NULL && T->rchild ==NULL)
return 1;//如果是叶子结点返回1
else
return LeafCount(T->lchild) + LeafCount(T->rchild);
}