当前位置： 首页 > news >正文

堆与二叉树（下）

news 来源：原创 2024/5/20 4:13:21

接着上次的，这里主要介绍的是堆排序，二叉树的遍历，以及之前讲题时答应过的简单二叉树问题求解

堆排序

给一组数据，升序（降序）排列

思路

思考：如果排列升序，我们应该建什么堆？

首先，如果排升序，数列最后一个数是 最大数，我们的思路是通过 向上调整 或者 向下调整，数组存放的第一个数不是最小值（小堆）就是最大值（大堆），此时我们将最后一个数与第一个数交换，使得最大值放在最后，此时再使用向上调整 或者 向下调整，得到第二大的数，重复上述动作，很明显，我们需要的第一个数是最大值，因此我们需要建大堆

反之，排降序，建立小堆

代码

#include<stdio.h>
void downAdjust(int* pa, int parent, int n)
{int child = parent * 2 + 1;while (child < n){if (child + 1 < n && pa[child] > pa[child + 1]){child++;}if (pa[parent] > pa[child]){swap(&pa[parent], &pa[child]);}else{break;}parent = child;child = parent * 2 + 1;}
}
int main()
{int arr[] = { 1,3,2,5,7,4,7,4,2,5,6,8};int n = sizeof(arr) / sizeof(arr[0]);for (int i = (n - 1 - 1) / 2; i >= 0; i--){downAdjust(arr, i, n);}for (int i = n; i > 0; ){swap(&arr[0], &arr[i - 1]);downAdjust(arr, 0, --i);}for (int i = 0; i < n; i++){printf("%d ", arr[i]);}return 0;
}

topK算法

在一组数据中，选出k个最大（最小）的数

思路

如果我们选择k个最大的数，假设数组的前k个数就是最大的数，这 k个数建立 小堆，带一个数与 后面的从第 k + 1个数开始，进行比较，如果比第一个数的就换下来，然后向下调整，直到每个所有数都比较完了

代码

void downAdjust(int* pa, int parent, int n)
{int child = parent * 2 + 1;while (child < n){if (child + 1 < n && pa[child] > pa[child + 1]){child++;}if (pa[parent] > pa[child]){swap(&pa[parent], &pa[child]);}else{break;}parent = child;child = parent * 2 + 1;}
}
#include<stdio.h>
int main()
{int arr[] = { 1,6,10,3,5,8,46,23,6,25,3,40 };int n = sizeof(arr) / sizeof(arr[0]);int k = 0;scanf("%d", &k);for (int i = (k - 1 - 1) / 2; i >= 0; i--){downAdjust(arr, i, n);}for (int i = k; i < n; i++){if (arr[i] > arr[0]){swap(&arr[i], &arr[0]);downAdjust(arr, 0, k);}}for (int i = 0; i < k; i++){printf("%d ", arr[i]);}return 0;
}

五. 二叉树的实现

1. 链接结构搭建二叉树

代码

typedef int TLType;
typedef struct TreeList
{TLType val;struct TreeList* left;struct TreeList* right;
}TL;
TL *creatnode(TLType x)
{TL*pa = (TL*)malloc(sizeof(TL));if (pa == NULL){perror("malloc");return;}TL* newnode = pa;newnode->left = newnode->right = NULL;newnode->val = x;return newnode;
}
TL* CreatTree()
{TL* tree1 = creatnode(1);TL *tree2 = creatnode(2);TL* tree3 = creatnode(3);TL* tree4 = creatnode(3);tree1->left = tree2;tree1->right = tree3;tree2->left = tree4;return tree1;
}
#include<stdio.h>
int main()
{TL* p = NULL;p = CreatTree();
}

我们搭建了一个这样的树结构：

2. 二叉树的遍历

二叉树的遍历可以分三种：前序，中序，后序，层序

a. 前序遍历：（根，左子树，右子树）

举例

这棵树的前序遍历是怎样的？（包括空树，用N表示）

val1 val2 val4 N N val5 N N val3 val6 N N val7 N N

代码实现 

