AI 助理
备案控制台
开发者社区 云计算 文章 正文

【数据结构】二叉树-C语言版（三）

2023-02-07 70
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 【数据结构】二叉树-C语言版

二叉树应用

1.单值二叉树 OJ链接

分析：判断所有节点的值是否相等，当根值等于左孩子的值并且根值等于右孩子的值时，需要递归判断左子树的根值是否等于其左孩子的值并且左子树的根值等于其右孩子的值，并且需要递归判断右子树的根值是否等于其左孩子的值并且右子树的根值等于其右孩子的值······

1. /**
2.  * Definition for a binary tree node.
3.  * struct TreeNode {
4.  *     int val;
5.  *     struct TreeNode *left;
6.  *     struct TreeNode *right;
7.  * };
8.  */
9. 
10. bool isUnivalTree(struct TreeNode* root){
11.     if(root == NULL)
12.     {
13.         return true;
14.     }
15.    
16.     if((root->left) && (root->left->val != root->val))    
17.     {
18.         return false;
19.     }
20. 
21.     if((root->right) && (root->right->val != root->val))    
22.     {
23.         return false;
24.     }
25. 
26.     return isUnivalTree(root->left) && isUnivalTree(root->right);
27. }

2.二叉树的前序遍历 OJ链接

分析：要求返回数组必须是malloc的，但是需要malloc多大的空间呢？malloc树的结点总数个空间，因此要

（1）求树的节点个数

（2）递归遍历整棵树，将根节点存到数组中

1. /**
2.  * Definition for a binary tree node.
3.  * struct TreeNode {
4.  *     int val;
5.  *     struct TreeNode *left;
6.  *     struct TreeNode *right;
7.  * };
8.  */
9. 
10. 
11. /**
12.  * Note: The returned array must be malloced, assume caller calls free().
13.  */
14. 
15. //求树的大小
16. int TreeSize(struct TreeNode* root)
17. {
18.   return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;
19. }
20. 
21. void _preorder(struct TreeNode* root,int * arr,int* pi)
22. {
23.     if(root == NULL)
24.     {
25.         return;
26.     }
27. 
28.     //将根节点保存起来
29.     arr[(*pi)++] = root->val;
30.     _preorder(root->left,arr,pi);
31.     _preorder(root->right,arr,pi);
32. }
33. 
34. int* preorderTraversal(struct TreeNode* root, int* returnSize){
35.     *returnSize = TreeSize(root);
36. 
37.     //申请树的节点个数大小空间
38.     int* arr = (int*)malloc(sizeof(int)*(*returnSize));
39.     int i = 0;
40.     _preorder(root,arr,&i);
41.     
42.     return arr;
43. }

 3.相同的树  OJ链接

分析：需要结构相同且结点有相同的值

（1）结构相同可以用递归遍历左右子树的根节点是否存在来判断

（2）值是否相同可以用递归遍历左右子树的根节点值是否相等来判断

1. /**
2.  * Definition for a binary tree node.
3.  * struct TreeNode {
4.  *     int val;
5.  *     struct TreeNode *left;
6.  *     struct TreeNode *right;
7.  * };
8.  */
9. 
10. bool isSameTree(struct TreeNode* p, struct TreeNode* q){
11.     //左右子树都为空
12.     if((p == NULL) && (q == NULL))
13.     {
14.         return true;
15.     }
16. 
17.     //左子树为空，右子树不为空
18.     if((p == NULL) && (q != NULL))
19.     {
20.         return false;
21.     }
22. 
23.     //左子树不为空，右子树为空
24.     if((p != NULL) && (q == NULL))
25.     {
26.         return false;
27.     }
28. 
29.     //左右子树都不为空
30.     if((p != NULL) && (q != NULL))
31.     {
32.         if(p->val == q->val)
33.         {
34.             return isSameTree(p->left,q->left) && isSameTree(p->right,q->right);
35.         }     
36.     }
37.     return false;
38. }

4.对称二叉树 OJ链接

