【数据结构】二叉树———Lesson2
Hi~！这里是奋斗的小羊，很荣幸您能阅读我的文章，诚请评论指点，欢迎欢迎 ~~
💥💥个人主页：奋斗的小羊
💥💥所属专栏：C语言
🚀本系列文章为个人学习笔记，在这里撰写成文一为巩固知识，二为展示我的学习过程及理解。文笔、排版拙劣，望见谅。
目录
- 前言
- 一、TOP-K问题
- 二、二叉树的链式结构
- 2.1前中后序遍历
- 2.2节点个数
- 2.3叶子个数
- 2.4高度 / 深度
- 2.5第K层节点数
- 2.6查找值为x的节点
- 2.7相关OJ题
- 总结
前言
在TOP-K问题中有一种方法能在占用很小空间的情况下高效地找出最大或最小的前K个数。
在上篇文章介绍树时说树是递归定义的，因此二叉树的遍历、二叉树的搜索、二叉树的深度、高度、节点数、二叉树的路径求解等问题，基本都会用递归解决。
一、TOP-K问题
接上篇文章，我们简单地了解了TOP-K问题，介绍了如何从比较大的数据量中快速找出最大（最小）的前K个数据。
| 方法一：
用这些较大的数据量建堆，循环Top、Pop，找出最大（最小）的前K个数。
但是这个方法有个致命缺陷，它只适合数据量还不是特别大的情况，因为如果数据量非常大时我们还建堆的话，这对空间的消耗是很大的，那我们就要想别的办法了。如果数据海量，但我们现在只有1GB的内存，直接建堆显然行不通。
| 方法二：
将这海量数据分成合适的若干份分别建堆，找出每份中的最大（最小）的前K的数，再将这些数建堆，循环Top、Pop K次就能找到最大（最小）的前K个数。
但是这个方法也不是特别好，因为1GB的内存还是比较大的，假如这个问题非要搞我们，它有海量的数据但是只给我们1KB的内存，甚至更狠一点只给我们100Byte的空间，这时候方法二就显得力不从心了，因为这个若干份将会非常大，非常不理想。
| 方法三：
先从这海量数据中拿出前K个数建小堆（大堆），然后再不断拿出剩下的数和堆顶数据比较，如果大（小）于堆顶就替换掉堆顶，再向下调整保证堆成立，当这海量的数据全都比完后，留在堆内的数就是这海量数据中最大（最小）的前K个数。
这个方法需要注意的是如果要求我们找最大的前K个数要建小堆，最小的前K个数要建大堆。当然K也不能太大，要是我们现在可用的内存连这K个数都装不下那就有点扯淡了。
方法三代码如下：
void test1()
{FILE* pf = fopen("data.txt", "w");if (pf == NULL){perror("fopen fail");return;}//产生随机的100000个数存到磁盘中for (int i = 0; i < 100000; i++){//rand函数产生的随机数有重复，+i减少重复的数int ret = rand() + i;fprintf(pf, "%d\n", ret);}fclose(pf);pf = NULL;
}void test2()
{FILE* pf = fopen("data.txt", "r");if (pf == NULL){perror("fopen fail");return;}int k = 0;scanf("%d", &k);int* arr = (int*)malloc(k * sizeof(int));if (arr == NULL){perror("malloc fail");return;}//读取k个数到数组中for (int i = 0; i < k; i++){fscanf(pf, "%d", &arr[i]);}//k个数建小堆for (int i = (k - 1 - 1) / 2; i >= 0; i--){AdjustDown(arr, i, k);}//读取剩下的数与堆顶比较int ret = 0;while (fscanf(pf, "%d", &ret) > 0){if (ret > arr[0]){arr[0] = ret;AdjustDown(arr, 0, k);}}//留在堆内的数就是所有数中最大的前K个数for (int i = 0; i < k; i++){printf("%d ", arr[i]);}fclose(pf);pf = NULL;
}int main()
{srand((unsigned int)time(NULL));test1();test2();return 0;
}
这里又有个问题，我们怎么知道这K个数就是最大的前K个数呢？如何验证？
为了验证我们这个程序有没什么问题，这里有个简单的小方法，我们可以手动地在已经产生了100000个随机数的文件中修改K个使它们一定是最大的K个数，然后再运行程序看看是否有问题。运行前先把产生随机数的函数屏蔽掉。
可以看到此时打印出来的10个数就是我们故意放进去的最大的10个数。
二、二叉树的链式结构
在上篇文章中简单地了解了二叉树的链式存储，即用链表来表示一棵二叉树，用链表来指示元素的逻辑关系。
通常每个节点由三个域组成，一个数据域和两个指针域，分别用左指针和右指针来指向左孩子和右孩子。链式结构又分为二叉链和三叉链，当前我们学习的是二叉链，三叉链会在后面的学习中学到。
typedef int BTDataType;
//二叉链
typedef struct BinTreeNode
{struct BinTreeNode* pleft;//左孩子struct BinTreeNode* pright;//右孩子BTDataType data;
}BTNode;
二叉树的创建方式比较复杂，后续我们会深入学习，这里为了测试下面将要介绍的二叉树遍历，我们先手动创建一棵链式二叉树。
#define _CRT_SECURE_NO_WARNINGS#include <stdio.h>
#include <stdlib.h>typedef int BinTreeType;typedef struct BinaryTreeNode
{BinTreeType data;struct BinaryTreeNode* left;struct BinaryTreeNode* right;
}BTNode;BTNode* BuyNode(BinTreeType x)
{BTNode* node = (BTNode*)malloc(sizeof(BTNode));if (node == NULL){perror("malloc fail");return;}node->data = x;node->left = node->right = NULL;return node;
}BTNode* GreatBinaryTree()
{BTNode* node1 = BuyNode(1);BTNode* node2 = BuyNode(2);BTNode* node3 = BuyNode(3);BTNode* node4 = BuyNode(4);BTNode* node5 = BuyNode(5);BTNode* node6 = BuyNode(6);node1->left = node2;node1->right = node4;node2->left = node3;node4->left = node5;node4->right = node6;return node1;
}int main()
{BTNode* root = GreatBinaryTree();return 0;
}
2.1前中后序遍历
二叉树的操作离不开树的遍历，按照规则，二叉树的遍历有：前序、中序、后序（前根序、中根序、后根序）的递归结构遍历。
- 前序： 访问顺序为根节点、左子树、右子树
A B D N N N C E N N F N N
- 中序： 访问顺序为左子树、根节点、右子树
N D N B N A N E N C N F N
- 后序： 访问顺序为左子树、右子树、根节点
N N D N B N N E N N F C A
代码实现：
void PrevOrder(BTNode* root)
{if (root == NULL){printf("N ");return;}printf("%d ", root->data);PrevOrder(root->left);PrevOrder(root->right);
}void InOrder(BTNode* root)
{if (root == NULL){printf("N ");return;}InOrder(root->left);printf("%d ", root->data);InOrder(root->right);
}void PostOrder(BTNode* root)
{if (root == NULL){printf("N ");return;}PostOrder(root->left);PostOrder(root->right);printf("%d ", root->data);
}
2.2节点个数
如何计算节点的个数呢？可能有同学会想到用上面学到的前中后序遍历二叉树++计数：
int TreeSize(BTNode* root)
{int size = 0;if (root == NULL){printf("N ");return;}size++;printf("%d ", root->data);TreeSize(root->left);TreeSize(root->right);return size;
}
但这样是行不通的，因为上面我们前中后序遍历二叉树是递归实现的，每一次递归函数栈帧内都重新定义了size。
那可能又有同学说用static修饰size不就好了，但是这个方法也不太能行得通。
int TreeSize(BTNode* root)
{static int size = 0;if (root == NULL){printf("N ");return;}size++;printf("%d ", root->data);TreeSize(root->left);TreeSize(root->right);return size;
}
可以看到用static修饰后这个方法也只能计算一次，因为static修饰的变量在静态区，程序运行结束才销毁。
我们可以考虑用递归的思想解决这个问题。因为一个二叉树的节点个数是左子树节点个数+右子树节点个数+1（根节点），左子树的节点个数又是它的左子树节点个数+右子树节点个数+1（根节点），所以我们可以用递归解决这个问题。
递归计算节点数代码如下：
int TreeSize(BTNode* root)
{if (root == NULL){return 0;}return TreeSize(root->left) + TreeSize(root->right) + 1;
}
2.3叶子个数
如果节点的左指针和右指针都指向NULL，那这个节点就是叶子，如果节点为空就返回0。
int TreeLeafSize(BTNode* root)
{if (root == NULL){return 0;}if (root->left == NULL && root->right == NULL){return 1;}return TreeLeafSize(root->left) + TreeLeafSize(root->right);
}
2.4高度 / 深度
一个二叉树的高度是左子树高度和右子树高度大的一个再加一，左子树的高度又是它的左子树高度和右子树高度大的一个再加一，这显然又是一个递归问题。
int TreeHight(BTNode* root)
{ if (root == NULL){return 0;}int lefthight = TreeHight(root->left);int leftright = TreeHight(root->right);return lefthight > leftright ? lefthight + 1 : leftright + 1;
}
这里需要注意要用一个值来接收左右子树的高度，不要写成下面这种：
int TreeHight(BTNode* root)
{ if (root == NULL){return 0;}return TreeHight(root->left) > TreeHight(root->right) ? TreeHight(root->left) + 1 : TreeHight(root->right) + 1;
}
虽然下面这种看起来更简单，但是当二叉树的深度比较深时，这个代码的时间消耗是非常非常非常大的。
2.5第K层节点数
求第K层的节点数，就是相对于第二层来说求第K-1层节点数，相对于第三层来说求第K-2层节点数，也可以用递归解决，当节点不为空且K==1时返回1。
int TreeKSize(BTNode* root, int k)
{if (root == NULL){return 0;}if (k == 1){return 1;}return TreeKSize(root->left, k - 1) + TreeKSize(root->right, k - 1);
}
2.6查找值为x的节点
查找值为x的节点可以用前序遍历二叉树解决，当节点值等于x时返回节点指针，如果不等于则查找左子树，如果左子树找到了就返回节点指针，如果没找到（返回NULL）则查找右子树，不管找没找到都返回右子树的返回值。
BTNode* TreeFind(BTNode* root, BinTreeType x)
{if (root == NULL){return NULL;}if (root->data == x){return root;}BTNode* node = TreeFind(root->left, x);if (node)//如果为空则左子树没找到{return node;}return TreeFind(root->right, x);
}
2.7相关OJ题
Leetcode—单值二叉树
bool isUnivalTree(struct TreeNode* root) {if (root == NULL){return true;}if (root->left && root->left->val != root->val){return false;}if (root->right && root->right->val != root->val){return false;}return isUnivalTree(root->left) && isUnivalTree(root->right);
}
Leetcode—相同的树
bool isSameTree(struct TreeNode* p, struct TreeNode* q) {if (p == NULL && q == NULL){return true;}if (p == NULL || q == NULL){return false;}if (p->val != q->val){return false;}return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}
Leetcode—对称二叉树
bool _isSymmetric(struct TreeNode* p, struct TreeNode* q) {if (p && q){if (p->val != q->val){return false;}return _isSymmetric(p->left, q->right) && _isSymmetric(p->right, q->left);}if (p == q){return true;}return false;
}
bool isSymmetric(struct TreeNode* root) {if (root == NULL){return true;}return _isSymmetric(root->left, root->right);
}
Leetcode—二叉树的前序遍历
int TreeSize(struct TreeNode* root)
{if (root == NULL){return 0;}return TreeSize(root->left) + TreeSize(root->right) + 1;
}
void PreOrder(struct TreeNode* root, int* arr, int* pi)
{if (root == NULL){return;}//每次递归都会建立新的栈帧空间，不同的栈帧空间内相同的变量之间互不影响，//而我们需要的是每次函数递归都要改变下标，所以需要传地址。arr[(*pi)++] = root->val;PreOrder(root->left, arr, pi);PreOrder(root->right, arr, pi);
}
int* preorderTraversal(struct TreeNode* root, int* returnSize) {*returnSize = TreeSize(root);//在开辟空间前可以先算出节点个数以开辟合适的空间int* arr = (int*)malloc(*returnSize * sizeof(int));int i = 0;PreOrder(root, arr, &i);return arr;
}
函数每次递归都会建立独立的栈帧空间，同一个变量在不同的栈帧空间中互不影响，如果我们想让某一变量在每次函数递归都改变，则应该传变量地址。
Leetcode—另一棵树的子树
bool isSameTree(struct TreeNode* p, struct TreeNode* q)
{if (p == NULL && q == NULL){return true;}if (p == NULL || q == NULL){return false;}if (p->val != q->val){return false;}return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}
bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot){if (root == NULL){return false;}if (root->val == subRoot->val && isSameTree(root, subRoot)){return true;}return isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);
}
我们知道二叉树是由根节点和左右子树构成，因此我们可以先判断两个根节点是否相等，如果相等且左右子树也相等则两个二叉树互为子树；如果根节点不相等则递归判断左子树或右子树。
总结
- 二叉树由根节点、左子树和右子树组成，每个子树也是一个二叉树。递归方法很适合处理这种具有递归结构的数据结构，例如通过递归函数不断地遍历左右子树。递归的思想可以帮助我们分解复杂问题，将大问题转化为相同结构的小问题，从而简化解题过程。