qidao123.com技术社区-IT企服评测·应用市场

标题: 重生之我在异天放学编程之数据结构与算法：深入数和二叉树篇 [打印本页]

---

作者: 瑞星    时间: 2025-1-6 06:55
标题: 重生之我在异天放学编程之数据结构与算法：深入数和二叉树篇
大家好，这里是小编的博客频道
小编的博客：就爱学编程
    很高兴在CSDN这个大家庭与大家相识，盼望能在这里与大家共同进步，共同收获更好的本身！！！
  
  

---

   那接下来就让我们开始遨游在知识的海洋！
  

---

一、树的根本概念

   界说：树是一种非线性数据结构，它由 n（n≥0）个有限节点组成一个具有层次关系的集合。它有一个特殊的节点，称为根节点，别的节点分成 m（m≥0）个互不相交的子集，每个子集又是一棵树，称为原树的子树。
  根本术语：
   

• 节点的度：一个节点含有的子树的个数称为该节点的度。
  
• 叶子节点：度为 0 的节点称为叶节点或终端节点。
  
• 非叶子节点：度不为 0 的节点称为非叶节点或非终端节点。除根节点之外，非叶子节点也称为内部节点。
  
• 节点的层次：从根开始界说起，根为第一层，根的子节点为第二层，以此类推。
  
• 树的高度或深度：树中节点的最大层次。
  
• 父节点和子节点：若节点 A 有直达节点 B 的路径，且 A 在这条路径上距离 B 最近，则称 A 为 B 的父节点，B 是 A 的子节点。
  
• 兄弟节点：有共同父节点的节点互为兄弟节点。
  

  表示方法：可以用孩子链表表示法、双亲孩子表示法和孩子-兄弟表示法等来表示一棵树。

---

二、二叉树的根本概念

   界说：二叉树是树形结构的一种特殊形式，它的特点是每个节点最多有两个子节点，通常被称为左子节点和右子节点。
  性子：
   在二叉树的第 i 层上至多有 2^(i-1) 个节点（i≥1）。
深度为 k 的二叉树至多有 2^k - 1 个节点（k≥1）。
对任何一棵二叉树 T，如果其终端节点数为 n0，度为 2 的节点数为 n2，则 n0 = n2 + 1。
  分类：
   满二叉树：一棵深度为 k 且有 2^k - 1 个节点的二叉树称为满二叉树。
完全二叉树：深度为 k 的，有 n 个节点的二叉树，当且仅当其每一个节点都与深度为 k 的满二叉树中编号从 1 至 n 的节点逐一对应时称之为完全二叉树。
  遍历方法：
   

• 前序遍历：访问次序是根节点→左子树→右子树。
  
• 中序遍历：访问次序是左子树→根节点→右子树。
  
• 后序遍历：访问次序是左子树→右子树→根节点。
  
• 层序遍历：按树的结构从上到下、从左到右依次访问各个节点。
  

  

---

三、在 C 语言中实现二叉树

在 C 语言中，可以使用结构体和指针来实现二叉树。以下为例：

1. #include <stdio.h>
2. #include <stdlib.h>
4. // 定义二叉树节点结构体
5. typedef struct TreeNode {
6.     int val;
7.     struct TreeNode *left;
8.     struct TreeNode *right;
9. } TreeNode;
11. // 创建新节点
12. TreeNode* createNode(int val) {
13.     TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));
14.     newNode->val = val;
15.     newNode->left = NULL;
16.     newNode->right = NULL;
17.     return newNode;
18. }
20. // 前序遍历
21. void preOrderTraversal(TreeNode* root) {
22.     if (root == NULL) return;
23.     printf("%d ", root->val);
24.     preOrderTraversal(root->left);
25.     preOrderTraversal(root->right);
26. }
28. // 中序遍历
29. void inOrderTraversal(TreeNode* root) {
30.     if (root == NULL) return;
31.     inOrderTraversal(root->left);
32.     printf("%d ", root->val);
33.     inOrderTraversal(root->right);
34. }
36. // 后序遍历
37. void postOrderTraversal(TreeNode* root) {
38.     if (root == NULL) return;
39.     postOrderTraversal(root->left);
40.     postOrderTraversal(root->right);
41.     printf("%d ", root->val);
42. }
44. int main() {
45.     // 创建二叉树
46.     TreeNode* root = createNode(1);
47.     root->left = createNode(2);
48.     root->right = createNode(3);
49.     root->left->left = createNode(4);
50.     root->left->right = createNode(5);
52.     // 遍历二叉树
53.     printf("Pre-order traversal: ");
54.     preOrderTraversal(root);
55.     printf("
56. ");
58.     printf("In-order traversal: ");
59.     inOrderTraversal(root);
60.     printf("
61. ");
63.     printf("Post-order traversal: ");
64.     postOrderTraversal(root);
65.     printf("
66. ");
68.     // 注意：这里只是示例代码，没有实现释放内存的操作，实际使用中需要添加释放内存的代码以避免内存泄漏。
70.     return 0;
71. }

复制代码

• 这个例子中，我们界说了二叉树节点的结构体 TreeNode ，并实现了创建新节点和前序、中序、后序遍历的函数。然后在 main 函数中创建了一个简单的二叉树，并对它进行了遍历。
  

---

快乐的时光总是短暂，咱们下篇博文再见啦！！！不要忘了，给小编点点赞和收藏支持一下，在此非常感谢！！！


免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。

---

欢迎光临 qidao123.com技术社区-IT企服评测·应用市场 (https://dis.qidao123.com/)

Powered by Discuz! X3.4