Skip to main content

二叉树理论基础篇

题目分类大纲如下：

二叉树大纲

二叉树的种类​

在我们解题过程中二叉树有两种主要的形式：满二叉树和完全二叉树。

满二叉树​

满二叉树：如果一棵二叉树只有度为 0 的结点和度为 2 的结点，并且度为 0 的结点在同一层上，则这棵二叉树为满二叉树。

如图所示：

img

这棵二叉树为满二叉树，也可以说深度为 k，有 2^k-1 个节点的二叉树。

完全二叉树​

什么是完全二叉树？

完全二叉树的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2^(h-1) 个节点。

典型的例子如题：

img

优先级队列其实是一个堆，堆就是一棵完全二叉树，同时保证父子节点的顺序关系。

二叉搜索树​

二叉搜索树是有数值的了，二叉搜索树是一个有序树。

  • 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
  • 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
  • 它的左、右子树也分别为二叉排序树

下面这两棵树都是搜索树 img

平衡二叉搜索树​

平衡二叉搜索树：又被称为 AVL（Adelson-Velsky and Landis）树，且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过 1，并且左右两个子树都是一棵平衡二叉树。

如图：

img

最后一棵 不是平衡二叉树，因为它的左右两个子树的高度差的绝对值超过了 1。

二叉树的存储方式​

二叉树可以链式存储，也可以顺序存储。

那么链式存储方式就用指针， 顺序存储的方式就是用数组。

顾名思义就是顺序存储的元素在内存是连续分布的，而链式存储则是通过指针把分布在各个地址的节点串联一起。

链式存储如图：

img

顺序存储呢

其实就是用数组来存储二叉树，顺序存储的方式如图：

img

用数组来存储二叉树如何遍历的呢？

如果父节点的数组下标是 i，那么它的左孩子就是 i * 2 + 1，右孩子就是 i * 2 + 2。

但是用链式表示的二叉树，更有利于我们理解，所以一般我们都是用链式存储二叉树。

但是用数组依然可以表示二叉树。

二叉树的遍历方式​

  • 深度优先遍历

    • 前序遍历（递归法，迭代法）

    • 中序遍历（递归法，迭代法）

    • 后序遍历（递归法，迭代法）

  • 广度优先遍历

    • 层次遍历（迭代法）

这里前中后，其实指的就是中间节点的遍历顺序，

  • 前序遍历：中左右
  • 中序遍历：左中右
  • 后序遍历：左右中

大家可以对着如下图，看看自己理解的前后中序有没有问题。

img

二叉树的定义​

function TreeNode(val, left, right) {
  this.val = val === undefined ? 0 : val
  this.left = left === undefined ? null : left
  this.right = right === undefined ? null : right
}

本文转载于：代码随想录