C数据结构：二叉树

news/2024/9/24 5:33:20/

目录

二叉树的数据结构

前序遍历

中序遍历

后序遍历

二叉树的创建

二叉树的销毁

二叉树的节点个数

二叉树叶子节点个数

二叉树第K层节点个数

二叉树的查找

层序遍历

判断二叉树是否为完全二叉树

完整代码

二叉树的数据结构

typedef char BTDataType;
typedef struct BinaryTreeNode
{BTDataType _data;struct BinaryTreeNode* _left;struct BinaryTreeNode* _right;
}BTNode;

这里二叉树是使用了链式存储

data负责存储数据，left指针负责存储左孩子节点，right负责存储右孩子节点

前序遍历

void BinaryTreePrevOrder(BTNode* root)
{if (root == NULL){printf("N ");return;}printf("%d ", root->_data);BinaryTreePrevOrder(root->_left);BinaryTreePrevOrder(root->_right);
}

前序遍历的规则是先访问根节点，然后访问左子树，最后访问右子树

根据规则我们在遍历前先打印当前根节点的值（若是遇到NULL则打印N代替空节点），然后再往下递归左子树、右子树即可 

中序遍历

void BinaryTreeInOrder(BTNode* root)
{if (root == NULL){printf("N ");return;}BinaryTreeInOrder(root->_left);printf("%d ", root->_data);BinaryTreeInOrder(root->_right);
}

中序遍历的规则是先访问左子树，然后访问根节点，最后访问右子树

 所以这里先递归到左子树（最左边），然后打印当前节点的值，然后再访问右子树（右子树的左子树），打印值，循环往复

后序遍历

void BinaryTreePostOrder(BTNode* root)
{if (root == NULL){printf("N ");return;}BinaryTreePostOrder(root->_left);BinaryTreePostOrder(root->_right);printf("%d ", root->_data);
}

 后序遍历的规则是先访问左子树，然后访问右子树，最后访问根节点

跟前面的前序遍历和中序遍历基本一致，都只是顺序不一样

二叉树的创建

BTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi)
{if (*pi >= n){(*pi)++;return NULL;}BTNode* root = (BTNode*)malloc(sizeof(BTNode));root->_data = a[(*pi)++];root->_left = BinaryTreeCreate(a, n, pi);root->_right = BinaryTreeCreate(a, n, pi);return root;
}

使用该函数需要传一个数组，并根据数组里的元素当作前序遍历构建起二叉树

并需要传一个数组的大小，和一个标记pi，在外面传参的时候从数组开始的下标开始传

这里为了让函数在递归过程中能够始终有一个变量能够指向数组的某个元素来迭代（遍历数组），不受递归变化而变化，所以需要一个指针变量，在下一次递归的时候只需要传地址，就能获得*pi的值，而不是通过传参

 在每次递归过程中需要先创建一个根节点root并开辟一块空间，并为该节点data赋值为当前走到的*pi的位置

接下来就要开始递归先从根的左子树开始到右子树，并分别赋值给root的左和右

这里的递归会一直递归，我们需要让他递归到空为止，所以需要设定if语句限定递归次数

if语句限定了当*pi超过了数组的长度或等于数组长度时，则不能继续递归获取空间

所以这里是从最后一个节点开始往回返，先return最后一个节点给上一个递归的左或者右节点，依次往复即可

二叉树的销毁

void BinaryTreeDestory(BTNode* root)
{if (root == NULL)return;BinaryTreeDestory(root);BinaryTreeDestory(root);free(root);
}

销毁我们需要用后序遍历，因为前序和中序会先将根节点给销毁了，这样就不好往下找了，故此要使用后序遍历来一个个free掉每一个节点

二叉树的节点个数

int BinaryTreeSize(BTNode* root)
{if (root == NULL)return 0;return BinaryTreeSize(root->_left)+ BinaryTreeSize(root->_right) + 1;
}

控制好递归的次数 

只需要在遍历每一层节点时+1，即可

二叉树叶子节点个数

int BinaryTreeLeafSize(BTNode* root)
{if (root == NULL)return 0;if (root->_left == NULL && root->_right == NULL)return 1;return BinaryTreeLeafSize(root->_left) + BinaryTreeLeafSize(root->_right);
}

还是先控制递归的层数，当root等于空时往回返

若root的左和右都为空，则说明当前节点为叶子节点，返回1

最后返回左子树叶子节点和右子树叶子节点个数相加即可

二叉树第K层节点个数

int BinaryTreeLevelKSize(BTNode* root, int k)
{if (root == NULL)return 0;if (k == 1)return 1;return BinaryTreeLevelKSize(root->_left, k - 1) + BinaryTreeLevelKSize(root->_right, k - 1);
}

 和前面的递归思路都差不多

这里返回1的条件是k == 1，因为只需要递归k-1次即可，当递归次数达到说明也到了第k层，则返回1即可

最后返回给外层的时候把左右子树的结果返回起来相加即可

二叉树的查找

BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{if (root == NULL)return NULL;if (root->_data == x)return root;BTNode* ret1 = BinaryTreeFind(root->_left, x);if (ret1)return ret1;BTNode* ret2 = BinaryTreeFind(root->_right, x);if (ret2)return ret2;return NULL;
}

 第一个if语句控制层数

第二个判断查找结果，若找到则返回根节点root

找到的结果返回给下面的ret1指针或者ret2指针，通过这两个指针返回给最外层

层序遍历

void BinaryTreeLevelOrder(BTNode* root)
{Queue q;QueueInit(&q);if (root)QueuePush(&q, root);while (!QueueEmpty(&q)){BTNode* front = QueueFront(&q);QueuePop(&q);printf("%d ", front->_data);if (front->_left)QueuePush(&q, front->_left);if (front->_right)QueuePush(&q, front->_right);}QueueDestroy(&q);
}

层序遍历是一层一层从左到右遍历，那么我们就需要借助队列来完成（先进先出）

例如该图层序遍历后就是1，2，4，3，5，6

首先我们需要将根节点入队列

然后进入循环，我们循环的条件是队列为空则停止循环

所以我们还需要不断入栈

这里第一层已经入栈了，这时候就可以拿到这个节点，我把它叫做front

后面我们就可以打印这个front节点的data

然后就可以删除掉这个节点了，但是删除的同时需要把它的左右孩子带进来，但是左右孩子有可能为空，所以先判断，若不为空则push入队列，这样第二层就入队列了

接下来继续pop2和4（pop的同时打印），然后push2和4的左右孩子

 最后不要忘记将队列销毁，防止造成内存泄漏

判断二叉树是否为完全二叉树

int BinaryTreeComplete(BTNode* root)
{Queue q;QueueInit(&q);if (root)QueuePush(&q, root);while (!QueueEmpty(&q)){BTNode* front = QueueFront(&q);QueuePop(&q);if (front == NULL)break;QueuePush(&q, front->_left);QueuePush(&q, front->_right);}while (!QueueEmpty(&q)){BTNode* front = QueueFront(&q);QueuePop(&q);if (front == NULL){QueueDestroy(&q);return 0;}}QueueDestroy(&q);return 1;
}

和前面层序遍历差不多，我们也需要借用一个队列来完成该函数

先入第一个根节点进队列，然后循环的将二叉树的全部节点按照层序遍历都push进去 

push到最后队列的头节点front总会碰到空节点，所以我们碰到空节点就break出去循环，这是第一个循环的主要作用

例如该二叉树，我们push2的时候就会把左节点3和右节点NULL给入队列，那么我们的front肯定会接收到NULL从而跳出循环

如上并不是一个完全二叉树，所以我们判断它不是完全二叉树的理由就是根据层序遍历它的空节点后面还有一个节点6

所以我们第二个循环的任务就是pop掉队列剩下的所有值，若pop的时候发现里面还有非空节点，则不为完全二叉树，return 0

例如我们在把NULL节点接收给front时，我们肯定会经过4这个节点，然后4这个节点就会把它的左NULL和右6两个节点入队列

所以我们最后在把队列全部出掉的时候肯定会碰到这个6，既然碰到了这个6就说明这不是一个完全二叉树

完整代码

#include"BinaryTree.h"
#include"Queue.h"BTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi)
{if (*pi >= n){(*pi)++;return NULL;}BTNode* root = (BTNode*)malloc(sizeof(BTNode));root->_data = a[(*pi)++];root->_left = BinaryTreeCreate(a, n, pi);root->_right = BinaryTreeCreate(a, n, pi);return root;
}void BinaryTreeDestory(BTNode* root)
{if (root == NULL)return;BinaryTreeDestory(root);BinaryTreeDestory(root);free(root);
}int BinaryTreeSize(BTNode* root)
{if (root == NULL)return 0;return BinaryTreeSize(root->_left)+ BinaryTreeSize(root->_right) + 1;
}int BinaryTreeLeafSize(BTNode* root)
{if (root == NULL)return 0;if (root->_left == NULL && root->_right == NULL)return 1;return BinaryTreeLeafSize(root->_left) + BinaryTreeLeafSize(root->_right);
}int BinaryTreeLevelKSize(BTNode* root, int k)
{if (root == NULL)return 0;if (k == 1)return 1;return BinaryTreeLevelKSize(root->_left, k - 1) + BinaryTreeLevelKSize(root->_right, k - 1);
}BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{if (root == NULL)return NULL;if (root->_data == x)return root;BTNode* ret1 = BinaryTreeFind(root->_left, x);if (ret1)return ret1;BTNode* ret2 = BinaryTreeFind(root->_right, x);if (ret2)return ret2;return NULL;
}void BinaryTreePrevOrder(BTNode* root)
{if (root == NULL){printf("N ");return;}printf("%d ", root->_data);BinaryTreePrevOrder(root->_left);BinaryTreePrevOrder(root->_right);
}void BinaryTreeInOrder(BTNode* root)
{if (root == NULL){printf("N ");return;}BinaryTreeInOrder(root->_left);printf("%d ", root->_data);BinaryTreeInOrder(root->_right);
}void BinaryTreePostOrder(BTNode* root)
{if (root == NULL){printf("N ");return;}BinaryTreePostOrder(root->_left);BinaryTreePostOrder(root->_right);printf("%d ", root->_data);
}void BinaryTreeLevelOrder(BTNode* root)
{Queue q;QueueInit(&q);if (root)QueuePush(&q, root);while (!QueueEmpty(&q)){BTNode* front = QueueFront(&q);QueuePop(&q);printf("%d ", front->_data);if (front->_left)QueuePush(&q, front->_left);if (front->_right)QueuePush(&q, front->_right);}QueueDestroy(&q);
}int BinaryTreeComplete(BTNode* root)
{Queue q;QueueInit(&q);if (root)QueuePush(&q, root);while (!QueueEmpty(&q)){BTNode* front = QueueFront(&q);QueuePop(&q);if (front == NULL)break;QueuePush(&q, front->_left);QueuePush(&q, front->_right);}while (!QueueEmpty(&q)){BTNode* front = QueueFront(&q);QueuePop(&q);if (front == NULL){QueueDestroy(&q);return 0;}}QueueDestroy(&q);return 1;
}

