Listening to the Words

计算机基础(8)之二叉树

二叉树(Binary Tree)

二叉树是对现实世界中树的抽象,由于树有清晰的组织结构方便管理和操作,因此它在计算机领域有十分广泛的应用

完全二叉树

完全二叉树使用比喻解释:爷爷最多有两个孩子,而且左边的孩子没有达到两个孩子时,右边的孩子不能有孩子

更通俗的说是大伯父家没有两个孩子,二叔是不能有孩子的

《计算机基础(8)之二叉树》

这样的好处呢?

当然有的:
《计算机基础(8)之二叉树》

完全二叉树的结构可以使用数组实现好处显而易见:连续内存,访问高效

大顶堆(max heap)和小顶堆(min heap)

大顶堆和小顶堆是必然会存在的两种排序方式,它们的使用场景也很多,比如: 优先级的队列(Priority Queue),它本身是堆结构,在入队和出队时可以根据顺序调整顺序

  • 权重高的任务先执行

二叉树遍历

二叉树作为一种简单的树结构,它的遍历按照顺序可以划分为三种:

  • 前序遍历:对于每一棵子树,依次访问其根节点→左子节点→右子节点
  • 中序遍历:对于每一棵子树,依次访问其左子节点→根节点→右子节点
  • 后序遍历:对于每一棵子树,依次访问其左子节点→右子节点→根节点

《计算机基础(8)之二叉树》

区别在于根节点出现的时机,前->爸爸在前,中->爸爸在中 后->爸爸在后

点赞