devbox
IT小白
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

数据结构 二叉树和堆总结

作者：IT小白 | 2024-08-08 00:06:07

赞

踩

数据结构 二叉树和堆总结

树

概念

树是一种层次结构非线性的数据结构，其是由节点和边组成，可以用来表示层次关系的数据。

树的相关概念

  • 节点：树的基本组成单位，每个节点都包含数据，同时与其他节点相互连接
  • 根节点：树的顶层节点，没有父节点
  • 子节点：由一个节点直接连接的下层节点
  • 父节点：直接连接子节点的上层节点
  • 叶子节点：没有子节点的就是叶子节点
  • 内部节点：至少有一个子节点的节点
  • 兄弟节点：具有同一个父节点的节点
  • 路径：从一个节点到另外一个节点所经过的节点路径
  • 深度：节点到根节点的路径长度
  • 高度：节点到叶子节点的最长路径长度
  • 度：节点的子节点数
  • 子树：由某个节点机器所有后代节点组成的树

二叉树

概念

二叉树是一种特殊的树结构，其每个节点最多有两个子节点，也就是左子节点和右子节点，二叉树可以为空（没有节点，也可以只有一个根节点）。

二叉树性质

重要性质总结

  • 节点数与层数：

    • 二叉树第iii层上最多有 2i−12^{i-1}2i−1 个节点。
    • 深度为 hhh 的二叉树最多有 2h−12^h - 12h−1 个节点。

  • 满二叉树：

    • 深度为 hhh 且有 2h−12^h - 12h−1 个节点的二叉树称为满二叉树。
    • 满二叉树中每一层的节点数都达到最大。

  • 完全二叉树：

    • 深度为 hhh 且有 nnn 个节点的二叉树，当且仅当其每一个节点都与深度为 hhh 的满二叉树中编号为 1 到 nnn 的节点对应时，称其为完全二叉树。
    • 完全二叉树除了最后一层外，每层都是满的，且最后一层的节点从左到右依次排列。

  • 节点的度：

    • 二叉树中度为 0 的节点（即叶节点）的数量为 n0n_0n0​。
    • 度为 2 的节点数量为 n2n_2n2​。
    • 对于一个二叉树，满足关系 n0=n2+1n_0 = n_2 + 1n0​=n2​+1。

  • 二叉树的遍历：

    • 前序遍历（Pre-order Traversal）：先访问根节点，再访问左子树，最后访问右子树。
    • 中序遍历（In-order Traversal）：先访问左子树，再访问根节点，最后访问右子树。
    • 后序遍历（Post-order Traversal）：先访问左子树，再访问右子树，最后访问根节点。
    • 层次遍历（Level-order Traversal）：按层次从上到下，从左到右依次访问各节点。

  • 子树：

    • 每个节点的左子树和右子树也是二叉树。

  • 树的高度：

    • 二叉树的高度是从根节点到叶节点的最长路径的节点数。

  • 平衡二叉树：

    • 一种特殊的二叉树，任何一个节点的左右子树的高度差不超过 1。常见的平衡二叉树包括 AVL 树和红黑树。

二叉树存储结构

链式存储结构：一个节点中有一个表示数据的，以及左右节点指针

  1. #include<iostream>
  2.  
  3. struct TreeNode
  4. {
  5. 	int data;
  6. 	TreeNode* left;
  7. 	TreeNode* right;
  8.  
  9. 	TreeNode(int value):data(value),left(nullptr),right(nullptr){}
  10. };
  11.  
  12. TreeNode* CreateTree()
  13. {
  14. 	TreeNode* root = new TreeNode(1);
  15. 	root->left = new TreeNode(2);
  16. 	root->right = new TreeNode(3);
  17. 	root->left->left = new TreeNode(4);
  18. 	root->left->right = new TreeNode(5);
  19. 	root->right->left = new TreeNode(6);
  20. 	root->right->right = new TreeNode(7);
  21. 	return root;
  22. }
  23.  
  24. void prevOrderTree(TreeNode* root)
  25. {
  26. 	if (root == nullptr) return;
  27. 	std::cout << root->data << " ";
  28. 	prevOrderTree(root->left);
  29. 	prevOrderTree(root->right);
  30. }
  31.  
  32. int main()
  33. {
  34. 	TreeNode* root = CreateTree();
  35. 	prevOrderTree(root);
  36. 	std::cout << std::endl;
  37. 	return 0;
  38. }

