树 --- 二叉树

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

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

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

•广度：最大节点的度

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

二叉树（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);
}