二叉树
读书笔记:
- 相同高度的情况下,满二叉树的结点比完全二叉树的结点多。
- 二叉树的数组表示法。不适合对稀疏二叉树进行存储。根节点对应数组下标为0
2.1. 左孩子结点left = 2 * parent + 1
2.2. 右孩子结点right = 2 * parent +2
2.3. 父节点下标 parent = (left - 1) / 2 - 二叉排序树的自平衡方式有AVL树,红黑树,树堆等,二叉堆也维相对顺序,只要求父节点大于左右孩子结点。
- 遍历方式之广度优先,深度优先。这两种遍历方式并不局限于二叉树,在访问树,图以及其他更为复杂的数据结构时,这两概念经常被用到。是一种抽象的算法思想。