顺序存储结构：使用一个数组进行存储，针对于第i个节点，2i位置是左子树，2i+1节点是右子树（基本不用，只适合完全静态的树）

  1. #include <iostream>
  2. #include <vector>
  3. #include <cmath>
  4.  
  5. std::vector<int> createBinaryTreeArray() {
  6.     // 假设二叉树的深度为3
  7.     std::vector<int> tree(8);  // 大小为2^3 = 8，index从0开始
  8.     tree[1] = 1;  // 根节点
  9.     tree[2] = 2;  // 左子节点
  10.     tree[3] = 3;  // 右子节点
  11.     tree[4] = 4;  // 左子节点的左子节点
  12.     tree[5] = 5;  // 左子节点的右子节点
  13.     tree[6] = 6;  // 右子节点的左子节点
  14.     tree[7] = 7;  // 右子节点的右子节点
  15.     return tree;
  16. }
  17.  
  18. void preOrderTraversalArray(const std::vector<int>& tree, int index) {
  19.     if (index >= tree.size() || tree[index] == 0) return;
  20.     std::cout << tree[index] << " ";
  21.     preOrderTraversalArray(tree, 2 * index);     // 左子节点
  22.     preOrderTraversalArray(tree, 2 * index + 1); // 右子节点
  23. }
  24.  
  25. int main() {
  26.     std::vector<int> tree = createBinaryTreeArray();
  27.     std::cout << "Pre-order traversal: ";
  28.     preOrderTraversalArray(tree, 1);  // 从根节点开始遍历
  29.     std::cout << std::endl;
  30.     return 0;
  31. }

前中后序遍历

总结

  • 前序遍历：根--左--右
  • 后序遍历：左--右--根
  • 中序遍历：左--根--右

  1. #include<iostream>
  2.  
  3. struct TreeNode
  4. {
  5. 	int data;
  6. 	TreeNode* left;
  7. 	TreeNode* right;
  8.  
  9. 	TreeNode(int value):data(value),left(nullptr),right(nullptr){}
  10. };
  11.  
  12. TreeNode* CreateTree()
  13. {
  14. 	TreeNode* root = new TreeNode(1);
  15. 	root->left = new TreeNode(2);
  16. 	root->right = new TreeNode(3);
  17. 	root->left->left = new TreeNode(4);
  18. 	root->left->right = new TreeNode(5);
  19. 	root->right->left = new TreeNode(6);
  20. 	root->right->right = new TreeNode(7);
  21. 	return root;
  22. }
  23.  
  24. void prevOrderTree(TreeNode* root)
  25. {
  26. 	if (root == nullptr) return;
  27. 	std::cout << root->data << " ";
  28. 	prevOrderTree(root->left);
  29. 	prevOrderTree(root->right);
  30. }
  31.  
  32. void inOrderTree(TreeNode* root)
  33. {
  34. 	if (root == nullptr) return;
  35. 	inOrderTree(root->left);
  36. 	std::cout << root->data << " ";
  37. 	inOrderTree(root->right);
  38. }
  39.  
  40. void postOrderTree(TreeNode* root)
  41. {
  42. 	if (root == nullptr) return;
  43. 	postOrderTree(root->left);
  44. 	postOrderTree(root->right);
  45. 	std::cout << root->data << " ";
  46. }
  47.  
  48. int main()
  49. {
  50. 	TreeNode* root = CreateTree();
  51. 	std::cout << "前序遍历:";
  52. 	prevOrderTree(root);
  53. 	std::cout << std::endl;
  54.  
  55. 	std::cout << "中序遍历:";
  56. 	inOrderTree(root);
  57. 	std::cout << std::endl;
  58.  
  59. 	std::cout << "后序遍历:";
  60. 	postOrderTree(root);
  61. 	std::cout << std::endl;
  62. 	return 0;
  63. }

 层序遍历

