编辑代码

/*二叉树的存储结构及基本运算*/

# include<stdio.h>
# include<malloc.h>
# define TRUE 1
# define FALSE 0

/*二叉树的链式存储结构*/
typedef char DataType;
typedef struct Node {
	DataType data;
	struct Node* LChild;
	struct Node* RChild;
}BiTNode, * BiTree;

BiTree T;

/*建立二叉链表方式存储的二叉树（按扩展先序遍历序列）*/
void CreateBiTree(BiTree* T) {
//'.'表示空子树
	char ch;
	ch = getchar();
	if (ch == ' ')									//'.'表示空子树
		*T = NULL;
	else {
		(*T) = (BiTree)malloc(sizeof(BiTNode));
		(*T)->data = ch;							//生成根结点
		CreateBiTree(&((*T)->LChild));				//构造左子树
		CreateBiTree(&((*T)->RChild));				//构造右子树
	}
}

/*先序遍历二叉树（递归）*/
void PreOrder(BiTree T) {
	if (T != NULL) {
		printf("%c ", T->data);				//输出结点值
		PreOrder(T->LChild);					//先序遍历左子树
		PreOrder(T->RChild);					//先序遍历右子树
	}
}

/*中序遍历二叉树（递归）*/
void InOrder(BiTree T) {
	if (T != NULL) {
		InOrder(T->LChild);					//中序遍历左子树
		printf("%c ", T->data);				//输出结点值
		InOrder(T->RChild);					//中序遍历右子树
	}
}

/*后序遍历二叉树（递归）*/
void PostOrder(BiTree T) {
	if (T != NULL) {
		PostOrder(T->LChild);					//后序遍历左子树
		PostOrder(T->RChild);					//后序遍历右子树
		printf("%c ", T->data);				//输出结点值
	}
}

/*后序遍历统计叶子结点数目*/
int count = 0;
void LeafCount(BiTree T) {
	if (T != NULL) {
		LeafCount(T->LChild);
		LeafCount(T->RChild);
		if (T->LChild == NULL && T->RChild == NULL)
			count++;
	}
}

/*后序遍历求二叉树高度*/
int PostTreeDepth(BiTree T) {
	int lh = 0, rh = 0, h;
	if (T != NULL) {
		lh = PostTreeDepth(T->LChild);
		rh = PostTreeDepth(T->RChild);
		h = lh > rh ? lh : rh;
		return (h + 1);
	}
	else
		return 0;
}


int main() {
    CreateBiTree(&T);
	printf("先序遍历：");
	PreOrder(T);

	printf("\n中序遍历：");
	InOrder(T);

	printf("\n后序遍历：");
	PostOrder(T);

	LeafCount(T);
    printf("\n树的深度：%d", PostTreeDepth(T));

	printf("\n叶结点数：%d", count);

	return 0;
}