当前位置：首页 > news >正文

数据结构--树和二叉树

news 来源：原创 2025/6/28 19:26:54

树和二叉树的定义

树的定义

树是一种非线性的数据结构，它模拟了具有层次关系的数据的集合。在树结构中，存在以下基本概念：

节点（Node）：树的每个元素被称为节点。
根节点（Root Node）：树的最顶层的节点，它是树的起点。
子节点（Child Node）：一个节点之下的节点被称为其子节点。
父节点（Parent Node）：若一个节点有子节点，则它被称为其子节点的父节点。
兄弟节点（Sibling Nodes）：具有相同父节点的节点互为兄弟节点。
叶子节点（Leaf Node）：没有子节点的节点被称为叶子节点。
度（Degree）：一个节点的子节点数量称为该节点的度。（树的度和节点的度）
树的度：树中节点的最大度称为树的度。
层次（Level）：从根节点开始，根节点为第一层，其子节点为第二层，以此类推。
树的高度（或深度）：树中节点的最大层次数。
有序树：树中节点的子节点从左到右是有次序的，不能互换。
无序树：树中节点的子节点没有固定的次序。
森林：零个或多个不相交的树组成的集合。

树的特点

它包含一个或多个结点。
每个结点可以有0个或多个子结点。
每个子结点只有一个父结点。
存在一个唯一的根结点，它没有前驱结点。
除了根结点外，每个子结点都可以看作是一个新的树的根，这个新的树（子树）与树的其他部分是不相关的。
路径唯一性：在树中，从根节点到任何节点的路径都是唯一的。这一特性确保了数据在树结构中的唯一性和确定性。
子树独立性：除了根节点外，每个节点都可以看作是一个新的树的根，即子树。这些子树与树的其他部分是不相关的，即它们之间没有直接的连接。这种独立性使得树结构在表示复杂数据时具有更高的灵活性和可扩展性。
有序性与无序性：虽然一般树中的子节点没有固定的顺序，但在某些特殊类型的树（如二叉搜索树）中，子节点是按照一定的顺序排列的。这种有序性有助于实现高效的查找和排序操作。然而，在一般树中，子节点的排列通常是无序的。
节点度数可变：在树中，节点的度数（即子节点的数量）是可变的。这意味着一个节点可以有任意数量的子节点（在一般树中）或最多两个子节点（在二叉树中）。这种灵活性使得树能够适应不同规模和数据复杂度的需求。
可遍历性：树结构支持多种遍历方式，如先序遍历、中序遍历、后序遍历和层次遍历等。这些遍历方式使得我们能够以不同的顺序访问树中的节点，从而满足不同的数据处理需求。

二叉树的定义

二叉树是树的一种特殊形式，它的每个节点最多有两个子节点，分别被称为左子节点和右子节点。

二叉树与数主要有以下区别：

二叉树每个结点至多只有两颗子树(即二叉树中不能存在度大于 2 的结点)
二叉树的子树有左右之分，其次序不能任意颠倒
即使树中某结点只有一棵子树，也要区分它是左子树还是右子树

二叉树具有以下特性：

二叉树的度：二叉树的度最大为2，即每个节点最多有两个子节点。
左子树和右子树：对于二叉树的每个节点，其左子树上的所有节点的值都小于该节点的值，而右子树上的所有节点的值都大于该节点的值（这一特性在二叉搜索树中尤为重要）。
满二叉树：除了叶子节点外，每个节点都有两个子节点的二叉树被称为满二叉树。
完全二叉树：若一个二叉树在层序遍历下，前面的节点都是满的，且后面的节点都是连续的叶子节点，则这个二叉树被称为完全二叉树。

二叉树的5种基本形态：
1.空二叉树
2.只有一个根节点
3.根节点只有左子树
4.根节点只有右子树
5.根节点既有左子树，又有右子树

树和二叉树的抽象数据类型定义

树的抽象数据类型定义（ADT for Trees）

数据对象：T

数据成员：

节点（Node）：每个节点包含一个数据元素以及指向其子节点的指针（或引用）。

基本操作：