分析：

（1）判断二叉树是否对称，需要判断左孩子和右孩子的结点值是否相等，就需要递归判断左孩子的左孩子值和右孩子的右孩子值是否相等······

（2）给出的函数只有一个入参，需要判断左右孩子值是否相等，最好重新写一个函数，同时入参左右结点

1. /**
2.  * Definition for a binary tree node.
3.  * struct TreeNode {
4.  *     int val;
5.  *     TreeNode *left;
6.  *     TreeNode *right;
7.  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
8.  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
9.  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
10.  * };
11.  */
12. 
13. bool _isSymmetric(struct TreeNode* left,struct TreeNode* right)
14. {
15.     if(left == NULL && right == NULL)
16.     {
17.         return true;
18.     }
19.     if(left == NULL && right != NULL)
20.     {
21.         return false;
22.     }
23.     if(left != NULL && right == NULL)
24.     {
25.         return false;
26.     }
27.  
28.     if(left->val == right->val)
29.     {
30.         return _isSymmetric(left->left,right->right) && _isSymmetric(left->right,right->left);
31.     }
32.       
33.     return false;
34. }
35.    
36. bool isSymmetric(struct TreeNode* root) {
37.     if(root == NULL)
38.     {
39.         return true;
40.     }
41.  
42.     return _isSymmetric(root->left,root->right);
43. }

5.平衡二叉树  OJ链接

方法一：

（1）求出左右子树的高度，如果高度差<=1，则是平衡二叉树

（2）平衡二叉树要求以每个结点为根的子树都是平衡的，因此要递归判断每个子结点是否是平衡的

1. /**
2.  * Definition for a binary tree node.
3.  * struct TreeNode {
4.  *     int val;
5.  *     struct TreeNode *left;
6.  *     struct TreeNode *right;
7.  * };
8.  */
9. 
10. int TreeDepth(struct TreeNode* root)
11.     {
12.         if(root == NULL)
13.         {
14.             return 0;
15.         }
16.         return fmax(TreeDepth(root->left),TreeDepth(root->right))+1;
17.     }
18. bool isBalanced(struct TreeNode* root) {
19.     if(root == NULL)
20.     {
21.         return true;
22.     }
23.     return fabs(TreeDepth(root->left)-TreeDepth(root->right)) < 2
24.          &&isBalanced(root->left)
25.          &&isBalanced(root->right);
26. }

方法二：判断左子树是否平衡的同时判断右子树是否平衡，同时把高度带给上一层父亲，让父亲计算父亲为根节点的子树高度

1. bool _isBalanced(struct TreeNode* root,int* ph)
2. {
3.     if(root == NULL)
4.     {
5.         *ph = 0;
6.         return true;
7.     }
8. 
9.     //后序
10.     //先判断左子树，再判断右子树
11.     int leftHeight= 0;
12.     if(_isBalanced(root->left,&leftHeight) == false)
13.     {
14.         return false;
15.     }
16. 
17.     int rightHeight = 0;
18.     if(_isBalanced(root->right,&rightHeight) == false)
19.     {
20.         return false;
21.     }
22. 
23.     //同时再把高度带给上一层父亲
24.     *ph = fmax(leftHeight,rightHeight) + 1;
25.     return abs(leftHeight - rightHeight) < 2;
26. }
27. 
28. bool isBalanced(struct TreeNode* root) {
29.     int height = 0;
30.     return _isBalanced(root,&height);
31. }

6.另一棵树的子树   OJ链接

分析：（1）遍历root的每个结点，每个结点做根和subRoot比较是否相等

          （2）如何判断树相等，前面已经已经有代码 

