二叉树（binary tree）实现详解

本文概述

• 二叉树的类型
• 二叉树遍历
• 二叉树表示

二进制树是一种特殊类型的通用树, 其中每个节点最多可以有两个孩子。二叉树通常分为三个不相交的子集。

1. 节点的根
2. 左子树, 它也是二叉树。
3. 右二叉树

下图显示了一个二叉树。

二叉树的类型

1.严格的二叉树

在严格二叉树中, 每个非叶节点都包含非空的左和右子树。换句话说, 每个非叶节点的度数始终为2。具有n个叶的严格二叉树将具有（2n-1）个节点。

下图显示了严格的二叉树。

2.完整的二叉树

如果所有叶子都位于同一级别d, 则将二叉树称为完整的二叉树。一个完整的二叉树是一个二叉树, 在级别0和d之间的每个级别上正好包含2个l个节点。深度为d的完整二叉树中的节点总数为2d + 1-1, 其中叶节点为2d, 非叶节点为2d-1。

二叉树遍历

二叉树表示

二叉树的表示形式有两种：

1.链接表示

在这种表示形式中, 二叉树以链接列表的形式存储在内存中, 其中节点数存储在非连续的内存位置, 并通过继承父子关系（如树）链接在一起。每个节点包含三部分：指向左侧节点的指针, 数据元素和指向右侧节点的指针。每个二叉树都有一个指向二叉树根节点的根指针。在空的二叉树中, 根指针将指向null。

考虑下图中给出的二叉树。

在上图中, 树被视为节点的集合, 其中每个节点包含三个部分：左指针, 数据元素和右指针。左指针存储左孩子的地址, 而右指针存储右孩子的地址。叶子节点的左指针和右指针包含null。

下图显示了如何使用链接表示为二叉树分配内存。内存中维护着一个特殊的指针, 该指针指向树的根节点。树中的每个节点都包含其左子节点和右子节点的地址。叶节点的左指针和右指针中包含null。

2.顺序表示

这是存储树元素的最简单的内存分配技术, 但由于需要大量空间来存储树元素, 因此它是一种低效的技术。下图显示了一个二叉树及其内存分配。

在此表示形式中, 数组用于存储树元素。数组的大小将等于树中存在的节点数。树的根节点将出现在数组的第一个索引处。如果将节点存储在第ith个索引处, 则其左右子节点将存储在2i和2i + 1位置。如果数组的第一个索引（即tree [1]）为0, 则表示树为空。