23 | 二叉树基础（上）：什么样的二叉树适合用数组来存储

作者：鲁米

2023-12-09
北京
本文字数：1526 字
阅读完需：约 5 分钟

给定一组数据，比如 1，3，5，6，9，10。你来算算，可以构建出多少种不同的二叉树？

构建二叉树的种类数量与卡特兰数（Catalan number）有关。对于给定的 n 个节点，可以构建的不同二叉树的数量是第 n+1 个卡特兰数。

对于给定的节点序列 1，3，5，6，9，10，节点数量 n = 6。因此，可以构建的不同二叉树的数量是第 7 个卡特兰数。

卡特兰数的计算公式为：

C n = \frac{( 2 n ) !}{( n + 1 ) ! \cdot n !}

其中，Cn 表示第 n 个卡特兰数，! 表示阶乘。

对于 n = 6，计算得到：

C_{6} = \frac{( 2 \cdot 6 ) !}{( 6 + 1 ) ! \cdot 6 !} = \frac{1 2 !}{7 ! \cdot 6 !} = \frac{4 7 9 0 0 1 6 0 0}{5 0 4 0 \cdot 7 2 0} = 132

因此，给定节点序列 1，3，5，6，9，10，可以构建 132 种不同的二叉树。

卡特兰数

卡特兰数是一类在组合数学中常见的数列，通常用来描述在许多抽象情境中，不同元素的组合方式的数量。这个数列以法国数学家欧仁·查理·卡特兰（Eugène Charles Catalan）的名字命名。

在二叉树的上下文中，卡特兰数表示的是具有 n 个节点的不同二叉树的数量。对于给定的 n，卡特兰数 CnC**n 表示构建的不同二叉树的数量。

卡特兰数的递推关系为：

C_{0} = 1, C_{n + 1} = \frac{2 ( 2 n + 1 )}{n + 2} \cdot C_{n}

卡特兰数的计算公式为：

C_{n} = \frac{( 2 n ) !}{( n + 1 ) ! \cdot n !}

卡特兰数的应用不仅局限于二叉树，还涉及许多其他组合问题，例如括号匹配、山脉问题、合法的出栈序列等。它在计数和组合问题中的广泛应用使得理解和计算卡特兰数成为组合数学中的重要概念。

阶乘

阶乘是一个正整数 n 的阶乘，记作 n!，表示从 1 到 n 的所有正整数相乘的结果。阶乘的计算公式为：

n! = n \cdot (n - 1) \cdot (n - 2) \cdot \dots \cdot 3 \cdot 2 \cdot 1

其中，0 的阶乘定义为 1。阶乘是一个常见的数学运算，经常用于组合数学、排列组合、概率统计等领域。

例如：

5! = 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 120

0! = 1

阶乘的计算在编程和数学问题中经常会遇到，尤其在组合数学、排列组合、递归等算法中。

我们讲了三种二叉树的遍历方式，前、中、后序。实际上，还有另外一种遍历方式，也就是按层遍历，你知道如何实现吗？

按层遍历二叉树也称为广度优先搜索（Breadth-First Search，简称 BFS）。BFS 通常使用队列来实现。按层遍历的过程是从树的根节点开始，逐层访问节点，先访问当前层的所有节点，然后再逐层访问下一层的节点。

以下是按层遍历二叉树的基本步骤：

将根节点入队。
循环执行以下步骤，直到队列为空：
出队一个节点，访问该节点。
如果该节点有左子节点，将左子节点入队。
如果该节点有右子节点，将右子节点入队。

class TreeNode2 {    int val;    TreeNode2 left;    TreeNode2 right;
    public TreeNode2(int val) {        this.val = val;    }}
public class LevelOrderTraversal {
    public static void levelOrderTraversal(TreeNode2 root) {        if (root == null) {            return;        }        Queue<TreeNode2> queue = new LinkedList<>();        queue.offer(root);        while (!queue.isEmpty()) {            TreeNode2 current = queue.poll();            System.out.print(current.val + " ");            if (current.left != null) {                queue.offer(current.left);            }            if (current.right != null) {                queue.offer(current.right);            }        }    }
    public static void main(String[] args) {        // 示例二叉树        TreeNode2 root = new TreeNode2(1);        root.left = new TreeNode2(2);        root.right = new TreeNode2(3);        root.left.left = new TreeNode2(4);        root.left.right = new TreeNode2(5);        System.out.println("按层遍历结果：");        levelOrderTraversal(root);    }}

复制代码

发布于: 刚刚阅读数: 4

鲁米

关注

生活黑客35 2019-06-11 加入

起点不重要，迭代很重要，就需要保持充分的开放和积累；而信息越充分，结果越可靠，又要求随时调整、不断逼近真相。

发布

暂无评论

创作场景

23 | 二叉树基础（上）：什么样的二叉树适合用数组来存储

卡特兰数

阶乘

鲁米

评论