二叉树

title: 二叉树 id: 3c554a35588e0b381d124fff75438783 tags: [] date: 2000/01/01 00:00:00 updated: 2021/03/01 17:32:18 isPublic: true --#|[分隔]|#--

二叉树

定义

• 二叉树(Binary tree)

  • 完全二叉树(Complete Binary Tree)：子节点从上往下、从左往右依次排列，中间没有跳过的项

  • 满二叉树(Full Binary tree)：除最后一层无任何子节点外，每一层上的所有结点都有两个子结点的二叉树

  满二叉树肯定是完全二叉树，满二叉树是完全二叉树的一个特例

• 二叉搜索树/二叉查找树/二叉排序树(Binary Search Tree)(BST)：每一个节点，它如果有子节点，那么它左侧的所有子节点的值都比他小，右侧的所有子节点的值都比它大。

• 平衡树(Balance Tree)(BT)：根节点左侧的层数F_L和右侧的层数F_R，(F_L - F_R)的绝对值小于等于1，也就是左侧和右侧的层级相差最多差一层。

  • 不平衡的二叉树想平衡，需要调整结构，整体的结构变化，需要控制数左旋或右旋，左边层数少就往左旋，右边层数少就往右旋，旋的层级就看两边相差几层。

  • 有时遇到复杂一些的不平衡树，需要旋转多次。

• 二叉堆：是一种特殊的堆，结构是完全二元树，有且仅有下面两种结构

  • 最大堆/大堆顶：父节点的值，大于等于它的子节点，导致堆顶(根节点)最大

  • 最小堆/小堆顶：父节点的值，小于等于它的子节点，导致堆顶(根节点)最小

应用

二叉树使用一维数组表示，比如二叉树中的某个节点的数据，存放在数组中的索引值为n，那么：

• 当前节点索引值: 「n」

• 父节点索引值：「Math.floor((n - 1) / 2)」

• 左子节点的索引值：「2n + 1」

• 右子节点的索引值：「2n + 2」