|
目录
1.建立二叉树
2.复制二叉树
3.计算二叉树的深度
?4.计算二叉树结点总数
5.计算二叉树的叶子结点数
1.建立二叉树
算法思想：按照先序遍历序列建立二叉树的二叉链表，由于已知一种先序序列可以构造出多棵不同的二叉树，我们在这里引入在先序序列中增加“#”的算法解决这个问题
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;
}
2.复制二叉树
算法思想：如果是空树，递归结束；否则，申请新的结点空间，复制根结点，再依次递归复制左子树和右子树
Status CopyBiTree(BiTree T,BiTree &NewT){
if(T=NULL) return NULL;
else{
T=(BiTNode*)malloc(sizeof(BiTNode));
NewT->data=T->data;
CopyBiTree(T->lchild);//复制左子树
CopyBiTree(T->rchild); //复制右子树
}
}
3.计算二叉树的深度
算法思想：如果是空树，则深度为0；否则，递归计算左子树的深度，再递归计算右子树的深度，二叉树的深度为二者中较大者+1
int DepthBiTree(BiTree T){
if(T=NULL) return 0;
else{
m=DepthBiTree(T->lchild);
n=DepthBiTree(t->rchild);
return (m>n?m:n)+1;
}
}
?4.计算二叉树结点总数
算法思想：如果是空树，则结点个数为0；否则，结点个数为左子树的结点个数+右子树的结点个数+1
int NodeCount(BiTree T){
if(T=NULL) return 0;
else
{
return NodeCount(T->lchild)+NodeCount(T->rchild)+1;
}
}
5.计算二叉树的叶子结点数
算法思想：如果是空树，则叶子结点个数为0；否则，为左子树的叶子结点个数+右子树的叶子结点个数
int LeafCount(BiTree T){
if(T=NULL) return 0;
if(T->lchild&&T->rchild){
return 1;
}
else{
return LeafCount(lchild)+LeafCount(rchild);
}
}
二叉树的遍历算法虽然代码量简短，但理解起来相对困难，理解有困难的同学可以与我交流
|