12.JavaScript 数据结构与算法（十二）二叉树

[webVueBlog]

二叉树

二叉树的概念

如果树中的每一个节点最多只能由两个子节点，这样的树就称为二叉树；

二叉树的组成

• 二叉树可以为空，也就是没有节点；
• 若二叉树不为空，则它由根节点和称为其左子树 TL 和右子树 TR 的两个不相交的二叉树组成；

二叉树的五种形态

空的二叉树、只有一个节点的二叉树、只有左子树 TL 的二叉树、只有右子树 TR 的二叉树和有左右两个子树的二叉树。

二叉树的特性

• 一个二叉树的第 i 层的最大节点树为：2^(i-1)^，i >= 1；
• 深度为 k 的二叉树的最大节点总数为：2^k^ - 1 ，k >= 1；
• 对任何非空二叉树，若 n0 表示叶子节点的个数，n2表示度为 2 的非叶子节点个数，那么两者满足关系：n0 = n2 + 1；如下图所示：H，E，I，J，G 为叶子节点，总数为 5；A，B，C，F 为度为 2 的非叶子节点，总数为 4；满足 n0 = n2 + 1 的规律。

特殊的二叉树

完美二叉树

完美二叉树（Perfect Binary Tree）也成为满二叉树（Full Binary Tree），在二叉树中，除了最下一层的叶子节点外，每层节点都有 2 个子节点，这就构成了完美二叉树。

完全二叉树

完全二叉树（Complete Binary Tree）:

• 除了二叉树最后一层外，其他各层的节点数都达到了最大值；
• 并且，最后一层的叶子节点从左向右是连续存在，只缺失右侧若干叶子节点；
• 完美二叉树是特殊的完全二叉树；