二叉树（完美二叉树、完全二叉树、完满二叉树）

树的概念树的基本术语 二叉树（Binary Tree)什么是二叉树（Binary Tree)二叉树的性质完美二叉树(Perfect Binary Tree)完全二叉树(Complete Binary Tree)完满二叉树(Full Binary Tree) 比较区分完美二叉树 v.s. 完全二叉树完满(Full)二叉树 v.s. 完全(Complete)二叉树 v.s. 完美(Perfect)二叉树 遍历序列前序遍历（DLR）中序遍历（LDR）后序遍历（LRD） 实战训练

树的概念

树是由结点或顶点和边组成的(可能是非线性的)且不存在着任何环的一种数据结构。没有结点的树称为空(null或empty)树。一棵非空的树包括一个根结点，还(很可能)有多个附加结点，所有结点构成一个多级分层结构。

树的基本术语

根： 树的顶端结点；孩子：当远离根(Root)的时候，直接连接到另外一个结点的结点被称之为孩子(Child) ；双亲：相应地，另外一个结点称为孩子(child)的双亲(parent)；兄弟：具有同一个双亲(Parent)的孩子(Child)之间互称为兄弟(Sibling)；叶子（终端结点）：没有孩子的结点(也就是度为0的结点)称为叶子(Leaf)或终端结点；分支(非终端结点)：至少有一个孩子的结点称为分支(Branch)或非终端结点；度：结点所拥有的子树个数称为结点的度(Degree)；层次：结点的层次(Level)从根(Root)开始定义起，根为第0层，根的孩子为第1层。以此类推，若某结点在第i层，那么其子树的根就在第i+1层；结点的高度：结点的高度是该结点和某个叶子之间存在的最长路径上的边的个数；树的高度：树的高度是其根结点的高度；结点的深度：结点的深度是从树的根结点到该结点的边的个数。 （注：树的深度指的是树中结点的最大层次）

二叉树（Binary Tree)

什么是二叉树（Binary Tree)

每个结点至多拥有两棵子树(即二叉树中不存在度大于2的结点)，并且，二叉树的子树有左右之分，其次序不能任意颠倒。

二叉树的性质

（1）若二叉树的层次从0开始，则在二叉树的第i层至多有2^i个结点(i>=0)。

（2）高度为k的二叉树最多有2^(k+1) - 1个结点(k>=-1)。 (空树的高度为-1)

（3）对任何一棵二叉树，如果其叶子结点(度为0)数为m, 度为2的结点数为n, 则m = n + 1。

完美二叉树(Perfect Binary Tree)

一个深度为k(>=-1)且有2^(k+1) - 1个结点的二叉树称为完美二叉树。 (注： 国内的数据结构教材大多翻译为"满二叉树")。

完全二叉树(Complete Binary Tree)

完全二叉树从根结点到倒数第二层满足完美二叉树，最后一层可以不完全填充，其叶子结点都靠左对齐。

完满二叉树(Full Binary Tree)

所有非叶子结点的度都是2。（只要你有孩子，你就必然是有两个孩子。）

比较区分

完美二叉树 v.s. 完全二叉树

那么，将编号为15, 14, …, 9的叶子结点从右到左依次拿掉或者拿掉部分，则是一棵完全(Complete)二叉树,例如:

下图就不是一棵完全(Complete)二叉树:

完满(Full)二叉树 v.s. 完全(Complete)二叉树 v.s. 完美(Perfect)二叉树

遍历序列

前序遍历（DLR）

前序遍历，是二叉树遍历的一种，也叫做先根遍历、先序遍历、前序周游，可记做根左右。前序遍历首先访问根结点然后遍历左子树，最后遍历右子树。

中序遍历（LDR）

中序遍历是二叉树遍历的一种，也叫做中根遍历、中序周游。在二叉树中，中序遍历首先遍历左子树，然后访问根结点，最后遍历右子树。

后序遍历（LRD）

后序遍历（LRD）是二叉树遍历的一种，也叫做后根遍历、后序周游，可记做左右根。后序遍历有递归算法和非递归算法两种。在二叉树中，先左后右再根，即首先遍历左子树，然后遍历右子树，最后访问根结点。

实战训练

1、一棵完美二叉树共个结点，则叶子结点有多少个？

计算：叶子结点=总结点/2 = 1009

2、一棵完全二叉树共个结点，则叶子结点有多少个？

计算：-1024+1 = 995

3、一棵度为2的树与一棵二叉树有什么区别？

简答：度为2的树从形式上看与二叉树很相似,但它的子树是无序的,而二叉树是有序的。即,在一般树中若某结点只有一个孩子，则无需区分左右次序，而在二叉树中即使一个孩子也要有左右之分。

4、已知二叉树的中序遍历序列是DBGEAFHC,后序遍历序列是DGEBHFCA,请构造一棵二叉树,并给出前序遍历序列？

解析： ABDEGCFH