【数据结构】二叉树-C语言版（三）-阿里云开发者社区

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

2023-02-07 66

版权

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

简介： 【数据结构】二叉树-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语言版（三）

二叉树应用

热门文章

最新文章

相关课程

相关电子书