数据结构-二叉树

1. 二叉树的第i层上节点数最多 2n-1。
2. 高度为k的二叉树中，最多有 2k-1 个节点。
3. 在任意一棵二叉树中，如果终端节点的度为 n，度为2的节点数为 m，则 n=m+1。
4. 二叉树的子树有左右之分，顺序不能颠倒。
5. 若采用连续储存的方式存放二叉树，则节点下标之间的关系：
   • 若某个节点的下标为 i ，则这个节点的父节点的下标为 i / 2。
   • 若某个节点下标为 i ，且节点的度为2，则这个节点的左子节点的下标为 2 * i + 1 ，右子节点的下标为 2 * i + 2 。

树最后一层没有任何子节点，其余每一层的所有节点都有2个子节点。

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

如果二叉树的深度为k，则除第k层外其余所有层节点的度都为2，且叶子节点从左到右依次存在。也即是，将满二叉树的最后一层从左到右依次删除若干节点就得到完全二叉树。满二叉树是一棵特殊的完全二叉树，但完全二叉树不一定是满二叉树。

1. 满二叉树是一棵特殊的完全二叉树，但完全二叉树不一定是满二叉树。
2. 在满二叉树中最下一层，连续删除若干个节点得到完全二叉树。
3. 在完全二叉树中，若某个节点没有左子树，则一定没有有子树。
4. 若采用连续储存的方式存放二叉树，则节点下标之间的关系（根节点下标为0）：
   • 若某个节点的下标为 i ，则这个节点的父节点的下标为 i / 2。
   • 若某个节点下标为 i ，且节点的度为2，则这个节点的左子节点的下标为 2 * i + 1 ，右子节点的下标为 2 * i + 2 。
   • 除了根节点外，左子树的下标为基数，右子树的下标为偶数。

1. 左子树上所有节点的值均小于它的根节点的值；
2. 右子树上所有节点的值均大于它的根节点的值；
3. 以此类推：左、右子树也分别为二叉查找树。
4. 没有键值相等的节点（no duplicate nodes）。
5. 二叉搜索树的中序遍历是升序的。

1. 平衡二叉树
2. 每个节点的左右子树的高度最多相差 1