实现方式：借助队列实现

  • 初始化队列，将根节点的数值放入进去
  • 设置循环直到队列为空： 队列中提取并出队，然后分别放入左右的数值进行循环判断

  1. #include<iostream>
  2. #include<queue>
  3.  
  4. struct TreeNode
  5. {
  6. 	int data;
  7. 	TreeNode* left;
  8. 	TreeNode* right;
  9.  
  10. 	TreeNode(int value):data(value),left(nullptr),right(nullptr){}
  11. };
  12.  
  13. TreeNode* CreateTree()
  14. {
  15. 	TreeNode* root = new TreeNode(1);
  16. 	root->left = new TreeNode(2);
  17. 	root->right = new TreeNode(3);
  18. 	root->left->left = new TreeNode(4);
  19. 	root->left->right = new TreeNode(5);
  20. 	root->right->left = new TreeNode(6);
  21. 	root->right->right = new TreeNode(7);
  22. 	return root;
  23. }
  24.  
  25. void levelOrderTree(TreeNode* root)
  26. {
  27. 	if (!root) return;
  28.  
  29. 	std::queue<TreeNode*>q;
  30. 	q.push(root);
  31.  
  32. 	while (!q.empty())
  33. 	{
  34. 		TreeNode* tem = q.front();
  35. 		q.pop();
  36. 		std::cout << tem->data << " ";
  37.  
  38. 		if (tem->left) q.push(tem->left);
  39. 		if (tem->right) q.push(tem->right);
  40. 	}
  41. }
  42.  
  43. int main()
  44. {
  45. 	TreeNode* root = CreateTree();
  46. 	levelOrderTree(root);
  47. 	std::cout << std::endl;
  48. 	return 0;
  49. }

堆

存储方式

  • 通常借助数组来存储
    • 父节点下标：（i -1）/2
    • 左孩子：2i + 1
    • 右孩子：2i + 2

概念

  • 堆是一颗完全二叉树，除了最后一层，所有层都是满的，并且最后一层的节点是从左往右依次排列
  • 堆主要有两种表现形式
    • 大堆：每个节点的值都大于等于其子节点的值
    • 小堆：每个节点的值都小于等于其节点的值

向上调整与向下调整

向上调整

  • 插入新元素时，将新元素放入到堆的末尾
  • 从新插入元素的下标（堆的末尾），检查父节点是否比自己大或者小（根据大小堆来决定，大堆的话则是当前元素比父元素大就交换）
  • 如果大于或者小于父节点，则交换两个节点，然后当前下标更新成为父元素的下标，继续检查
  • 重复此过程，直到当前元素不大于父元素，或者已经到达栈顶
  • 事例代码（建大堆）
  • 场景：当插入新元素的时候使用向上调整，因为新元素是插入到数组尾部
  1. 	//向上调整
  2. 	void AdjuestUp(int index)
  3. 	{
  4. 		while (index > 0 && heap[index] > heap[(index - 1) / 2])
  5. 		{
  6. 			std::swap(heap[index], heap[(index - 1) / 2]);
  7. 			index = (index - 1) / 2;
  8. 		}
  9. 	}

 向下调整

  • 从堆中删除第一个元素（大堆就是删除最大元素，小堆则是最小）下面叙述按照大堆逻辑。将堆的最后一个元素移动到堆顶
  • 从堆顶开始，找到当前节点、左孩子、右孩子三个节点的最大值
  • 如果当前节点不是最大值，则将其与最大值节点交换，并更新当前索引为最大子节点索引，继续检查
  • 重复上述过程，直到当前节点大于或者等于其子节点，或者已经到达堆的底部
  • 使用场景：删除元素的时候
  • 代码事例，大堆的向下调整
  1. //改写法适合排序堆排使用
  2.  
  3. void AdjustDown(vector<int>& arr, int n, int i)
  4. {
  5. 	int largest = i;
  6. 	int left = 2 * i + 1, right = 2 * i + 2;
  7.  
  8. 	if (left<n && arr[left]>arr[largest]) largest = left;
  9. 	if (right<n && arr[right]>arr[largest]) largest = right;
  10. 	
  11. 	if (largest != i)
  12. 	{
  13. 		swap(arr[i], arr[largest]);
  14. 		AdjustDown(arr, n, largest);
  15. 	}
  16. }
  1. 	//向下调整
  2. 	void AdjuestDown(int index)
  3. 	{
  4. 		int size = heap.size();
  5. 		while (index * 2 + 1 < size)
  6. 		{
  7. 			int largest = index;
  8. 			int leftChild = index * 2 + 1;
  9. 			int rightChild = index * 2 + 2;
  10.  
  11. 			//找到是三个节点的最大值
  12. 			if (leftChild < size && heap[leftChild]>heap[largest])
  13. 			{
  14. 				largest = leftChild;
  15. 			}
  16. 			if (rightChild<size && heap[rightChild]>heap[largest])
  17. 			{
  18. 				largest = rightChild;
  19. 			}
  20.  
  21. 			//如果最大节点不是当前节点，则交换最大值，然后继续向下调整
  22. 			if (largest != index)
  23. 			{
  24. 				std::swap(heap[index], heap[largest]);
  25. 				index = largest;
  26. 			}
  27. 			else
  28. 			{
  29. 				break;
  30. 			}
  31. 		}
  32. 	}

