数据结构DAY5--二叉树相关流程

流程有：创建->遍历->得到信息->销毁 

创建

根据先序遍历的流程以及对叶子结点的左后驱结点和右后驱结点以#号替代的原则，写出一个数组，并建立一个结构体，包括数据域，结构体类型的左后驱结点和右后驱结点指针。

typedef struct tree_node
{
	BTint data;//任意数据类型
	struct tree_node *pl;
	struct tree_node *pr;
}TREE_NODE;
 
char tree[] = "ABC##EH###DF##G##";

以上述两者为基础，建立函数：初始化一个数据，其值为创建的数组，数组角标为一个全局变量，以便于在树中插入数据，用结构体定义一个指针，大小为结构体大小，使其数据域为数组中的值，左右后驱结点指向函数自身（回调以创造子结点）最后返回该指针结点---当数组数据为#时，直接返回NULL，以结束创建过程。

TREE_NODE *create_Btree()
{
	BTDATA_TYPE data = tree[idx++];
	if (data == '#')
	{
		return NULL;
	}
 
	TREE_NODE *pnode = malloc(sizeof(TREE_NODE));
	if (NULL == pnode)
	{
		perror("fail malloc");
		return  NULL;
	}
	pnode->data = data;
	pnode->pl = create_Btree();
	pnode->pr = create_Btree();
 
	return pnode;
}

遍历

前序

输入树，若树指向空则返回（证明从根节点到叶子结点一条线已经遍历完了），打印根结点（数据域），然后以左结点为新的根结点回调自身，再以左结点为新的根结点回调自身，即遍历完毕。

void pre_order(TREE_NODE *proot)
{
	if (NULL == proot)
	{
		return ;
	}
	printf("%c", proot->data);
	pre_order(proot->pl);
	pre_order(proot->pr);
}

中序

void mid_order(TREE_NODE *proot)
{
	if (NULL == proot)
	{
		return ;
	}
 
	mid_order(proot->pl);
	printf("%c", proot->data);
	mid_order(proot->pr);
}

后序

void pos_order(TREE_NODE *proot)
{
	if (NULL == proot)
	{
		return ;
	}
	
	pos_order(proot->pl);
	pos_order(proot->pr);
	printf("%c", proot->data);
}

遍历以回调函数为主，看似复杂且难以理解，实际步骤很简单，以下以前序遍历为例做过程分析：

1.打印出A->2.以B为新的根结点，回调自身->3.打印B->4.以B为新的根结点，回调自身->

5.打印C->6.以C的左结点为新的根结点，回调自身->7.C的左结点为空，结束6返回上一级

->8.以C的右结点为新的根结点，回调自身->9.C的右结点为空，结束8返回上一级->10.C这一步回调函数运行结束，继续函数4的下一步，以B的右结点D为新的根结点，回调自身->11.与C的过程相同->12.B的函数运行结束，继续函数1的下一步->13.以E为新的根结点，回调自身->14.与C的过程相同->结束函数。

获得二叉树相关信息

获得二叉树的结点个数

传入树根结点，若树的结点为空，则返回0，否则返回1与以自身的左结点为根结点的回调函数与右以自身的右结点为根结点的回调函数，即可获得结点个数，其逻辑与前面遍历类似

int get_tree_node(TREE_NODE *proot)
{
	if (NULL == proot)
	{
		return 0;
	}
	return 1+get_tree_node(proot->pl)+get_tree_node(proot->pr);
}

获得二叉树的层数

其逻辑是获得所有分支的层数，然后通过对比获得最大值，就是二叉树的层数，思想与遍历类似，使用回调函数来实现：首先将根结点输入函数，若函数为空，则返回0，接着以左结点为根结点回调自身，然后以左结点为根结点回调自身，最后返回左右分支中最大的一只，并加上根结点这一层，就是层数

int get_btree_layer_cnt(TREE_NODE *proot)
{
	if (NULL == proot)
	{
		return 0;
	}
	int layL = get_btree_layer_cnt(proot->pl);
	int layR = get_btree_layer_cnt(proot->pr);
 
	return layL > layR ? layL+1 : layR+1;
}

销毁

与遍历思想类似：只不过是把打印换为了释放空间：

void destroy_btree(TREE_NODE *proot)
{
	if (NULL == proot)
	{
		return ;
	}
	destroy_btree(proot->pl);
	destroy_btree(proot->pr);
	free(proot);
}