CreateTree()：创建一个空树，返回树的根节点指针（或引用）。
DestroyTree(T)：销毁树T，释放其占用的所有内存。
InsertNode(T, data, parentNode)：在树T中，向指定父节点parentNode下插入一个新节点，新节点的数据为data。
DeleteNode(T, node)：从树T中删除指定节点node。
FindNode(T, data)：在树T中查找数据为data的节点，返回找到的节点指针（或引用），若未找到则返回空。
TraverseTree(T, visitorFunction)：按照某种遍历方式（如深度优先或广度优先）遍历树T，并对每个节点执行visitorFunction函数。
GetRootNode(T)：返回树T的根节点指针（或引用）。

二叉树的抽象数据类型定义（ADT for Binary Trees）

数据对象：BT

数据成员：

节点（Node）：每个节点包含一个数据元素，以及指向其左子节点和右子节点的指针（或引用）。

基本操作：

CreateBinaryTree()：创建一个空二叉树，返回二叉树的根节点指针（或引用）。
DestroyBinaryTree(BT)：销毁二叉树BT，释放其占用的所有内存。
InsertLeft(BT, parentNode, data)：在二叉树BT中，向指定父节点parentNode的左子树插入一个新节点，新节点的数据为data。
InsertRight(BT, parentNode, data)：在二叉树BT中，向指定父节点parentNode的右子树插入一个新节点，新节点的数据为data。
DeleteNode(BT, node)：从二叉树BT中删除指定节点node，保持二叉树的性质（如二叉搜索树的性质）。
FindNode(BT, data)：在二叉树BT中查找数据为data的节点，返回找到的节点指针（或引用），若未找到则返回空。
InorderTraversal(BT, visitorFunction)：对二叉树BT进行中序遍历，并对每个节点执行visitorFunction函数。
PostorderTraversal(BT, visitorFunction)：对二叉树BT进行后序遍历，并对每个节点执行visitorFunction函数。
PreorderTraversal(BT, visitorFunction)：对二叉树BT进行前序遍历，并对每个节点执行visitorFunction函数（注意：在某些定义中，前序遍历可能不被视为二叉树的基本操作，但它是常见的遍历方式）。
LevelOrderTraversal(BT, visitorFunction)：对二叉树BT进行层序遍历，并对每个节点执行visitorFunction函数。
GetRootNode(BT)：返回二叉树BT的根节点指针（或引用）。

二叉树的性质和存储结构

二叉树的性质

定义：
- 二叉树（Binary Tree）是树形数据结构的一种，其中每个节点最多有两个子节点，分别称为左子节点和右子节点。
- 特殊的二叉树包括满二叉树、完全二叉树和平衡二叉树等。
基本性质：
- 递归定义：二叉树要么是空树，要么由一个根节点和左、右两棵互不相交的二叉树组成。
- 节点数目：
  - 对于一个非空二叉树，若其深度为h，则最多有 2h−1 个节点（满二叉树的情况）。
  - 在第i层（i从1开始计数）上最多有 2i−1 个节点。
- 边数目：
  - 对于一个有n个节点的二叉树，边数为 n−1。
- 叶子节点数目：
  - 对于一个非空二叉树，若其总结点数为n，则叶子节点数目在 [2n,n−1] 之间。
- 完全二叉树性质：
  - 在完全二叉树中，除了最后一层外，每一层都是满的，且最后一层的节点都靠左对齐。

性质1：在二叉树的第i层上至多有2i-1个结点（i>=1）

性质2：深度为k的二叉树至多有2k-1个结点（k>=1）

性质3：对任何一棵二叉树T，如果其终端结点数为n0,度为2的结点数为n2，则n0 = n2+1

遍历：
- 前序遍历（Preorder Traversal）：根节点 -> 左子树 -> 右子树。
- 中序遍历（Inorder Traversal）：左子树 -> 根节点 -> 右子树（适用于二叉搜索树）。
- 后序遍历（Postorder Traversal）：左子树 -> 右子树 -> 根节点。
- 层次遍历（Level Order Traversal）：按层次从上到下、从左到右遍历。

二叉树的存储结构

二叉树主要有以下几种存储方式：

链式存储结构：

