二叉树

如果树中每个节点最多只能有两个子节点，这样的树就成为”二叉树”
二叉树的重要性，不仅仅是因为简单，也因为 几乎上所有的树都可以表示成二叉树的形式

二叉树的定义

二叉树可以为空，也就是没有节点
若不为空，则它是由根节点和称为其左子树TL和右子树TR的两个不相交的二叉树组成

二叉树的特性

一个二叉树第i层的最大节点数为：2^(i-1)， i>=1;
深度为k的二叉树由最大节点总数位： 2^k - 1, k>=1
对任何非空二叉树T,若n0表示叶节点的个数、n2是度为2的非叶节点个数，那么两者满足关系n0=n2+1
二叉树的节点个数假设为n，那么一共有n - 1条边(每两个节点一条边)=>可得到等式n0 + n1 + n2（n0是节点为0的个数，n1是节点为1的个数，n2是节点为2的个数） = 边的个数 = n1 + 2n2 + 1 ==>n0 = n2 + 1

二叉树的存储常见的的方式是数组和链表

使用数组：
完全二叉树：按从上至下，从左只有顺序存储
非完全二叉树：非完全二叉树要转成完成才能按照上面的方案存储（使用数组），但是会造成很大的空间浪费

二叉树最常见的方式还是使用链表存储

每个节点封装成一个Node,Node中包含存储的数据，左节点的引用，右节点的引用

学习二叉树的作用

• 二叉树是理解高级数据结构的基础

  完全二叉树-堆、优先队列
  多叉树/森林-字典树、AC自动机、并查集
  二叉排序树(BST)-AVL树、2-3树、红黑树、B-树、B+树

• 二叉树是练习递归技巧的最佳选择

  设计/理解递归程序：
  (1)数学归纳法-》结构归纳法(k0正确，我们假设ki->k-+1是正确的)=>联立第一和第二步
  (2)赋予递归函数一个明确的意义
  (3)思考边界问题
  (4)实现递归过程

• 学习二叉树后，可以使用左孩子右兄弟法来节省空间

  例子：   1                     1
      	/ | \                    /
      	2 3 4      =>           2
       	   /\                   \
       	  5 6                   3
                                / \
                                5  4
                                 \
                                  6

  三叉树每个节点中存放了三个指针域：左边6个节点->63=18个指针域=》有多少个有效指针域：5条边 =>浪费了18 - 5 = 13个指针域
  二叉树每个节点中存放了二个指针域：6 * 2 = 12个指针，=》有多少个有效指针域：5条边，5个指针域=》浪费了12 - 5= 7个指针域
  可以得到n个节点的k叉树：一个有n*k个指针域，有n-1条边(有效指针域),浪费了nk - n + 1 = n(k - 1) + 1
  =》二叉树浪费n(2 - 1) + 1 => n + 1个指针域