树 #

对比数组和链表 #

• 数组
  • 优点
    • 访问元素速度快，对于有序数组，可以使用二分查找提交检索效率
  • 缺点
    • 如果需要检索具体某个值或者插入值，需要整体移动，效率低
  • ArrayList实际是维护了一个Object[]数组
  • 添加元素时，先判断是否需要扩容，如果需要，调用grow方法
  • 扩容原理：每次在底层都需要创建新的数组，将原来数组的数据拷贝到数组，并插入新的数据
• 链表
  • 优点
    • 一定程度上对数组存储方式有优化
    • 效率仍然较低，（检索某个值需要从头遍历）
• 树
  • 能提高数据存储和读取的效率，比如二叉排序树

二叉树 #

相关术语 #

• 节点
• 根节点
• 父结点
• 子节点
• 叶子结点：没有子节点的节点
• 节点的权（节点值）
• 路径（从根节点找到该节点的路线）
• 层
• 子树
• 树的高度（最大层数）
• 森林：多棵子树构成森林

二叉树的概念 #

• 每个节点最多只能有链两个节点
• 子节点分为左节点和右节点
• 如果二叉树的所有叶子结点都在最后一层，并且结点总数 = 2^n^ - 1，n为层数，则称为满二叉树
• 如果该二叉树的所有叶子节点都在最后一层或者倒数第二层，而且最后一层的叶子节点在左边连续，倒数第二层的叶子节点在右边连续，我们称为完全二叉树。

遍历 #

• 前序遍历
• 中序遍历
• 后序遍历