#include<stdio.h>
#include<stdlib.h>
typedef int TLType;
typedef struct TreeList
{TLType val;struct TreeList* left;struct TreeList* right;
}TL;
TL *creatnode(TLType x)
{TL*pa = (TL*)malloc(sizeof(TL));if (pa == NULL){perror("malloc");return;}TL* newnode = pa;newnode->left = newnode->right = NULL;newnode->val = x;return newnode;
}
TL* CreatTree()
{TL* tree1 = creatnode(1);TL *tree2 = creatnode(2);TL* tree3 = creatnode(3);TL* tree4 = creatnode(4);TL* tree5 = creatnode(5);TL* tree6 = creatnode(6);TL* tree7 = creatnode(7);tree1->left = tree2;tree1->right = tree3;tree2->left = tree4;tree2->right = tree5;tree3->left = tree6;tree3->right = tree7;return tree1;
}
#include<stdio.h>
void PrevOrder(TL *root)
{if (root == NULL){printf("N ");return;}printf("%d ", root->val);PrevOrder(root->left);PrevOrder(root->right);
}
int main()
{TL* p = NULL;p = CreatTree();PrevOrder(p);
}

运行结果：

b. 中序遍历：（左子树，根，右子树）

举例

这棵树的中序遍历是怎样的？（包括空树，用N表示）

N val4 N val2 N val5 N val1 N val6 N val3 N val7 N

 代码实现

#include<stdio.h>
#include<stdlib.h>
typedef int TLType;
typedef struct TreeList
{TLType val;struct TreeList* left;struct TreeList* right;
}TL;
TL *creatnode(TLType x)
{TL*pa = (TL*)malloc(sizeof(TL));if (pa == NULL){perror("malloc");return;}TL* newnode = pa;newnode->left = newnode->right = NULL;newnode->val = x;return newnode;
}
TL* CreatTree()
{TL* tree1 = creatnode(1);TL *tree2 = creatnode(2);TL* tree3 = creatnode(3);TL* tree4 = creatnode(4);TL* tree5 = creatnode(5);TL* tree6 = creatnode(6);TL* tree7 = creatnode(7);tree1->left = tree2;tree1->right = tree3;tree2->left = tree4;tree2->right = tree5;tree3->left = tree6;tree3->right = tree7;return tree1;
}
#include<stdio.h>
void InOder(TL* root)
{if (root == NULL){printf("N ");return;}InOder(root->left);printf("%d ", root->val);InOder(root->right);
}
int main()
{TL* p = NULL;p = CreatTree();InOder(p);
}

运行结果：

c. 后序遍历：（左子树，右子树，根）

举例

这棵树的后序遍历是怎样的？（包括空树，用N表示）

N N val4 N N val5 val2 N N val6 N N val7 val3 val1

代码实现 

#include<stdio.h>
#include<stdlib.h>
typedef int TLType;
typedef struct TreeList
{TLType val;struct TreeList* left;struct TreeList* right;
}TL;
TL* creatnode(TLType x)
{TL* pa = (TL*)malloc(sizeof(TL));if (pa == NULL){perror("malloc");return;}TL* newnode = pa;newnode->left = newnode->right = NULL;newnode->val = x;return newnode;
}
TL* CreatTree()
{TL* tree1 = creatnode(1);TL* tree2 = creatnode(2);TL* tree3 = creatnode(3);TL* tree4 = creatnode(4);TL* tree5 = creatnode(5);TL* tree6 = creatnode(6);TL* tree7 = creatnode(7);tree1->left = tree2;tree1->right = tree3;tree2->left = tree4;tree2->right = tree5;tree3->left = tree6;tree3->right = tree7;return tree1;
}
void PostOder(TL* root)
{if (root == NULL){printf("N ");return;}PostOder(root->left);PostOder(root->right);printf("%d ", root->val);
}
int main()
{TL* p = NULL;p = CreatTree();PostOder(p);
}

运行结果：

d. 层序遍历

一排排的遍历

画图举例

实现思路 