完


http://www.ppmy.cn/news/1463706.html

相关文章

vue-封装上下(垂直方向)轮播

vue-封装上下(垂直方向)轮播

需求&#xff1a;没有找到特别好的上下轮播插件-所以自己写了一个简单的demo 一.上下平滑轮播-移入停止-移出继续轮播 <!--* 消息滚动 --> <template><div class"news"><div id"roll" class"InfoBox" mouseover"thi…
阅读更多...
java新特性（Stream API）

java新特性（Stream API）

什么是 Stream API？ Stream API 是 Java 8 引入的一个用于对集合数据进行函数式编程操作的强大的库。它允许我们以一种更简洁、易读、高效的方式来处理集合数据，可以极大提高 Java 程序员的生产力，是目前为止对 Java 类库最好的补充。 Stream API 的核心思想是将数据处理操作…
阅读更多...
【Sql Server】随机查询一条表记录，并重重温回顾下自定义函数的封装和使用

【Sql Server】随机查询一条表记录，并重重温回顾下自定义函数的封装和使用

大家好&#xff0c;我是全栈小5&#xff0c;欢迎来到《小5讲堂》。 这是《Sql Server》系列文章&#xff0c;每篇文章将以博主理解的角度展开讲解。 温馨提示&#xff1a;博主能力有限&#xff0c;理解水平有限&#xff0c;若有不对之处望指正&#xff01; 目录 前言随机查询语…
阅读更多...
6.Redis之String命令

6.Redis之String命令

1.String类型基本介绍 redis 所有的 key 都是字符串, value 的类型是存在差异的~~ 一般来说,redis 遇到乱码问题的概率更小~~ Redis 中的字符串,直接就是按照二进制数据的方式存储的. (不会做任何的编码转换【讲 mysql 的时候,知道 mysql 默认的字符集, 是拉丁文,插入中文…
阅读更多...
vite+js配置

vite+js配置

vite js 配置路径 npm install types/node --save-dev vite.config.js import { defineConfig } from vite import vue from vitejs/plugin-vue //需要引入 import path from path// https://vitejs.dev/config/ export default defineConfig({plugins: [vue()],resolve: {a…
阅读更多...
人类和小鼠转录组上游分析

人类和小鼠转录组上游分析

基础软件 conda install cutadapt, trimmomatic, samtools, hisat2, subread, deeptools -y人类转录组上游分析 # 样本名称 sample_namesample# 线程 threads4# 双端测序原始fastq1和fastq2路径 fastq1_path/path/${sample_name}_1.fq.gz fastq2_path/path/${sample_name}_2.…
阅读更多...
vue2 面试题

vue2 面试题

一、.vue的性能优化怎么做&#xff1f; 1.编码优化&#xff1a; 不要把所有的数据都放在data中&#xff1b;v-for时给每个元素绑定事件用事件代理&#xff1b;keep-alive缓存组件&#xff1b;尽可能拆分组件&#xff0c;提高复用性、维护性&#xff1b;key值要保证唯一&#…
阅读更多...
基于SpringBoot+Vue在线动漫信息平台设计和实现(源码+LW+部署讲解)

基于SpringBoot+Vue在线动漫信息平台设计和实现(源码+LW+部署讲解)

&#x1f339;作者主页&#xff1a;青花锁 &#x1f339;简介&#xff1a;Java领域优质创作者&#x1f3c6;、Java微服务架构公号作者&#x1f604; &#x1f339;简历模板、学习资料、面试题库、技术互助 &#x1f339;文末获取联系方式 &#x1f4dd; &#x1f339;推荐一个人…
阅读更多...
最新文章

Copyright @ 2022~2023