时间复杂度分析

堆操作相关时间复杂度分析

  • 插入操作（Insert）

    • 时间复杂度：O(log n)
    • 插入一个新元素时，首先将其添加到堆的末尾，然后通过向上调整（heapify up）使堆恢复最大堆或最小堆的性质。向上调整的过程最多需要经过堆的高度层，而堆的高度是 O(logn)O(log n)O(logn)。

  • 删除堆顶元素（Extract Max / Extract Min）

    • 时间复杂度：O(log n)
    • 删除堆顶元素（即最大堆中的最大元素或最小堆中的最小元素）时，将堆的最后一个元素移动到堆顶，然后通过向下调整（heapify down）使堆恢复堆的性质。向下调整的过程最多需要经过堆的高度层，时间复杂度也是 O(logn)O(log n)O(logn)。

  • 获取堆顶元素（Get Max / Get Min）

    • 时间复杂度：O(1)
    • 获取堆顶元素不需要进行任何调整操作，只需要返回堆数组的第一个元素即可，因此时间复杂度是 O(1)O(1)O(1)。

  • 建堆操作（Build Heap）

    • 时间复杂度：O(n)
    • 从一个无序数组构建一个堆可以通过自底向上的方法进行，即从最后一个非叶子节点开始向下调整（heapify down）。这种方法的总时间复杂度是 O(n)O(n)O(n)，而不是 O(nlog⁡n)O(n \log n)O(nlogn)，因为每个节点向下调整的平均次数比堆的高度要少。

  • 堆排序（Heap Sort）

    • 时间复杂度：O(n \log n)
    • 堆排序包括两个主要步骤：首先将无序数组构建成一个堆（时间复杂度 O(n)O(n)O(n)），然后重复地提取堆顶元素并调整堆（每次提取和调整的时间复杂度是 O(logn)O(log n)O(logn)）。因此，总的时间复杂度是 O(n)+O(nlog⁡n)=O(nlog⁡n)O(n) + O(n \log n) = O(n \log n)O(n)+O(nlogn)=O(nlogn)。

堆排序

思路总结（以大堆为例分析）

  • 构建大堆，将数组转化成为堆
  • 交换堆顶元素与末尾元素，同时缩小堆的范围，对堆顶元素进行向下调整，直到数组排序完成

 

  1. #include<iostream>
  2. #include<vector>
  3. #include<algorithm>
  4.  
  5. using namespace std;
  6.  
  7. void AdjustDown(vector<int>& arr, int n, int i)
  8. {
  9. 	int largest = i;
  10. 	int left = 2 * i + 1, right = 2 * i + 2;
  11.  
  12. 	if (left<n && arr[left]>arr[largest]) largest = left;
  13. 	if (right<n && arr[right]>arr[largest]) largest = right;
  14. 	
  15. 	if (largest != i)
  16. 	{
  17. 		swap(arr[i], arr[largest]);
  18. 		AdjustDown(arr, n, largest);
  19. 	}
  20. }
  21.  
  22. void heapSort(vector<int>& arr)
  23. {
  24. 	int n = arr.size();
  25.  
  26. 	//构建大堆（找父节点然后调整）
  27. 	for (int i = n / 2 - 1; i >= 0; i--)
  28. 	{
  29. 		AdjustDown(arr, n, i);
  30. 	}
  31.  
  32. 	//交换头尾元素，然后再次向下调整
  33. 	for (int i = n - 1; i > 0; i--)
  34. 	{
  35. 		swap(arr[0], arr[i]);
  36. 		AdjustDown(arr, i, 0);
  37. 	}
  38. }
  39.  
  40. int main()
  41. {
  42. 	std::vector<int> arr{ 12,89,5,4,66,82,56,99,1 };
  43. 	cout << "begin arr:";
  44. 	for (auto& ch : arr) {
  45. 		cout << ch << " ";
  46. 	}
  47. 	cout << endl;
  48.  
  49. 	heapSort(arr);
  50. 	cout << "after sort :";
  51. 	for (auto& ch : arr)
  52. 	{
  53. 		cout << ch << " ";
  54. 	}
  55. }

