二叉树

介绍二叉树之前先说下树状结构，不同于线性结构只有前后两个方向，树状结构可以有多个方向。

tree.png

树的基本概念

• 节点、根节点、父节点、子节点、兄弟节点
  如上图中的每个元素都一个节点，节点A是根节点，A是B和C的父节点，B和C是A的子节点，B和C互相是兄弟节点；

• 一棵树可以没有任何节点，称为空树

• 一棵树可以只有一个节点，即只有根节点

• 子树、左子树、右字树
  如上图中，子树B是A的左子树，子树C是A的右子树

• 节点的度
  子树的个数，等于节点的子节点数

• 树的度
  所有节点度中的最大值

• 叶子节点
  度为0的节点

• 非叶子节点
  度不为0的节点

• 层数
  根节点在第一层，根节点的子节点在第二次，依次往下类推

• 节点的深度
  从根节点到当前节点唯一路径上的节点总数

• 节点的高度
  从当前节点到最远叶子节点的路径上的节点总数

• 树的深度
  所有节点深度中的最大值

• 树的高度
  所有节点高度中的最大值

• 树的深度等于树的高度

• 有序树
  树中任意节点的子节点之间有顺序关系

• 无序树
  树中任意节点之间没有顺序关系，也称“自由树”

• 森林
  有n(n ≥0)课互不相交的树组成的集合

二叉树(BinaryTree)

每个节点的度最大为2，左子树和右子树是有序的，即使只有一颗子树也要区分左右的树是二叉树；

BinaryTree.png

二叉树的性质

• 非空二叉树的第i层，最多有个节点（i>=1）
• 高度为h的二叉树上最多有个节点（h>=1）
• 对于任意一课非空二叉树，如果叶子节点个数为n0，度为2的节点数为n2
• 若度为1的节点数为n1，二叉树的总结点数n = n0 + n1 + n2
• 二叉树的总边数T = n1 + 2*n2 = n - 1 = n0 + n1 + n2 -1，因此 n0 = n2 + 1

真二叉树

所有节点的度要么为0，要么为2的二叉树称为真二叉树；

满二叉树

最后一层节点的度为0，其他节点的度都为2的二叉树称为满二叉树；

满二叉树.png

完全二叉树

对一棵具有n个结点的二叉树按层编号，如果编号为i(1<=i<=n)的结点与同样深度的满二叉树中编号为i的结点在二叉树中位置完全相同，则这棵二叉树称为完全二叉树

完全二叉树.png

• 叶子节点只会出现最后两层，最后一层的叶子节点都靠左对齐的二叉树

• 从根节点至倒数第二层是一棵满二叉树

• 满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树

• 度为1的节点只有左子树

• 度为1的节点要么是1个，要么是0个

• 同样节点数量的二叉树，完全二叉树的高度最小

• 假设完全二叉树的高度为h(h≥1)，那么
  至少有 个节点(++···+ + 1)
  最多有- 1个节点( ++···+) ，满二叉树)

• 若总结点数为n
  ≤ n ＜ => h -1≤ < h => h = floor() + 1

• 一棵有n个节点的完全二叉树(n>0)，从上到下、从左到右对节点从1开始进行编号，对任意第i个节点

排序完全二叉树.png

若i=1，它是根节点
若i>1,它的父节点编号是floor(i/2)
若2i≤n，它的左子节点编号为2i
若 2i＞n，它无左子节点
若2i+1 ≤n，它的右子节点编号为2i+1
若2i+1 ＞n，它无右子节点

从图中可以看到，对于节点i，它的左子节点等于2i，右子节点等于2i+1；