这里我们借助队列（可以先进先出），开辟的数组里面存放根节点的地址（通过地址可以找到左右子树，否则如果存值是没有办法找到左右子树），打印完根节点的值，就释放，存入左右子树的节点

代码实现

实现的二叉树是这样的：

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int TLType;
typedef struct TreeList
{TLType val;struct TreeList* left;struct TreeList* right;
}TL;
TL* creatnode(TLType x)
{TL* pa = (TL*)malloc(sizeof(TL));if (pa == NULL){perror("malloc");return;}TL* newnode = pa;newnode->left = newnode->right = NULL;newnode->val = x;return newnode;
}
TL* CreatTree()
{TL* tree1 = creatnode(1);TL* tree2 = creatnode(2);TL* tree3 = creatnode(3);TL* tree4 = creatnode(4);TL* tree5 = creatnode(5);TL* tree6 = creatnode(6);TL* tree7 = creatnode(7);tree1->left = tree2;tree1->right = tree3;tree2->left = tree4;tree2->right = tree5;tree3->left = tree6;tree3->right = tree7;return tree1;
}
typedef struct QueueNode
{struct QueueNode* next;TL* data;
}QNode;typedef struct Queue
{QNode* head;QNode* tail;int size;
}Que;void QueueInit(Que* pq)
{assert(pq);pq->head = pq->tail = NULL;pq->size = 0;
}void QueueDestroy(Que* pq)
{assert(pq);QNode* cur = pq->head;while (cur){QNode* next = cur->next;free(cur);cur = next;}pq->head = pq->tail = NULL;pq->size = 0;
}void QueuePush(Que* pq, TL* x)
{assert(pq);QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){perror("malloc fail");exit(-1);}newnode->data = x;newnode->next = NULL;if (pq->tail == NULL){pq->head = pq->tail = newnode;}else{pq->tail->next = newnode;pq->tail = newnode;}pq->size++;
}bool QueueEmpty(Que* pq)
{assert(pq);return pq->head == NULL;
}
void QueuePop(Que* pq)
{assert(pq);assert(!QueueEmpty(pq));if (pq->head->next == NULL){free(pq->head);pq->head = pq->tail = NULL;}else{QNode* next = pq->head->next;free(pq->head);pq->head = next;}pq->size--;
}TL* QueueFront(Que* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->head->data;
}int QueueSize(Que* pq)
{assert(pq);return pq->size;
}
void leverOrder(TL* root, Que* pq)
{QueuePush(pq, root);while (!QueueEmpty(pq)){TL* pa = QueueFront(pq);printf("%d ", pa->val);QueuePop(pq);if (pa->left != NULL){QueuePush(pq, pa->left);}if (pa->right != NULL){QueuePush(pq, pa->right);}}}
int main()
{TL* p = NULL;p = CreatTree();Que q;QueueInit(&q);leverOrder(p, &q);return 0;
}

运行结果：

3. 简单二叉树经典问题求解

a. 求二叉树的节点个数

思路

想要求二叉树的节点可以分成 根节点 + 左子树 + 右子树

这里的遍历类似 前序遍历

代码

实现的树是这样的：

#include<stdio.h>
#include<stdlib.h>
typedef int TLType;
typedef struct TreeList
{TLType val;struct TreeList* left;struct TreeList* right;
}TL;
TL* creatnode(TLType x)
{TL* pa = (TL*)malloc(sizeof(TL));if (pa == NULL){perror("malloc");return;}TL* newnode = pa;newnode->left = newnode->right = NULL;newnode->val = x;return newnode;
}
TL* CreatTree()
{TL* tree1 = creatnode(1);TL* tree2 = creatnode(2);TL* tree3 = creatnode(3);TL* tree4 = creatnode(4);TL* tree5 = creatnode(5);TL* tree6 = creatnode(6);TL* tree7 = creatnode(7);tree1->left = tree2;tree1->right = tree3;tree2->left = tree4;tree2->right = tree5;tree3->left = tree6;tree3->right = tree7;return tree1;
}
int TreeSize(TL* root)
{if (root == NULL){return 0;}return 1 + TreeSize(root->left) + TreeSize(root->right);
}
int main()
{TL* p = NULL;p = CreatTree();int size = TreeSize(p);printf("%d ", size);return 0;
}

