2025年数据结构和算法之七：二叉树

大家好，我是讯享网，很高兴认识大家。

数据结构树论之二叉树

本篇文章，详细学习一下二叉树相关知识。

首先，简单的理解一下树的一下基本概念：

结点：树里面的元素。

父子关系：结点之间相连的边

子树：当结点大于1时，其余的结点分为的互不相交的集合称为子树

度：一个结点拥有的子树数量称为结点的度

叶子：度为0的结点

孩子：结点的子树的根称为孩子结点

双亲：和孩子结点对应

兄弟：同一个双亲结点

森林：由N个互不相交的树构成深林

画个图示意一下：

在这里插入图片描述
讯享网

除了最后一个不是树（是图），其他的都是树，可以看到，树其实是包含链表结构的。

另外在树结构里面，还有几个重要的术语

在树形结构里面有几个重要的术语：

结点的高度：结点到叶子结点的最长路径

结点的深度：根结点到该结点的边个数

结点的层数：结点的深度加1

树的高度：根结点的高度

如下图所示

在这里插入图片描述

在了解了树的一些基本概念之后，我们来先来关注最基本的树-二叉树，很多经典的算法与数据结构其实都是通过二叉树发展而来。

二叉树

如果二叉树的除了叶子节点那一层（最后一层），每一层都长满了，也就是每一层的的节点数为最大的2^(N-1)，那么这就是一个满二叉树。如果除最后一层外，其他的结点个数必须达到最大，并且最后一层结点都连续靠左排列，这就是一个完全二叉树。

在这里插入图片描述

二叉树如何存储起来呢？（说到底层存储，要么是数组，要么是链表）

显然，可以用链表来做存储。在基础的部分，我们也说过，因为数组的性能更高，因此能用数组的话就尽可能用数组来存储，那么二叉树可以使用数组来存储吗？

在在一颗满二叉树中，根据满二叉树满足的条件，可以推算出数组下标与树节点之间的关系。如果根节点从1开始，那么左孩子节点的数组下标为父节点下标的2倍，右孩子节点为父节点下标的2倍+1.

在这里插入图片描述

通过这种映射关系，我们很容易对一个满二叉树存储到数组中。同理，完全二叉树存储到数组中也是一样的道理。

那么对于普通的二叉树，能不能用数组存呢？

答案当然是可以啦，不存在的节点对应数组中的元素用特定的值来标记一下就可以了。不过这种方式会带来空间的大量浪费，你可以画图理解一下。

学习二叉树，那么最基本算法就是先学会如何遍历二叉树。

四种遍历方式（重要口诀：根节点输出！）：

前序：根左右

中序：左根右

后序：左右根

层次遍历。

如果二叉树为：
在这里插入图片描述

4种遍历分别用代码实现一下：

/ * 二叉树 * 子节点最多只有两个的树。 * * 满二叉树：除了叶子节点，所有的节点都有2个子节点 * 完全二叉树：除最后一层，其他节点是满二叉树，最后一层节点从左到右依次排列，不能有间隔，右边允许空。 * * 二叉树的4种遍历方式 * 口诀：根节点输出 * 1. 前序 根 左 右 * 2. 中序 左 根 右 * 3. 后序 左 右 根 * 4. 层遍历 * */ public class BinaryTree { 
    / * 前序遍历 根->左->右 * 从根开始，先看左边 递归左边，再根，在递归右边。 * 遍历流程，画图理解。 * @param root */ public static void pre(TreeNode root){ 
    print(root); if(root.left != null){ 
    pre(root.left); } if(root.right != null){ 
    pre(root.right); } } / * 中序遍历 左->根->右 * 遍历流程，画图理解。 * @param root */ public static void in(TreeNode root){ 
    if(root.left != null){ 
    in(root.left); } print(root); if(root.right != null){ 
    in(root.right); } } / * 前序遍历 左->右->根 * 遍历流程，画图理解。 * @param root */ public static void post(TreeNode root){ 
    if(root.left != null){ 
    post(root.left); } if(root.right != null){ 
    post(root.right); } print(root); } / * 按层次遍历 * 思路 * 将二叉树按照层级，一层一层映射到数组上，首先将二叉树用空节点补充为满二叉树， * 如果将满二叉树一层一层的放到数组上，会发现这样一个规律（画图理解） * 如果根节点的索引为i，那么其左孩子节点的索引为2i，右孩子节点的索引为2i+1. * * 遍历树时，使用前序（根-左-右） */ public static void tier(char[] data, TreeNode root, int index){ 
    data[index] = root.data; //当前根装到数组里面 if(root.left != null){ 
    tier(data, root.left, index*2);//左孩子的索引为父亲的2倍 } if(root.right != null){ 
    tier(data, root.right, index*2+1);//右孩子的索引为父亲的2倍+1 } } / * 层次遍历，利用队列的FIFO特性实现。 */ public static void tierByQueue( TreeNode root){ 
    Queue<TreeNode> queue = new ArrayBlockingQueue<>(2<<3); queue.add(root); while(!queue.isEmpty()){ 
    TreeNode curNode = queue.poll(<

讯享网

2025年数据结构和算法之七：二叉树

数据结构树论之二叉树

二叉树

相关推荐