【数据结构】二叉树的操作2

#include <stdio.h>
#include <stdlib.h>

typedef char ElemType;
typedef struct BiTree
{
    ElemType elem;
	BiTree * LChild;
	BiTree * RChild;
}BiTree,* PBiTree;

/*先序顺序创建二叉树*/
PBiTree CreateBiTree();
/*先序顺序遍历二叉树*/
void PreOrderTraverse(PBiTree T);
/*中序顺序遍历二叉树*/
void InOrderTraverse(PBiTree T);
/*后序顺序遍历二叉树*/
void PostOrderTraverse(PBiTree T);
/*遍历查找叶子节点*/
void TravelLeadNode(PBiTree T);
/*计算树的高度*/
int CountTreeHeight(PBiTree T);

int main()
{
	PBiTree Tree;
	int TreeHeight = 0;

	printf("按照先序顺序创建二叉树：n");
	Tree = CreateBiTree();
	
	printf("n按照先序顺序输出n");	
	PreOrderTraverse(Tree);
	
	printf("n按照中序顺序输出n");	
	InOrderTraverse(Tree);
	
	printf("n按照后序顺序输出n");	
	PostOrderTraverse(Tree);
	
	printf("n叶子结点为：n");
	TravelLeadNode(Tree);

	TreeHeight = CountTreeHeight(Tree);
	printf("n树的深度为：%dn",TreeHeight);
	
	return 0;
}

PBiTree CreateBiTree()
{
	PBiTree Tree = NULL;
	ElemType elem = '';
	scanf("%c",&elem);
	
	if (elem == '#')
	{
		Tree = NULL;
	}
	else
	{
		Tree = (PBiTree)malloc(sizeof(BiTree));
		Tree->elem = elem;
		Tree->LChild = CreateBiTree();
		Tree->RChild = CreateBiTree();
	}
	
	return Tree;
}


void PreOrderTraverse(PBiTree T)
{
	if (T != NULL)
	{
		printf("%c ",T->elem);
		
		PreOrderTraverse(T->LChild);
		PreOrderTraverse(T->RChild);
	}
	else 
		return;
}


void InOrderTraverse(PBiTree T)
{
	if (T != NULL)
	{
		if (T->LChild != NULL)
		{
			InOrderTraverse(T->LChild);
		}
		
		printf("%c ",T->elem);	
		InOrderTraverse(T->RChild);	
	}
}


void PostOrderTraverse(PBiTree T)
{
	if (T != NULL)
	{
		if (T->LChild != NULL)
		{
			PostOrderTraverse(T->LChild);
		}
		
		PostOrderTraverse(T->RChild);	
		printf("%c ",T->elem);
	}
}


void TravelLeadNode(PBiTree T)
{
	if (T != NULL)
	{
		if (T->LChild == NULL && T->RChild == NULL)
		{
			printf("%c ",T->elem);
		}
		
		TravelLeadNode(T->LChild);
		TravelLeadNode(T->RChild);
	}
}


int CountTreeHeight(PBiTree T)
{
	if (T != NULL)
	{
		return	CountTreeHeight(T->LChild) > CountTreeHeight(T->RChild) 
			? CountTreeHeight(T->LChild)+1 : CountTreeHeight(T->RChild)+1;
	}
	else
	{
		return 0;
	}
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!