b. 求树的高度

思路

求二叉树的高度，我们需要找到到那个最长的路径，这里采用分治的思想，如果为空树，返回 0 （空树高度为 0），调用左子树和右子树都会 + 1（+ 1可以理解成加上节点的高度），对比左子树和右子树，返回高度最大的那个

注：每求一次左右节点个数时，一定要保存，否则会有很大的时间浪费

代码

#include<stdio.h>
#include<stdlib.h>
typedef int TLType;
typedef struct TreeList
{TLType val;struct TreeList* left;struct TreeList* right;
}TL;
TL* creatnode(TLType x)
{TL* pa = (TL*)malloc(sizeof(TL));if (pa == NULL){perror("malloc");return;}TL* newnode = pa;newnode->left = newnode->right = NULL;newnode->val = x;return newnode;
}
TL* CreatTree()
{TL* tree1 = creatnode(1);TL* tree2 = creatnode(2);TL* tree3 = creatnode(3);TL* tree4 = creatnode(4);TL* tree5 = creatnode(5);TL* tree6 = creatnode(6);TL* tree7 = creatnode(7);TL* tree8 = creatnode(8);tree1->left = tree2;tree1->right = tree3;tree2->left = tree4;tree2->right = tree5;tree3->left = tree6;tree3->right = tree7;tree4->left = tree8;return tree1;
}
int TreeHigh(TL* root)
{if (root == NULL){return 0;}int Left = 1 + TreeHigh(root->left);int Right = 1 +  TreeHigh(root->right) ;return Left > Right ? Left : Right;
}
int main()
{TL* p = NULL;p = CreatTree();int high = TreeHigh(p);printf("%d ", high);return 0;
}

c. 求根节点的个数

思路

判断是否是根节点的方法就是判断它的左右子树是否是 空树，我们只需要遍历这棵树就行，但如果遍历时，根节点遇到空树这也是一种结束条件

代码

#include<stdio.h>
#include<stdlib.h>
typedef int TLType;
typedef struct TreeList
{TLType val;struct TreeList* left;struct TreeList* right;
}TL;
TL* creatnode(TLType x)
{TL* pa = (TL*)malloc(sizeof(TL));if (pa == NULL){perror("malloc");return;}TL* newnode = pa;newnode->left = newnode->right = NULL;newnode->val = x;return newnode;
}
TL* CreatTree()
{TL* tree1 = creatnode(1);TL* tree2 = creatnode(2);TL* tree3 = creatnode(3);TL* tree4 = creatnode(4);TL* tree5 = creatnode(5);TL* tree6 = creatnode(6);TL* tree7 = creatnode(7);TL* tree8 = creatnode(8);tree1->left = tree2;tree1->right = tree3;tree2->left = tree4;tree2->right = tree5;tree3->left = tree6;tree3->right = tree7;tree4->left = tree8;return tree1;
}
int RootSize(TL* root)
{if (root == NULL){return 0;}if (root->left == NULL && root->right == NULL){return 1;}return RootSize(root->left) + RootSize(root->right);
}
int main()
{TL* p = NULL;p = CreatTree();int root = RootSize(p);printf("%d ", root);return 0;
}

d. 求倒数第k排节点的个数

思路

这个可以是求树的高度的变形，将计数倒过来

代码 