1. /**
2.  * Definition for a binary tree node.
3.  * struct TreeNode {
4.  *     int val;
5.  *     struct TreeNode *left;
6.  *     struct TreeNode *right;
7.  * };
8.  */
9. 
10. 
11. bool isSameTree(struct TreeNode* p, struct TreeNode* q){
12.     //左右子树都为空
13.     if((p == NULL) && (q == NULL))
14.     {
15.         return true;
16.     }
17. 
18.     //左子树为空，右子树不为空
19.     if((p == NULL) && (q != NULL))
20.     {
21.         return false;
22.     }
23. 
24.     //左子树不为空，右子树为空
25.     if((p != NULL) && (q == NULL))
26.     {
27.         return false;
28.     }
29. 
30.     //左右子树都不为空
31.     if((p != NULL) && (q != NULL))
32.     {
33.         if(p->val == q->val)
34.         {
35.             return isSameTree(p->left,q->left) && isSameTree(p->right,q->right);
36.         }     
37.     }
38.     return false;
39. }
40. 
41. bool isSubtree(struct TreeNode* root,struct  TreeNode* subRoot) {
42.     //遍历root的每个结点，每个结点做子树的根和subRoot比较是否相等
43.     if(root == NULL)
44.     {
45.         return false;
46.     }
47. 
48.     //每个结点作为子树根和subRoot进行比较
49.     if(isSameTree(root,subRoot))
50.     {
51.         return true;
52.     }
53. 
54.     return isSubtree(root->left,subRoot) 
55.         || isSubtree(root->right,subRoot);
56. }

7.二叉树遍历 OJ链接

分析：

(1)构建树:遇到#就忽略跳到下一个字符，递归构建左右子树

(2)中序遍历

