july-class-02（树）

二叉树遍历

前序遍历：根左右 中序遍历：左根右 后序遍历：左右根

层次遍历：使用队列

//先序遍历
void PreOrderTraverse(BiTree T){
	if(T){
		printf("%c",T->data);
		PreOrderTraverse(T->lchild);
		PreOrderTraverse(T->rchild);
	}
}
//中序遍历
void InOrderTraverse(BiTree T){
	if(T){
		InOrderTraverse(T->lchild);
		printf("%c",T->data);
		InOrderTraverse(T->rchild);
	}
}

//后序遍历
void PostOrderTraverse(BiTree T){
	if(T){
		PostOrderTraverse(T->lchild);
		PostOrderTraverse(T->rchild);
		printf("%c",T->data);
	}
}

二叉树的深度

int Depth(BiTree T){
	if(!T) return 0;
	int d1=Depth(T->lchild);
	int d2=Depth(T->rchild);
	return (d1>d2?d1:d2)+1;
}

二叉树的节点数

int NodeCount(BiTree T){
	if(!T) return 0;
	return NodeCount(T->lchild)+NodeCount(T->rchild)+1;
}

二叉树的叶子节点数

int LeafCount(BiTree T){
	if(!T) return 0;
	if(!T->lchild && !T->rchild) return 1;
	return LeafCount(T->lchild)+LeafCount(T->rchild);
}

判断两颗二叉树是否相同

bool IsSameTree(BiTree T1,BiTree T2){
	if(!T1 && !T2) return true;
	if(!T1 || !T2) return false;
	if(T1->data!=T2->data) return false;
	return IsSameTree(T1->lchild,T2->lchild)&&IsSameTree(T1->rchild,T2->rchild);
}