#include<stdio.h>
#include<stdlib.h>
typedef int TLType;
typedef struct TreeList
{TLType val;struct TreeList* left;struct TreeList* right;
}TL;
TL* creatnode(TLType x)
{TL* pa = (TL*)malloc(sizeof(TL));if (pa == NULL){perror("malloc");return;}TL* newnode = pa;newnode->left = newnode->right = NULL;newnode->val = x;return newnode;
}
TL* CreatTree()
{TL* tree1 = creatnode(1);TL* tree2 = creatnode(2);TL* tree3 = creatnode(3);TL* tree4 = creatnode(4);TL* tree5 = creatnode(5);TL* tree6 = creatnode(6);TL* tree7 = creatnode(7);TL* tree8 = creatnode(8);tree1->left = tree2;tree1->right = tree3;tree2->left = tree4;tree2->right = tree5;tree3->left = tree6;tree3->right = tree7;tree4->left = tree8;return tree1;
}int TreeHigh(TL* root)
{if (root == NULL){return 0;}int Left = 1 + TreeHigh(root->left);int Right = 1 +  TreeHigh(root->right) ;return Left > Right ? Left : Right;
}
int RootKsize(TL* root,int n,int k)
{if (root == NULL){return 0;}if (n == k){return 1;}return RootKsize(root->left, n - 1, k) + RootKsize(root->right, n - 1, k);
}
int main()
{int k = 0;scanf("%d", &k);TL* p = NULL;p = CreatTree();int high = TreeHigh(p);int rootk = RootKsize(p, high, k);printf("%d ", rootk);return 0;
}

e. 判断是否是相同的树

思路

采用前序，先比较根节点是否相同，再比较左右子树是否相同

代码

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
typedef int TLType;
typedef struct TreeList
{TLType val;struct TreeList* left;struct TreeList* right;
}TL;
TL* creatnode(TLType x)
{TL* pa = (TL*)malloc(sizeof(TL));if (pa == NULL){perror("malloc");return;}TL* newnode = pa;newnode->left = newnode->right = NULL;newnode->val = x;return newnode;
}
TL* CreatTree1()
{TL* tree1 = creatnode(1);TL* tree2 = creatnode(2);TL* tree3 = creatnode(3);TL* tree4 = creatnode(4);TL* tree5 = creatnode(5);TL* tree6 = creatnode(6);TL* tree7 = creatnode(7);TL* tree8 = creatnode(8);tree1->left = tree2;tree1->right = tree3;tree2->left = tree4;tree2->right = tree5;tree3->left = tree6;tree3->right = tree7;tree4->left = tree8;return tree1;
}
TL* CreatTree2()
{TL* tree1 = creatnode(1);TL* tree2 = creatnode(2);TL* tree3 = creatnode(3);TL* tree4 = creatnode(4);TL* tree5 = creatnode(5);TL* tree6 = creatnode(6);TL* tree7 = creatnode(7);tree1->left = tree2;tree1->right = tree3;tree2->left = tree4;tree2->right = tree5;tree3->left = tree6;tree3->right = tree7;return tree1;
}
bool IsSameTree(TL* root1,TL* root2)
{if (root1 == NULL && root2 == NULL){return true;}if (root1 == NULL || root2 == NULL){return false;}if (root1->val != root2->val){return false;}return IsSameTree(root1->left, root2->left) && IsSameTree(root1->right, root2->right);
}
int main()
{TL* p = NULL;p = CreatTree1();TL* q = CreatTree2();printf("%d ", IsSameTree(p, q));return 0;
}

f. 找到某个值，返回节点的地址

思路

前序遍历完数组，如果对比左右子树，判断是否找到节点的地址

代码

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
typedef int TLType;
typedef struct TreeList
{TLType val;struct TreeList* left;struct TreeList* right;
}TL;
TL* creatnode(TLType x)
{TL* pa = (TL*)malloc(sizeof(TL));if (pa == NULL){perror("malloc");return;}TL* newnode = pa;newnode->left = newnode->right = NULL;newnode->val = x;return newnode;
}
TL* CreatTree()
{TL* tree1 = creatnode(1);TL* tree2 = creatnode(2);TL* tree3 = creatnode(2);TL* tree4 = creatnode(4);TL* tree5 = creatnode(5);TL* tree6 = creatnode(6);TL* tree7 = creatnode(7);TL* tree8 = creatnode(8);tree1->left = tree2;tree1->right = tree3;tree2->left = tree4;tree2->right = tree5;tree3->left = tree6;tree3->right = tree7;tree4->left = tree8;return tree1;
}
TL* FindRoot(TL* root,int m)
{if (root == NULL){return NULL;}if (root->val == m){return root;}TL* Left = FindRoot(root->left, m);TL* Right = FindRoot(root->right, m);if (Left == NULL && Right == NULL){return NULL;}if (Left == NULL && Right != NULL){return Right;}else {return Left;}}
int main()
{TL* p = NULL;p = CreatTree();int m = 0;scanf("%d", &m);TL *root = FindRoot(p,m);if (root == NULL){printf("找不到\n");}else{printf("%d ", root->val);}return 0;
}

