【算法】二叉树学习笔记

树由边和节点组成

概念和用途

  • 树是一种非线性的数据结构, 分层存储。
  • 树被用来存储具有层级关系的数据, 还被用来存储有序列表。
  • 二叉树进行查找特别快, 为二叉树添加或删除元素也也别快
  • 集合中不允许相同成员存在。

关键概念定义

  1. 树由一组以边连接的节点组成
  2. 一棵树最上面的节点称为根节点, 如果一个节点下面连接多个节点, 那么该节点称为父节点, 它下面的节点被称为子节点。 一个节点可以有0个、 1个或多个子节点。 没有任何子节点的节点称为叶子节点。
  3. 二叉树是一种特殊的树, 子节点个属不超过两个。
  4. 从一个节点走到另一个节点的这一组称为路径
  5. 以某种特定顺序访问树中的所有节点称为树的遍历
  6. 树分为几个层次, 根节点是第0层, 它的子节点是第一层, 一次类推。 我们定义的层数就是树的深度
  7. 每个节点都有一个与之相关的值, 该值有时被称为键。
  8. 一个父节点的两个子节点分别称为左节点和右节点。 二叉查找树是一种特殊的二叉树, 相对较小的值保存在左节点, 较大的值保存在右节点, 这一特性使得查找效率很高。
你的支持将鼓励我继续创作