堆的简单实现

插入与删除实现

  • 插入：末尾插入新元素，然后向上调整
  • 删除：删除头部元素，尾部元素填充头部元素，然后向下调整
  • 下述代码（插入、删除、向上调整、向下调整整体实现）
  1. #include<iostream>
  2. #include<vector>
  3. #include<algorithm>
  4.  
  5. class MaxHeap
  6. {
  7. private:
  8. 	std::vector<int> heap;
  9.  
  10. 	//向上调整
  11. 	void AdjuestUp(int index)
  12. 	{
  13. 		while (index > 0 && heap[index] > heap[(index - 1) / 2])
  14. 		{
  15. 			std::swap(heap[index], heap[(index - 1) / 2]);
  16. 			index = (index - 1) / 2;
  17. 		}
  18. 	}
  19.  
  20. 	//向下调整
  21. 	void AdjuestDown(int index)
  22. 	{
  23. 		int size = heap.size();
  24. 		while (index * 2 + 1 < size)
  25. 		{
  26. 			int largest = index;
  27. 			int leftChild = index * 2 + 1;
  28. 			int rightChild = index * 2 + 2;
  29.  
  30. 			//找到是三个节点的最大值
  31. 			if (leftChild < size && heap[leftChild]>heap[largest])
  32. 			{
  33. 				largest = leftChild;
  34. 			}
  35. 			if (rightChild<size && heap[rightChild]>heap[largest])
  36. 			{
  37. 				largest = rightChild;
  38. 			}
  39.  
  40. 			//如果最大节点不是当前节点，则交换最大值，然后继续向下调整
  41. 			if (largest != index)
  42. 			{
  43. 				std::swap(heap[index], heap[largest]);
  44. 				index = largest;
  45. 			}
  46. 			else
  47. 			{
  48. 				break;
  49. 			}
  50. 		}
  51. 	}

TopK问题

实现思路总结

  • 问题回顾：TopK就是从一组数据中找出前K大或者前K小的元素
  • 思路（通过小根堆解决）
    • 维护一个大小为K的小根堆
    • 遍历全部的数据，将每个元素与栈顶元素（也就是最小值）比较
      • 如果当前元素大于栈顶元素，则替换掉栈顶元素，然后重新调整堆
      • 否则的话就继续遍历下一个元素
  • 事例（前K大的元素，因为小根堆的首元素永远都是最小的元素）

  1. #include<iostream>
  2. #include<queue>
  3. #include<vector>
  4.  
  5. using namespace std;
  6.  
  7. vector<int> topKElements(vector<int>& data, int k)
  8. {
  9.     if (k <= 0) return {};
  10.     //利用比较器实现小堆
  11.     priority_queue<int, vector<int>, greater<int>> minheap;
  12.  
  13.     //遍历data中的全部属于，没添加满就继续添加，添加满了就比较堆顶元素
  14.     for (int num : data)
  15.     {
  16.         if (minheap.size() < k)
  17.         {
  18.             minheap.push(num);
  19.         }
  20.         else if (num > minheap.top())
  21.         {
  22.             minheap.pop();
  23.             minheap.push(num);
  24.         }
  25.     }
  26.  
  27.     vector<int>ret;
  28.     while (!minheap.empty())
  29.     {
  30.         ret.push_back(minheap.top());
  31.         minheap.pop();
  32.     }
  33.     return ret;
  34. }
  35.  
  36. int main() {
  37.     vector<int> data = { 3, 1, 5, 12, 2, 11, 10, 7, 6 };
  38.     int k = 3;
  39.     vector<int> result = topKElements(data, k);
  40.  
  41.     cout << "Top " << k << " elements: ";
  42.     for (int num : result) {
  43.         cout << num << " ";
  44.     }
  45.     cout << endl;
  46.  
  47.     return 0;
  48. }

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/IT小白/article/detail/945103
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号