相关文章：

  • 深度学习 | 基础卷积神经网络
  • 智能优化算法应用：基于蛇优化算法3D无线传感器网络(WSN)覆盖优化 - 附代码
  • C语言沉浸式刷题【C语言必刷题】
  • rk3588 之启动
  • 初识QT（上篇）：What Qt
  • 【顶级快刊】IEEE(Trans)，审稿快仅2个月录用，入选CCF-B，现在投最快！
  • ZKP Mathematical Building Blocks (2)
  • Spring MVC 方法中添加参数、HttpServletRequest 和 HttpServletResponse 对象
  • Netty-4-网络编程模式
  • 【clickhouse】在CentOS中离线安装clickhouse
  • 代码随想录算法训练营 | day60 单调栈 84.柱状图中最大的矩形
  • 每日一题(LeetCode)----栈和队列--滑动窗口最大值
  • centos 安装 Miniconda
  • Python爬虫山东重庆各地区天气预报
  • 深度学习（七）：bert理解之输入形式
  • IE9 : DOM Exception: INVALID_CHARACTER_ERR (5)
  • Android 架构优化~MVP 架构改造
  • CSS中外联样式表代表的含义
  • Date型的使用
  • ECMAScript 6 学习之路 （ 四 ） String 字符串扩展
  • java B2B2C 源码多租户电子商城系统-Kafka基本使用介绍
  • JavaScript设计模式与开发实践系列之策略模式
  • Laravel 实践之路: 数据库迁移与数据填充
  • LeetCode刷题——29. Divide Two Integers（Part 1靠自己）
  • nodejs调试方法
  • python 学习笔记 - Queue Pipes，进程间通讯
  • 技术攻略】php设计模式(一)：简介及创建型模式
  • 那些年我们用过的显示性能指标
  • 如何用Ubuntu和Xen来设置Kubernetes？
  • 使用common-codec进行md5加密
  • 在GitHub多个账号上使用不同的SSH的配置方法
  • 在Mac OS X上安装 Ruby运行环境
  • 【干货分享】dos命令大全
  • python最赚钱的4个方向，你最心动的是哪个？
  • #、%和$符号在OGNL表达式中经常出现
  • （6）设计一个TimeMap
  • （第9篇）大数据的的超级应用——数据挖掘-推荐系统
  • （二）Pytorch快速搭建神经网络模型实现气温预测回归(代码+详细注解)
  • （七）Java对象在Hibernate持久化层的状态
  • （企业 / 公司项目）前端使用pingyin-pro将汉字转成拼音
  • （四）c52学习之旅-流水LED灯
  • （一）80c52学习之旅-起始篇
  • (转)Android学习系列(31)--App自动化之使用Ant编译项目多渠道打包
  • (转)MVC3 类型“System.Web.Mvc.ModelClientValidationRule”同时存在
  • (轉貼)《OOD启思录》：61条面向对象设计的经验原则 (OO)
  • .bat批处理（一）：@echo off
  • .cn根服务器被攻击之后
  • .Net Core webapi RestFul 统一接口数据返回格式
  • .netcore 如何获取系统中所有session_如何把百度推广中获取的线索（基木鱼，电话，百度商桥等）同步到企业微信或者企业CRM等企业营销系统中...
  • .NET企业级应用架构设计系列之技术选型
  • ?php echo ?,?php echo Hello world!;?
  • [ 转载 ] SharePoint 资料
  • [3D游戏开发实践] Cocos Cyberpunk 源码解读-高中低端机性能适配策略
  • [c]统计数字
  • [c++] 自写 MyString 类