二叉树基本概念

树

1. 结点的度：节点拥有的子树数；
2. 树的度：树内各结点度的最大值；
3. 结点的层次从根开始定义，根为第一层；
4. 树的深度或高度：树中结点的最大层次；
5. 路径长度：路径上的分支数目；
6. 树的路径长度是从树根到每一结点的路径长度之和，完全二叉树路径长度最短；

• 二叉树节点的深度：指从根节点到该节点的最长简单路径边的条数。

• 二叉树节点的高度：指从该节点到叶子节点的最长简单路径边的条数。

二叉树

1. 二叉树每个结点至多有两个子树；
2. 在二叉树的第i层至多有2i-1个结点；
3. 深度为k的二叉树至多有2k-1 个结点；
4. 对任何一棵二叉树，如果其终端结点数为n0 ，度为2的结点数为n2 ，则n0 = n2 + 1；
5. 满二叉树：一棵深度为k的有2k - 1 个结点的二叉树；
6. 赫夫曼树，又称最优二叉树，是一类带权路径长度最短的树；

完全二叉树

• 定义：自上而下，自左而右，每一结点编号对应于满二叉树。

• 特点：对完全二叉树的任一结点 i``(1<=i<=n)有：

• • 若i>1，则其双亲结点为结点i/2；
  • 若2i>n，则结点i无左孩子，否则其左孩子为结点2i；
  • 若2i+1>n，则结点i无右孩子，否则其右孩子为结点2i+1；

遍历

• 深度优先遍历（栈）

• • 前序遍历（递归法，迭代法）
  • 中序遍历（递归法，迭代法）
  • 后序遍历（递归法，迭代法）

• 广度优先遍历（队列）

• • 层次遍历（迭代法）

二叉搜索树

也称二叉排序树，定义如下：

• 或者是一棵空树，或者满足以下条件；

• 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；

• 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；

• 它的左、右子树也分别为二叉排序树。

平衡二叉树

也称AVL树，定义如下：

• 它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

C++中map、set、multimap，multiset的底层实现都是平衡二叉搜索树（红黑树），所以map、set的增删操作时间时间复杂度是logn；

unordered_map、unordered_set，unordered_map、unordered_map底层实现是哈希表。