# 介绍 ## 特点 二叉树： `最多只有两个` 子节点的树。度为2的数。  ## 分类 二叉树分为： - 满二叉树 - 完全二叉树 - 平衡二叉树 - 二叉搜索树 ### 满二叉树 除了最后一层叶子结构之外，其他节点都有两个子节点的树。  ### 完全二叉树 除了最后缺的几个节点不考虑之外，剩下的节点和一个满二叉结构节点数完全相同。  ### 平衡二叉树 任一节点左右子节点的 `高度差` 小于等于 |1|。 节点高度：从这个节点到叶子节点最多的边数。  ### 二叉搜索树（BST-Binary Search Tree） 规则： 1. 任意一个节点的左子节点都小于这个节点 2. 任意一个节点的右子节点都大于这个节点  ## 存储方式 二叉树的存储方式： - 顺序存储（用数组） - 链式存储（用链表） ### 链式存储 每个节点都有 左、右 两个指针，指向左右两个子节点。  节点类： ~~~ class Node { construct(data) { this.data = data // 数据 this.left = null // 左子节点 this.right = null // 右子节点 } } ~~~ ### 顺序存储 使用数组存储二叉树。 存储完之后必须要满公式： 情况一、（如果根节点保存在 0 这个下标时的公式） 第i个节点的左子节点下标：2i+1 第i个节点的右子节点下标：2i+2 第i个节点的父节点下标；Math.floor((i-1)/2) 情况二、根节点保存在1这个位置时：  顺序存储比较适合 `完全二叉树`，否则会比较浪费空间（有很多空位）：