目录

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);
	}
}

二叉树的遍历算法虽然代码量简短，但理解起来相对困难，理解有困难的同学可以与我交流