C 语言画树的程序

在计算机科学中，树是数据结构中最常见的应用之一。它们提供了快速的插入、删除和搜索功能，以及一种存储分层数据的有效方法。树在许多不同场景中使用，例如数据库索引、排序算法和分层关系表示。在 C 编程中，可以使用连接父子节点之间节点的指针来构建树。这使得在代码中高效地建模和修改树结构成为可能。在本文中，我们将探讨树数据结构的基本 C 实现。我们将介绍如何执行插入、删除和搜索等重要操作，并描述节点结构。理解树对于学习 C 数据结构和算法至关重要。

什么是树？

树是一种非线性分层数据结构，由节点和边组成。它顶部有一个根节点，底部有叶节点，每个节点下面有 0 个或多个子节点。节点通过从每个节点回溯到其父节点的连接以父子关系连接，并包含数据项。树可用于表示各种数据结构，包括计算机文件夹系统、数据库索引、决策树、解析器和易于搜索的排序列表。从基部到叶子的最长路径上的总边数决定了树的高度。树是适应性强且灵活的数据结构，可用于快速添加、删除、搜索和排序数据。

树的关键术语

树有几个术语。以下是一些主要的树术语

节点 - 节点是树数据结构的基本组成部分。每个节点存储数据并链接到子节点。

根 - 根节点是树层次结构顶部的唯一节点。它锚定树。

父子 - 节点通过父子关系从上到下连接。每个节点都可以链接到其下方的子节点。

叶 - 叶节点是底层没有子节点的节点。它们表示树中的终点。

子树 - 子树是由一个节点及其所有后代组成的一部分树。

高度 - 高度测量从根到最低叶子的边数。它表示最大深度。

深度 - 深度是节点到根的距离，以边为单位。根的深度为0。

层 - 层表示深度加 1。根在第 1 层。

度 - 度是节点的子树/子节点数量。叶子的度为 0。

二叉树 - 二叉树限制节点最多有 2 个子节点。这种结构被广泛使用。

二叉搜索树 - BST按顺序组织左子树和右子树，以便左 <= 节点 < 右，从而实现高效搜索。

平衡树 - 平衡树平衡子树的高度。它能够实现高效的操作。

满二叉树 - 满二叉树要求每个节点有0或2 个子节点（而不是 1 个）。

完全二叉树 - 完全二叉树填充除最后一层外的所有层，并将节点靠左排列。

森林 - 森林包含多个独立的树。

遍历 - 遍历一棵树意味着系统地访问所有节点，通常是递归地。

树的关键属性

树有几个属性。以下是一些主要的树属性

• 分层 - 树对元素之间的分层关系进行建模。在父子关系中，每个元素可以有任意数量的从属元素在其下方。
• 递归 - 树被递归定义，其中每个节点本身就是一棵由其后代组成的树。树上的算法通常是递归定义的。
• 有根 - 树在顶部有一个单一的根节点，并从其向下生长。根节点没有父节点，所有其他节点最终都链接回根节点。
• 带标签 - 每个节点都有一个与之关联的值，称为其标签或数据元素。树在其节点中存储数据。
• 连通 - 所有节点通过从父节点到子节点的边连接。每个节点（根除外）都有一个来自其父节点的传入边。
• 无序 - 各层上的节点没有按特定顺序排列。节点的子节点没有特定顺序。
• 无环 - 树不能有环。边具有从父节点到子节点的特定方向，排除了环。
• 动态大小 - 树可以随着节点的添加或删除而增大或缩小。树没有固定的大小。
• 可变度 - 节点可以具有任意数量的子节点或子树大小。有些节点可能没有子节点，而有些节点有很多。

示例

让我们举一个例子来演示如何在 C 语言中创建一个树。

输出

Binary Tree (In-order traversal): 4 2 5 1 3

重要点说明

1. 在此示例中，包含h和stdlib.h头文件，用于标准输入/输出和内存分配函数。
2. 定义一个TreeNode 结构来表示二叉树中的每个节点。它包含一个整数数据值以及指向左子节点和右子节点的指针。
3. 创建一个createNode() 函数来为新的TreeNode分配内存并进行初始化。它将数据值和子节点指针设置为 null。
4. 定义一个inOrderTraversal()函数，以中序顺序（左子树、根、右子树）打印树节点。如果根不为 null，它将递归地遍历。
5. 在main()函数中，首先创建数据为 1 的根节点。
6. 向根节点添加数据为 2 和 3 的左和右子节点。
7. 向节点 2 添加数据为 4 和 5 的进一步左子节点和右子节点。
8. 通过调用inOrderTraversal()并传递根节点来打印树。它将按排序顺序打印节点值。
9. 通过从叶子节点向上遍历到根节点来释放为每个TreeNode分配的内存。
10. Return 0表示程序成功执行。

树的类型

树有几种类型。以下是一些重要的树类型

• 二叉树 - 每个节点最多有两个子节点，称为左子节点和右子节点。二叉树常用于二叉搜索树和堆。
• 二叉搜索树 (BST) - 一种二叉树，其中节点按顺序组织 - 左子树的节点小于父节点，右子树的节点大于父节点。提供快速的查找、插入和删除。
• AVL 树 - 自平衡二叉搜索树，其中任何节点的左子树和右子树的高度差不超过 1。避免了倾斜，并提供O(log n)的查找时间。
• 红黑树 - 一种自平衡 BST，其中节点具有额外的颜色位，以确保树在插入和删除期间保持近似平衡。
• B 树 - 一种树，其中每个节点可以有超过 2 个子节点，最多可达某个预定义的阶数。用于数据库和文件系统以实现高效搜索和顺序访问。
• 堆 - 一种特殊的树结构，其中父节点相对于子节点进行排序。两种常见的类型是最大堆和最小堆，最大和最小的值位于根部。用于实现优先队列。
• Trie（前缀树） - 一种树，其中节点存储由字符索引的关联数组。可以高效地查找和插入字符串。用于字典、数据库和拼写检查器。
• 后缀树 - 特殊的Trie，其中给定字符串的后缀存储在树的边上。允许快速的子串查询。

树遍历

1. 中序遍历

在此遍历中，首先访问左子树，然后是根节点，最后是右子树。它用于在二叉搜索树中按排序顺序获取节点。

伪代码

2. 前序遍历

在此，首先访问根节点，然后是左子树，最后是右子树。它有助于创建树的副本。

伪代码

3. 后序遍历

在此遍历中，首先访问左子树，然后是右子树，最后是根节点。它用于删除树或执行其他清理操作。

伪代码

这三种遍历允许您以不同的顺序系统地访问树中的所有节点。它们是许多常见树操作的基础。

树的应用

树有几种应用。以下是一些重要的树应用

二叉搜索树 (BST)：用于高效的搜索、插入和删除数据，是实现字典和符号表的理想选择。

表达式树：用于表示数学表达式，允许高效的求值和简化。

堆数据结构：一种特殊的二叉树，用于实现优先队列，例如二叉堆和斐波那契堆。

文件系统：树用于表示文件系统中的目录结构。每个目录可以包含文件或子目录，形成分层结构。

分层数据表示：树用于表示分层数据，例如组织结构图、家谱和XML/JSON数据结构。

人工智能：树在决策树算法中用于分类和回归任务。