二叉树（binary tree）实现详解二叉树|数据结构

本文概述

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

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

节点的根
左子树, 它也是二叉树。
右二叉树

下图显示了一个二叉树。

文章图片
二叉树的类型 1.严格的二叉树
在严格二叉树中, 每个非叶节点都包含非空的左和右子树。换句话说, 每个非叶节点的度数始终为2。具有n个叶的严格二叉树将具有（2n-1）个节点。
下图显示了严格的二叉树。

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

文章图片
二叉树遍历

序号	遍历	描述
1	Pre-order Traversal	首先遍历根, 然后分别遍历到左子树和右子树。此过程将递归应用于树的每个子树。
2	有序遍历	首先遍历左子树, 然后分别遍历根和右子树。此过程将递归应用于树的每个子树。
3	Post-order Traversal	遍历左侧子树, 然后分别遍历右侧子树和根。此过程将递归应用于树的每个子树。

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

文章图片
在上图中, 树被视为节点的集合, 其中每个节点包含三个部分：左指针, 数据元素和右指针。左指针存储左孩子的地址, 而右指针存储右孩子的地址。叶子节点的左指针和右指针包含null。
下图显示了如何使用链接表示为二叉树分配内存。内存中维护着一个特殊的指针, 该指针指向树的根节点。树中的每个节点都包含其左子节点和右子节点的地址。叶节点的左指针和右指针中包含null。

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

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