每个节点包含三部分：数据域（存储节点的值）、左指针域（指向左子节点）、右指针域（指向右子节点）。
优点：节省空间，适合表示稀疏二叉树。
缺点：需要额外的指针空间，访问某个节点时需要通过指针操作，相对复杂。

顺序存储结构：

使用数组来存储二叉树的节点，通常适用于完全二叉树或接近完全二叉树的情况。
假设根节点在数组的第1个位置（索引为0的位置可以不用或用于表示空节点），则对于任意节点i：
- 左子节点的索引为 2i
- 右子节点的索引为 2i+1
- 父节点的索引为 ⌊2i⌋
优点：访问节点速度快，数组操作相对简单。
缺点：空间利用率低，对于非完全二叉树会有大量的空间浪费。

遍历二叉树和线索二叉树

二叉树的遍历（Java）

在Java中，二叉树的遍历可以通过递归或迭代的方式实现。以下是四种基本遍历方式的递归实现：

前序遍历（Pre-order Traversal）：

class TreeNode {int val;TreeNode left;TreeNode right;TreeNode(int x) {val = x;}
}public class BinaryTreeTraversal {public void preorder(TreeNode root) {if (root != null) {System.out.print(root.val + " "); // 访问当前节点preorder(root.left); // 遍历左子树preorder(root.right); // 遍历右子树}}
}

中序遍历（In-order Traversal）：

public class BinaryTreeTraversal {public void inorder(TreeNode root) {if (root != null) {inorder(root.left); // 遍历左子树System.out.print(root.val + " "); // 访问当前节点inorder(root.right); // 遍历右子树}}
}

后序遍历（Post-order Traversal）：

public class BinaryTreeTraversal {public void postorder(TreeNode root) {if (root != null) {postorder(root.left); // 遍历左子树postorder(root.right); // 遍历右子树System.out.print(root.val + " "); // 访问当前节点}}
}

层次遍历（Level-order Traversal）（通常使用队列实现）：

import java.util.LinkedList;
import java.util.Queue;public class BinaryTreeTraversal {public void levelorder(TreeNode root) {if (root == null) return;Queue<TreeNode> queue = new LinkedList<>();queue.add(root);while (!queue.isEmpty()) {TreeNode node = queue.poll();System.out.print(node.val + " ");if (node.left != null) queue.add(node.left);if (node.right != null) queue.add(node.right);}}
}

线索二叉树（Threaded Binary Tree）

线索二叉树是一种特殊的二叉树，在这种树中，空的左孩子或右孩子指针被用来存储指向中序遍历前驱或后继节点的指针，这种指针被称为线索（thread）。

在Java中实现线索二叉树涉及更多细节，包括定义节点类以包含额外的线索信息和维护线索状态（左线索、右线索或正常指针）。此外，还需要实现构建线索二叉树和遍历线索二叉树的算法。

由于实现线索二叉树涉及较为复杂的指针操作和树结构的修改，这里只提供一个线索二叉树节点类的基本定义和构建线索的伪代码思路。

enum PointerTag { LINK, THREAD }class ThreadedNode {int val;ThreadedNode left, right;PointerTag leftTag, rightTag;ThreadedNode(int x) {val = x;left = right = null;leftTag = rightTag = PointerTag.LINK;}
}// 伪代码思路：
// 1. 中序遍历二叉树，同时设置线索。
// 2. 在遍历过程中，根据节点的左/右孩子是否为空来设置相应的线索和标签。
// 3. 需要注意维护一个前驱节点变量来设置后继线索。// 注意：这里的代码只是一个框架和思路，实际实现需要更详细的逻辑和错误处理。

树和森林

树（Tree）

定义：
- 树是由一个集合以及在该集合上定义的一种关系构成的。集合中的元素被称为树的结点，所定义的关系称为父子关系。
- 当集合为空时，称为空树；当集合非空时，有且仅有一个特定的结点被称为根结点。
基本术语：
- 结点：包含一个数据元素及若干指向其子树的分支。
- 结点的度：一个结点拥有的子树的数目。
- 叶子或终端结点：度为0的结点。
- 非终端结点或分支结点：度不为0的结点。
- 树的度：树内各结点的度的最大值。
- 孩子结点或子结点：结点的子树的根称为该结点的孩子结点或子结点。
- 双亲结点或父结点：若一个结点含有子结点，则这个结点称为其子结点的双亲结点或父结点。
- 兄弟结点：同一个双亲的孩子之间互称兄弟。
- 祖先结点：从根到该结点所经分支上的所有结点。
- 子孙结点：以某结点为根的子树中任一结点都称为该结点的子孙。
- 结点的层次：从根开始定义起，根为第一层，根的孩子为第二层。若某结点在第i层，则其子树的根就在第i+1层。
- 树的深度或高度：树中结点的最大层次。
存储结构：
- 双亲表示法：用一个一维数组存储每个结点，数组的下标就是结点的指针位置，每个结点包括一个数据域和与指向父亲结点的数组下标的域。
- 孩子链表表示法：用一个线性表来存储树的所有结点信息，称为结点表。每个结点的孩子结点排列起来，看成一个线性表，用单链表存储。
- 孩子兄弟表示法：又称二叉树表示法，每个结点除了数据域外，还包含第一个孩子和右邻兄弟。
遍历：
- 先序遍历：访问树的根结点；从左到右，依次先序遍历根的每棵子树。
- 后序遍历：从左到右，依次后序遍历根的每棵子树；访问树的根结点。

森林（Forest）

定义：
- 森林是m棵互不相交的树的集合。
与树的关系：
- 对树中的每个结点而言，其子树的集合即为森林。
- 删去一棵树的根，就得到一个森林；反之，加上一个结点作为树根，森林就变为一棵树。
遍历：
- 先序遍历：访问森林第一棵树的根结点；先序遍历第一棵树中根结点的子树森林；先序遍历除去第一棵树后剩余的树构成的森林。
- 中序遍历：中序遍历第一棵树中根结点的子树森林；访问森林中第一棵树的根结点；中序遍历除去第一棵树后剩余的树构成的森林。
- 后序遍历：中序遍历第一棵树中根结点的子树森林；中序遍历除去第一棵树后剩余的树构成的森林；访问森林中第一棵树的根结点。

树与二叉树的转换

树转化二叉树：
- 顺序连接同一结点的兄弟结点。
- 保留每个结点到其第一个孩子结点的连接作为该结点的左孩子结点，删除这个结点到其他孩子结点的连接。
- 以树的根结点为中心，顺时针旋转一定角度，使得结构层次分明。
二叉树还原为树或森林：
- 按层次序列对二叉树的每个结点做操作。
- 如果是根结点或者是左孩子结点，则不做任何改动。
- 如果是右孩子，将其当前父亲的父亲设置为当前结点的父结点，若其当前父亲的父亲为空，则改动后其父亲为空。

树和森林的遍历

树的遍历

对于一棵树，主要有以下几种遍历方法：

先序遍历（Preorder Traversal）：
- 访问根结点。
- 依次先序遍历每个子树。
- 对于每个子树，重复上述步骤。
中序遍历（Inorder Traversal，但通常不用于树，而更多用于二叉树）：
- 在树结构中，中序遍历不是标准遍历方式，因为它在二叉树中有特定意义（先遍历左子树，然后访问根，最后遍历右子树）。
- 但在某些特殊类型的树（如二叉搜索树）或特定应用中，可能会定义类似中序的遍历方式。
后序遍历（Postorder Traversal）：
- 依次后序遍历每个子树。
- 访问根结点。
层次遍历（Level Order Traversal）：
- 按层次从上到下、从左到右遍历结点。
- 通常使用队列来实现。

森林的遍历

森林是由多棵树组成的集合。对于森林，可以将其视为由一棵虚拟的根结点连接的所有树的集合，然后应用树的遍历方法。但更常见的是，直接对森林中的每棵树分别进行遍历。

先序遍历森林：
- 对森林中的第一棵树进行先序遍历。
- 对森林中除去第一棵树后的剩余树构成的森林进行先序遍历。
中序遍历森林（不是标准方式，但可定义）：
- 对森林中的第一棵树进行中序遍历（如果定义了树的中序遍历）。
- 访问虚拟的根结点（实际上在森林遍历中通常不显式访问）。
- 对森林中除去第一棵树后的剩余树构成的森林进行中序遍历。
注意：由于中序遍历在树结构中不是标准方式，因此这种中序遍历森林的定义也不是标准的。
后序遍历森林：
- 对森林中的第一棵树进行后序遍历。
- 对森林中除去第一棵树后的剩余树构成的森林进行后序遍历。

树与二叉树的转换及遍历

在将树转换为二叉树后，可以利用二叉树的遍历方法来间接实现树的遍历。转换规则如下：

树中的每个结点转换为二叉树中的一个结点。
树中结点的第一个孩子转换为二叉树中的左孩子。
树中结点的其他兄弟依次转换为二叉树中右孩子的右孩子（形成一条右链）。

转换后的二叉树可以使用二叉树的遍历方法（前序、中序、后序、层次）进行遍历。由于树转换为二叉树后，树的先序遍历与二叉树的前序遍历对应，树的后序遍历与二叉树的中序遍历（左-根-右，但这里的“根”实际上是原树中结点的最后一个孩子，而访问顺序是最后一个孩子-根-其他兄弟形成的右链）有某种对应关系（但需要注意，这种对应不是直接的，因为二叉树的中序遍历在访问根结点前会先访问左子树，而树的后序遍历则不会这样）。然而，通常不直接使用二叉树的中序遍历来表示树的后序遍历，而是使用递归或迭代的方法直接实现树的后序遍历。

哈弗曼树及其应用

哈夫曼树（Huffman Tree），又称最优二叉树，是一种重要的数据结构，在计算机科学中有着广泛的应用。以下是对哈夫曼树及其应用的详细介绍：

哈夫曼树的定义

给定N个权值作为N个叶子结点，构造一棵二叉树，若该树的带权路径长度（WPL）达到最小，则称这样的二叉树为最优二叉树，也称为哈夫曼树。哈夫曼树的特点是权值较大的结点离根较近，从而保证了整体带权路径长度的最小化。

哈夫曼树的构造

哈夫曼树的构造过程是一个自底向上的过程，具体步骤如下：

将给定的N个权值视为N棵只有根结点的二叉树（森林）。
在森林中选出两个根结点权值最小的树进行合并，作为一棵新树的左、右子树，新树的根结点权值为其左、右子树根结点权值之和。
从森林中删除这两个已合并的树，并将新树加入森林。
重复上述步骤，直到森林中只剩下一棵树，这棵树即为所求得的哈夫曼树。

哈夫曼树的应用

哈夫曼树的主要应用之一是数据压缩，特别是在通信、文件压缩、图像压缩和音频编码等领域。以下是哈夫曼树在数据压缩中的具体应用：

哈夫曼编码：
- 哈夫曼编码是一种基于哈夫曼树的变长编码方法。在编码过程中，根据字符出现的频率构建哈夫曼树，并生成对应的编码表。高频字符使用较短的编码，低频字符使用较长的编码。
- 编码时，将字符替换为对应的二进制码。由于高频字符具有较短的编码，因此整体编码长度会显著减少，从而实现数据压缩。
数据压缩算法：
- 哈夫曼编码被广泛应用于各种数据压缩算法中，如JPEG图像压缩、MP3音频编码等。这些算法利用哈夫曼编码对图像、音频等数据进行压缩，以减少存储空间和传输时间。
通信中的信道编码：
- 在通信系统中，哈夫曼编码也被用于信道编码。通过将传输的字符替换为哈夫曼编码，可以减少传输所需的比特数，从而提高通信效率。

哈夫曼树的优点

高效性：哈夫曼树通过构建最优二叉树，实现了带权路径长度的最小化，从而提高了数据压缩的效率。
灵活性：哈夫曼树可以根据字符出现的频率动态调整编码长度，适用于不同类型的数据压缩需求。
广泛应用性：哈夫曼树在通信、文件压缩、图像压缩和音频编码等领域有着广泛的应用，为数据传输和存储提供了有效的解决方案。