二叉树

二叉树

满足以下条件就是二叉树：

  1. 本身是有序树，分别称为左子树和右子树组成
  2. 树中包含的各个节点的度不能超过 2，即只能是 0、1 或者 2

有三个结点的二叉树总共有五种结构

数与二叉树的区别

  1. 二叉树中最大的结点为2，二数中不限制结点的数
  2. 二叉树是有有序数，及时只有一个几点也要指出是左子树还是右子树。数是可以有序树也可以是无序树

二叉树的性质

  1. 二叉树第i层（i>=1）上至多有2^n-1^个结点
  2. 深度为k（k>=1）的二叉树至多有2^k-1^个结点
  3. 对任何一颗二叉树，若其叶子结点数位n0，度为2的结点数位n2，则n0=n2+1
  4. 对任何一颗二叉树，若其总结点数为n，度为2的结点数位n2，则度为1的结点n1=n-2*n2-1

满二叉树的性质

  1. 满足普通二叉树的性质
  2. 满二叉树中第 i 层的节点数为 2^i-1^ 个。
  3. 深度为 k 的满二叉树必有 2^k^-1 个节点 ，叶子数为 2^k-1^。
  4. 满二叉树中不存在度为 1 的节点，每一个分支点中都两棵深度相同的子树，且叶子节点都在最底层。
  5. 具有 n 个节点的满二叉树的深度为 log2(n+1)

完全二叉树的性质

  1. 满足普通二叉树的性质
  2. 当 i>1 时，父亲结点为结点 [ i / 2 ]，左孩子结点为2 * i，右孩子结点为2 * i + 1。（i=1 时，表示的是根结点，无父亲结点）
  3. 如果 2 * i>n（总结点的个数），则结点 i 肯定没有左孩子（为叶子结点）；否则其左孩子是结点 2 * i
  4. 如果 2 * i + 1 > n ，则结点 i 肯定没有右孩子；否则右孩子是结点 2 * i + 1
  5. 具有n个结点的完全二叉树的高度为[log2n]+1

二叉树的存储

​ 顺序存储结构：将普通二叉树转为完全二叉树进行存储
​ 链式存储结构：结点包含数据域，左指针域(指向左孩子结点)，右指针域(指向右孩子结点)

二叉树的遍历

前序遍历：根、左、右

中序遍历：左、根、右

后序遍历：左、右、根

二叉树的度

树中所有结点的度数的最大值。二叉树的度小于等于2，因为二叉树的定义要求二叉树中任意结点的度数（结点的分支数）小于等于2

求二叉树的结点

n0=n2+1
n=n0+n1+n2

树的路径

结点的路径长度：树根到此结点之间的路径
数的路径长度：从树根到每一个叶子之间的路径长度之和
结点的带权路径长度：从该结点到树根之间的路径长度与该结点权值的乘积
数的带权路径长度：该树的每个结点的带权路径长度之和

哈夫曼树（最优二叉树）

构造哈夫曼树：找出两个最小的权值，把他们作为叶子结点构造成一棵树