1. #include<stdio.h>
2. #include<stdlib.h>
3. 
4. typedef struct TreeNode
5. {
6.     struct TreeNode* left;
7.     struct TreeNode* right;
8.     char val;
9. }TreeNode;
10. 
11. TreeNode* CreateTree(char* str, int* pi)
12. {
13.     if (str[*pi] == '#')
14.     {
15.         ++(*pi);
16.         return NULL;
17.     }
18. 
19.     //不是#，构造根
20.     TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
21.     if (root != NULL)
22.     {
23.         root->val = str[*pi];
24.         ++(*pi);
25.     }
26.     
27. 
28.     //递归构建左子树
29.     root->left = CreateTree(str, pi);
30. 
31.     //递归构建右子树
32.     root->right = CreateTree(str, pi);
33.     return root;
34. }
35. 
36. void Inorder(TreeNode* root)
37. {
38.     if (root == NULL)
39.     {
40.         return;
41.     }
42. 
43.     Inorder(root->left);
44.     printf("%c ", root->val);
45.     Inorder(root->right);
46. }
47. 
48. int main()
49. {
50.     char str[100];
51.     scanf("%s", str);
52. 
53.     int i = 0;
54.     TreeNode* root = CreateTree(str, &i);
55.     Inorder(root);
56.     printf("\n");
57. 
58.     return 0;
59. }
关键词：
二叉树C语言
数据结构二叉树C语言
数据结构c语言
数据结构二叉树
C语言数据结构
玲娜贝儿～
目录
相关文章
ephemerals__
|
14天前
|
C语言
【数据结构】栈和队列（c语言实现）（附源码）
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表，遵循“先进后出”原则；队列则在一端插入、另一端删除，遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现，并提供了完整的代码示例。栈和队列在实际应用中非常广泛，如二叉树的层序遍历和快速排序的非递归实现等。
ephemerals__
90 9
ephemerals__
|
13天前
|
存储 搜索推荐 算法
【数据结构】树型结构详解 + 堆的实现（c语言）（附源码）
本文介绍了树和二叉树的基本概念及结构，重点讲解了堆这一重要的数据结构。堆是一种特殊的完全二叉树，常用于实现优先队列和高效的排序算法（如堆排序）。文章详细描述了堆的性质、存储方式及其实现方法，包括插入、删除和取堆顶数据等操作的具体实现。通过这些内容，读者可以全面了解堆的原理和应用。
ephemerals__
56 16
ephemerals__
|
13天前
|
C语言
【数据结构】二叉树（c语言）（附源码）
本文介绍了如何使用链式结构实现二叉树的基本功能，包括前序、中序、后序和层序遍历，统计节点个数和树的高度，查找节点，判断是否为完全二叉树，以及销毁二叉树。通过手动创建一棵二叉树，详细讲解了每个功能的实现方法和代码示例，帮助读者深入理解递归和数据结构的应用。
ephemerals__
62 8
ephemerals__
|
16天前
|
存储 C语言
【数据结构】手把手教你单链表（c语言）（附源码）
本文介绍了单链表的基本概念、结构定义及其实现方法。单链表是一种内存地址不连续但逻辑顺序连续的数据结构，每个节点包含数据域和指针域。文章详细讲解了单链表的常见操作，如头插、尾插、头删、尾删、查找、指定位置插入和删除等，并提供了完整的C语言代码示例。通过学习单链表，可以更好地理解数据结构的底层逻辑，提高编程能力。
ephemerals__
44 4
ephemerals__
|
17天前
|
存储 C语言
【数据结构】顺序表（c语言实现）（附源码）
本文介绍了线性表和顺序表的基本概念及其实现。线性表是一种有限序列，常见的线性表有顺序表、链表、栈、队列等。顺序表是一种基于连续内存地址存储数据的数据结构，其底层逻辑是数组。文章详细讲解了静态顺序表和动态顺序表的区别，并重点介绍了动态顺序表的实现，包括初始化、销毁、打印、增删查改等操作。最后，文章总结了顺序表的时间复杂度和局限性，并预告了后续关于链表的内容。
ephemerals__
49 3
ephemerals__
|
16天前
|
C语言
【数据结构】双向带头循环链表（c语言）（附源码）
本文介绍了双向带头循环链表的概念和实现。双向带头循环链表具有三个关键点：双向、带头和循环。与单链表相比，它的头插、尾插、头删、尾删等操作的时间复杂度均为O(1)，提高了运行效率。文章详细讲解了链表的结构定义、方法声明和实现，包括创建新节点、初始化、打印、判断是否为空、插入和删除节点等操作。最后提供了完整的代码示例。
ephemerals__
37 0
程序员大阳
|
算法 C语言
C语言数据结构(15)--二叉树的前序、中序、后序遍历
本文目录 1. 背景 2. 前序遍历 3. 中序遍历 4. 后序遍历 5. 层序遍历 6. 代码实现
程序员大阳
356 0
C语言数据结构(15)--二叉树的前序、中序、后序遍历
白子寰
|
1月前
|
C语言 C++
C语言 之 内存函数
C语言 之 内存函数
白子寰
33 3
Skyund
|
6天前
|
C语言
c语言调用的函数的声明
被调用的函数的声明： 一个函数调用另一个函数需具备的条件: 首先被调用的函数必须是已经存在的函数，即头文件中存在或已经定义过； 如果使用库函数，一般应该在本文件开头用#include命令将调用有关库函数时在所需要用到的信息“包含”到本文件中。.h文件是头文件所用的后缀。 如果使用用户自己定义的函数，而且该函数与使用它的函数在同一个文件中，一般还应该在主调函数中对被调用的函数做声明。 如果被调用的函数定义出现在主调函数之前可以不必声明。 如果已在所有函数定义之前，在函数的外部已做了函数声明，则在各个主调函数中不必多所调用的函数在做声明
Skyund
22 6
ephemerals__
|
26天前
|
存储 缓存 C语言
【c语言】简单的算术操作符、输入输出函数
本文介绍了C语言中的算术操作符、赋值操作符、单目操作符以及输入输出函数 `printf` 和 `scanf` 的基本用法。算术操作符包括加、减、乘、除和求余，其中除法和求余运算有特殊规则。赋值操作符用于给变量赋值，并支持复合赋值。单目操作符包括自增自减、正负号和强制类型转换。输入输出函数 `printf` 和 `scanf` 用于格式化输入和输出，支持多种占位符和格式控制。通过示例代码详细解释了这些操作符和函数的使用方法。
ephemerals__
34 10