树 --- 二叉树

树的物理结构和逻辑结构上都是树形结构。

树形结构：由一个根和若干个子节点组成的集合。

叶子节点：最外围的节点，只有前驱而没有后继。

（一）树的性质

• ⼦树是不相交的
• 除了根结点外，每个结点有且仅有⼀个⽗结点

•度数：一个节点的子树的个数称为该节点的度数，一棵树的度数是指该树中节点的最大度数。

•度：当前节点的子节点为度

•广度：最大节点的度

•深度：树的层数

（二）树的种类

树按照根节点的分支来分，可以分为二叉树和多叉树。下面只介绍二叉树：

二叉树

二叉树（Binary Tree）
定义：每个节点最多有两个子节点的树结构。可以是空树，或者由一个根节点和左、右子树组成。

性质：二叉树广度为2

二叉树又分为满二叉树和完全二叉树

①满二叉树

满N叉树是一种深度为K的二叉树，其中每一层的节点数都达到了该层能有的最大节点数。如下图：

K层满二叉树节点为2 ^k -1

②完全二叉树

在满二叉树的基础上，如要删除节点，只能从右至左，从下至上依次删除若干节点。从左至右，从上至下添加节点。

前三种为深度优先遍历算法，层序遍历为广度优先算法

注：

只知道一个遍历结果，无法推测一颗唯一的二叉树。

已知前序加中序，可以确定一颗二叉树。

已知后续和中序，可以确定一颗二叉树。

前序遍历：

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

中序遍历：

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

后序遍历:

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

层序遍历：不使用递归

void  large_order(TNode_t*proot)
{
    QDataType outdata;
	Queue_t *pque = create_queue();	
	if (NULL == pque)
	{
		printf("fail create_queue\n");
		return ;
	}

	push_queue(pque, proot);
	while (!is_empty_queue(pque))
	{
		pop_queue(pque, &outdata);
		printf("%c", outdata->data);
		if (outdata->pl != NULL)
		{
			push_queue(pque, outdata->pl);
		}
		if (outdata->pr != NULL)
		{
			push_queue(pque, outdata->pr);
		}
	}

	destroy_queue(pque);
}