数据结构-二叉树

二叉树是数据结构中具有的一个 很有特色的类别。

二叉树顾名思义，每个节点最多有两个子节点，分别叫做左子节点和右子节点。

如果树的所有层，除了最后一层的节点外都是两个子节点，那么称这个树为满二叉树。

如果树只有最下面一层没有排满，且排好的都在左侧，那么称这个树为完全二叉树。（也就是所有的节点都连续集中在最左边）

树作为数据结构中最为基础的非线性结构，有很多重要的性质:


结点的度：一个结点的子树的个数记为该结点的度．

树的度：所有节点中度数最大的结节的度数，叶子节点的度为零。

树的高度：一棵树的最大层次数记为树的高度(或深度)。

有序(无序)树：若将树中结点的各子树看成是从左到右具有次序的，即不能交换，则称该树为有序树。否则称为无序树。

二叉树第i层（i≥1）上至多有2^(i-1)个节点。

深度为k的二叉树至多有2^k-1个节点（k≥1）。

对任何一棵二叉，若叶子节点数为n0，度为2的节点数为n2，则n0=n2+1。

具有n个节点的完全二叉树的深度为 (㏒2^n)(向下取整)+1。

对一棵有n个节点的完全二叉树的节点按层次从上到下，自左至右进行编号，则对任一节点i(1≤i≤n)有：若 i=1，则节点i是二叉树的根，无双亲；若 i>1，则其双亲为 i/2(向下取整)。若2i>n，则节点i没有孩子节点，否则其左孩子为2i。若2i+1>n，则节点i没有右孩子，否则其右孩子为2i+1。

若深度为k的二叉树有2^k-1个节点，则称其为满二叉树。满二叉树是一棵完全二叉树。


对于完全二叉树中，度为1的节点个数只可能为1个或0个。

对于二叉树，如果叶子节点数为n0，度为1的节点数为n1，度为2的节点数为n2，则节点总数n = n0 + n1 + n2。

对于任意树，总节点数 = 每个节点度数和 + 1

二叉树的高度等于根与最远叶节点（具有最多祖先的节点）之间分支数目。空树的高度是-1。只有单个元素的二叉树，其高度为0。

有了二叉树，就有了关于遍历的知识。

遍历是按某种策略访问树中的每个节点，且仅访问一次。

遍历二叉树实际上就是将一个非线性的二维结构给排列呈线性的过程。如果是顺序实现了二叉树的结构，自然底层就是线性的，无需转化。如果是纯链表实现呢，就需要将离散的节点重新组织组织了。

二叉树的遍历主要分为两大类：深度优先遍历、广度优先遍历。

对于深度优先遍历又分为三种模式：先根遍历、中根遍历、后根遍历。


深度优先遍历：就是优先访问树中最深层次的节点

广度优先遍历：就是从根往下一层一层遍历访问

先根遍历：先遍历根节点，之后处理其他子节点

中根遍历：先遍历根节点的左子树，之后遍历根节点，最后遍历右子树

后根遍历：先遍历根节点的左子树，之后遍历右子树，最后遍历根节点