二叉树
概念
- 树的最大度为2
- 孩子分为左右
- 每层的节点数量：2^层号
- 所欲的节点数量：2层数－1，不是2(层数－1)
- 斜树请直接使用线性表
- 一般二叉树是没有规律的，所以无法使用
- 满二叉树也是一种特殊的完全二叉树
https://raw.githubusercontent.com/arkulo56/thought/master/images/datastruct/binary_tree.png
满二叉树
- 所有叶子节点都在一层
- 所有分支节点密度为2
- 满二叉树层数：2^3-1=7 => log2(7+1) => log2(n+1)
完全二叉树
- 第i个元素的位置与满二叉树位置相同
- 节点顺序为先左后右
- 所有叶子节点都分布在倒数后2层
- log2(n)<完全二叉树层数<log2(n)+1
二叉树遍历
这里有两个关键词：访问＋次序
访问：对每个数据节点需要做的处理，例如：打印、加法运算
次序：不同的应用场景该有不同的访问顺序。例如：给公司所有人员发年终奖，按照岗位重要性逐个发放
总结
所有的数据都是存在磁盘上的，然后通过程序将其加载进内存，然后在内存中形成一棵树。好的，开始读写吧～
网友评论