0x01概述
什么是二叉树？
二叉树是 n (n >= 0)个结构的有限集合,改集合或者为空集(称为空二叉树),或者有一个根节点和两棵互不相交的、分别称为根节点的左子树和右子树的二叉树组成。
0x02 特殊的二叉树
这里主要记录一下特殊的二叉树，满二叉树和完全二叉树，比较典型。
- 满二叉树
-
什么是满二叉树？
在一棵二叉树中,如果所有的分支节点都存在左子树和右子树,并且所有叶子都在同一层面上,这样的二叉树成为满二叉树。
满二叉树的特点
(1) 满二叉树的叶子只能出现在最下一层,出现在其它层就不可能达成平衡。
(2) 非叶子节点的度一定是2。
(3) 在同样深度的热茶树中,满二叉树的节点个数最多,叶子数最多。
- 完全二叉树
-
什么是完全二叉树？
对于一棵具有 n 个节点的二叉树按层序编号,如果编号为 i ( 1<= i <= n)的节点与同样深度的满二叉树中编号为 i 的节点在二叉树中位置完全相同,则这棵二叉树成为完全二叉树。
完全二叉树的特点
(1) 完全二叉树的叶子节点只能出现在最下面的两层.
(2) 最下层的叶子一定集中在左部的连续位置.
(3) 倒数二层,若有叶子节点,则一定在右部的连续位置/
(4) 如果结点度为1,则该结点只有有孩子,即不存在只有右子树的情况.
(5) 同样结点书的二叉树,完全二叉树的深度最小.
0x03 二叉树的性质
在二叉树的第i层上有至多2**(i-1) (i>=1)个节点。
深度为K的二叉树至多有2**K - 1个节点
对于任意一颗二叉树，如果其叶子结点数为N0，度为2的节点数为N2，那么N2=N0+1
具有N个节点的完全二叉树的深度为[log2(n)]+1 （[X]为不大于X的最大整数）
如果对一棵有 n 个结点的完全二叉树(其深度为[log (2) n] + 1) 的结点按层序编号(从第1层到第[log (2) n] + 1 层,每一层从左到右),对任一结点i (1 <= i <= n) 有:
- 如果 i = 1 ,则结点i是二叉树的根,无双亲;如果i > 1,则其双亲是结点 [ i /2 ];
- 如果2i > n,则结点i无左孩子(结点i为叶子结点);否则其左孩子是结点2i;
- 如果2i +1 > n,则结点i无右孩子;否则其右孩子是结点2i +1;
0x04 二叉树的遍历
二叉树的遍历常用的有前序遍历，中序遍历，后序遍历
- 前序遍历
前序遍历就是先访问根节点，然后遍历左子树，再遍历右子树；在遍历左子树的时候也先访问根节点，然后左子树，然后右子树。。。
- 中序遍历
中序遍历就是先访问左子树，再访问根节点，最后访问右子树。
- 后序遍历
后序遍历就是先访问左子树，再访问右子树，最后访问根节点。
