程序员经验分享-hwhale

【数据结构】二叉树接口的实现及OJ题

2023-11-02

需要云服务器等云产品来学习Linux的同学可以移步/-->腾讯云<--/-->阿里云<--/-->华为云<--/官网，轻量型云服务器低至112元/年，新用户首次下单享超低折扣。

 目录

一、二叉树的接口

1、二叉树的结构体

2、手动造一颗二叉树

3、二叉树的销毁

4、二叉树的前、中、后序遍历

5、二叉树的节点个数

6、二叉树的叶子节点个数

7、二叉树第k层节点的个数

8、求树的高度

9、查找二叉树节点值为x的节点

10、二叉树的层序遍历、判断一颗二叉树是否是完全二叉树

二、二叉树相关OJ题

1、二叉树的前序遍历

2、单值二叉树

3、二叉树的最大深度

4、翻转二叉树

5、相同的树

6、对称二叉树

7、另一颗数的子树

8、平衡二叉树

9、二叉树遍历

本文以该颗二叉树为例：

一、二叉树的接口

1、二叉树的结构体

typedef int BinaryDataType;
typedef struct BinaryTree
{
	BinaryDataType data;
	struct BinaryTree* left;
	struct BinaryTree* right;
}BTNode;

一个二叉树的节点包含数据、指向左子树、右子树的指针。

2、手动造一颗二叉树

BTNode* BTBuyNode()//动态申请一个二叉树节点
{
	BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	return newnode;
}
BTNode* BinaryTreeCreate()//创造一颗二叉树
{
	BTNode* A = BTBuyNode();BTNode* B = BTBuyNode();BTNode* C = BTBuyNode();
	BTNode* D = BTBuyNode();BTNode* E = BTBuyNode();BTNode* F = BTBuyNode();
	A->data = 1;B->data = 2;C->data = 3;D->data = 4;E->data = 5;F->data = 6;
	A->left = B;A->right = C;
	B->left = D;B->right = NULL;
	C->left = E;C->right = F;
	D->left = NULL;D->right = NULL;
	E->left = NULL;E->right = NULL;
	F->left = NULL;F->right = NULL;
	return A;
}

3、二叉树的销毁

void BinaryTreeDestory(BTNode** root)//二叉树的销毁
{
	if (*root == NULL)
	{
		return;
	}
	BinaryTreeDestory(&(*root)->left);
	BinaryTreeDestory(&(*root)->right);
	free(*root);
	*root = NULL;
}

注意二叉树的销毁要销毁每个节点，先销毁左右子树，再销毁根。再将根节点置空。

4、二叉树的前、中、后序遍历

void PreOrder(BTNode* root)//前序遍历
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	printf("%d ", root->data);
	PreOrder(root->left);
	PreOrder(root->right);
}
void InOrder(BTNode* root)//中序遍历
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	InOrder(root->left);
	printf("%d ", root->data);
	InOrder(root->right);
}
void PostOrder(BTNode* root)//后序遍历
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	PostOrder(root->left);
	PostOrder(root->right);
	printf("%d ", root->data);
}

前序遍历（先根）：根 、左子树、右子树

中序遍历（中根）：左子树、根、右子树

后序遍历（后根）：左子树、右子树 、根

5、二叉树的节点个数

int BinaryTreeSize(BTNode* root)//二叉树节点个数
{
	return root == NULL ? 0 : BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;
}

6、二叉树的叶子节点个数

int BinaryTreeLeafSize(BTNode* root)//二叉树的叶子结点
{
	if (root == NULL)
		return 0;
	else if (root->left == NULL && root->right == NULL)
		return 1;
	return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}

7、二叉树第k层节点的个数

int BinaryTreeLevelKSize(BTNode* root, int k)//二叉树第k层的节点个数，化简为k-1层问题
{
	if (root == NULL)
		return 0;
	else if (k == 1)//k走到1就是一个节点
		return 1;
	return BinaryTreeLevelKSize(root->left, k - 1) + BinaryTreeLevelKSize(root->right, k - 1);
}

8、求树的高度

int BinaryTreeHeight(BTNode* root)//求树的高度
{
	if (root == NULL)
		return 0;
	int leftHeight = BinaryTreeHeight(root->left);
	int rightHeight = BinaryTreeHeight(root->right);
	return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}

9、查找二叉树节点值为x的节点

BTNode* BinaryTreeFind(BTNode* root, BinaryDataType x)//查找二叉树节点值为x的节点
{
	if (root == NULL)
		return NULL;
	if (root->data == x)
		return root;
	BTNode* leftRet = BinaryTreeFind(root->left, x);
	BTNode* rightRet = BinaryTreeFind(root->right, x);
	return leftRet == NULL ? rightRet : leftRet;
}

10、二叉树的层序遍历、判断一颗二叉树是否是完全二叉树

void BinaryTreeLevelOrder(BTNode* root)//二叉树的层序遍历，广度优先遍历，使用队列
{
	Queue q;
	QueueInit(&q);//初始化
	QueuePush(&q, root);//入队,尾插
	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);//访问队头数据
		QueuePop(&q);//出队（头删）
		printf("%d ", front->data);
		if (front->left != NULL)
			QueuePush(&q, front->left);//入队,尾插
		if (front->right != NULL)
			QueuePush(&q, front->right);//入队,尾插
	}
	QueueDestroy(&q);//销毁
}
bool BinaryTreeComplete(BTNode* root)//判断一颗树是否是完全二叉树,层序判断
{
	Queue q;
	QueueInit(&q);//初始化
	QueuePush(&q, root);//入队,尾插
	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);//访问队头数据
		if (front == NULL)//当队头为NULL时，后续全是NULL，则为完全二叉树
			break;
		QueuePop(&q);//出队（头删）
		QueuePush(&q, front->left);//入队,尾插
		QueuePush(&q, front->right);//入队,尾插
	}
	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);//访问队头数据
		if (front != NULL)
			return false;
		QueuePop(&q);//出队（头删）
	}
	QueueDestroy(&q);//销毁
	return true;
}

二叉树的层序遍历可以使用队列来完成，先将根节点入队，根节点出队时将自己的左右节点带入队列中。注意，这里要带入节点而不是节点的值（因为你把节点的值入队列，那节点的值是没有办法找到它的左右子树的）

判断一颗二叉树是不是一颗完全二叉树，同样使用队列来进行判断，先对节点不断入队，出队时遇到NULL，就跳出第一个循环。加入第二个循环如果这是一颗完全二叉树，那么继续出队将全是NULL，如果不是，将会遇到不为空的节点。

二、二叉树相关OJ题

1、二叉树的前序遍历

思路：

这道题的参数只有一个root，还需要知道二叉树的节点个数，用于动态申请空间用于存储节点值。

1、求出二叉树节点个数

2、因为原函数开辟了空件，不能对原函数递归，需要写一个前序遍历函数。

代码：

int BinaryTreeSize(struct TreeNode* root)//节点个数
 {
    return root==NULL?0:BinaryTreeSize(root->left)+BinaryTreeSize(root->right)+1;
 }

void PreOrdre(struct TreeNode* root,int* arr,int* pi)//前序遍历
{
    if(root==NULL)
    {
        return;
    }
    arr[(*pi)++]=root->val;
    PreOrdre(root->left,arr,&pi);
    PreOrdre(root->right,arr,&pi);
}

int* preorderTraversal(struct TreeNode* root, int* returnSize){
    int size=BinaryTreeSize(root);
    *returnSize=size;
    int* arr=(struct TreeNode*)malloc(sizeof(struct TreeNode));
    int i=0;
    PreOrdre(root,arr,&i);
    return arr;
}

注意这里的i需要传入i的地址，因为i需要改变，所以要传入i的地址，并且i在递归调用时，属于不同的栈帧空间，需要使用i的地址将改变的i带回。

2、单值二叉树

思路：

判断false的情况，再进行递归，左右子树有一个为false，整体为false

代码：

bool isUnivalTree(struct TreeNode* root){
    if(root==NULL)
        return true;
    if(root->left!=NULL&&root->val!=root->left->val)
        return false;
    if(root->right!=NULL&&root->val!=root->right->val)
        return false;
    bool left=isUnivalTree(root->left);
    bool right=isUnivalTree(root->right);
    return left==false?false:right;
}

3、二叉树的最大深度

思路：

就是求二叉树的高度

代码：

int maxDepth(struct TreeNode* root){
    if(root==NULL)
        return 0;
    int leftHeight=maxDepth(root->left);
    int rightHeight=maxDepth(root->right);
    return leftHeight>rightHeight?leftHeight+1:rightHeight+1;
}

4、翻转二叉树

思路：

代码：

void Swap(struct TreeNode** left,struct TreeNode** right)
{
    struct TreeNode* tmp=*left;
    *left=*right;
    *right=tmp;
}
struct TreeNode* invertTree(struct TreeNode* root){
    if(root==NULL)
        return NULL;
    Swap(&(root->left),&(root->right));
    invertTree(root->left);
    invertTree(root->right);
    return root;
}

5、相同的树

思路：

思路和本文第二题类似，先把一遍的情况全部罗列出来，再执行递归。本题相同的树需要考虑p和q均为空指针、p和q是否均有节点、p和q指向的节点的值是否相等。

代码：

bool isSameTree(struct TreeNode* p, struct TreeNode* q){
    if(p==NULL&&q==NULL)
        return true;
    if((p==NULL&&q!=NULL)||(p!=NULL&&q==NULL))
        return false;
    if(p->val!=q->val)
        return false;
    return isSameTree(p->left,q->left)&&isSameTree(p->right,q->right);
}

6、对称二叉树

思路：

判断一颗二叉树是不是轴对称，那么只需要判断它的子树是不是轴对称

1、如果左树为空，右树不为空，false

2、如果左树不为空，右树为空，false

3、如果左树右树均为空，true

4、如果左树值等于右树值且左树的左子树和右树的右子树且左树的右子树和右树的左子树，true

代码：

bool A(struct TreeNode* leftTree,struct TreeNode* rightTree)
{
    if(leftTree==NULL&&rightTree!=NULL)
        return false;
    if(leftTree!=NULL&&rightTree==NULL)
        return false;
    if(leftTree==NULL&&rightTree==NULL)
        return true;
    if((leftTree->val==rightTree->val)&&A(leftTree->left,rightTree->right)
    &&A(leftTree->right,rightTree->left))
        return true;
    return false;
}

bool isSymmetric(struct TreeNode* root){
    if(root==NULL)
        return true;
    return A(root->left,root->right);
}

7、另一颗数的子树

思路：

复用本文第5题，相同的树接口，就很简单了

代码：

bool isSametree(struct TreeNode* root, struct TreeNode* subRoot)
{
    if(root==NULL&&subRoot==NULL)
        return true;
    if(root==NULL||subRoot==NULL)
        return false;
    if(root->val!=subRoot->val)
        return false;
    return isSametree(root->left,subRoot->left)
    &&isSametree(root->right,subRoot->right);

}
bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot){
    if(isSametree(root,subRoot))
        return true;
    if(root==NULL)
        return false;
    return isSubtree(root->left,subRoot)||isSubtree(root->right,subRoot);
}

8、平衡二叉树

思路：

1、根节点为空，true

2、计算左树的高度、计算右树的高度

3、绝对值是否大于1

4、返回根节点左子树并且右子树的情况

代码：

int BinaryTreeHeight(struct TreeNode* root)
{
    if(root==NULL)
        return 0;
    int leftHeight=BinaryTreeHeight(root->left)+1;
    int rightHeight=BinaryTreeHeight(root->right)+1;
    return leftHeight>rightHeight?leftHeight:rightHeight;
}
bool isBalanced(struct TreeNode* root){
    if(root==NULL)
        return true;
    int leftHeight=BinaryTreeHeight(root->left);
    int rightHeight=BinaryTreeHeight(root->right);
    if(abs(leftHeight-rightHeight)>1)
        return false;
    return isBalanced(root->left)&&isBalanced(root->right);
}

9、二叉树遍历

思路：

1、如果arr[*i]是'#'，那么返回NULL

2、如果arr[*i]不是'#'，创建一个节点并将对应数组的值赋给这个节点

3、递归左树，递归右树，返回根节点

代码：

#include <stdio.h>
#include <stdlib.h>
typedef struct BinaryTree
{
    char data;
    struct BinaryTree* left;
    struct BinaryTree* right;
}BTNode;
void InOrder(BTNode* root)//中序遍历
{
	if (root == NULL)
	{
		return;
	}
	InOrder(root->left);
	printf("%c ", root->data);
	InOrder(root->right);
}
BTNode* create(char* arr,int* i)
{
    if(arr[*i]=='#')
    {
        ++(*i);
        return NULL;
    }      
    BTNode* root=(BTNode*)malloc(sizeof(BTNode));
    root->data=arr[(*i)++];//如果能到这一步，说明arr[*i]不是#
    root->left=create(arr,i);
    root->right=create(arr,i);
    return root;
}

int main()
{
    char arr[101];
    scanf("%s",arr);
    int i=0;//数组下标
    BTNode* root=create(arr,&i);
    InOrder(root);//中序遍历
    return 0;
}
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

数据结构与算法

数据结构

算法

Java

【数据结构】二叉树接口的实现及OJ题 的相关文章

随机推荐

  • Java多线程:高并发下数据插入重复问题

    转自 微点阅读 https www weidianyuedu com 1 背景描述 应用框架 Spring SpringMVC Hibernate 数据库 Oracle11g 一家文学网站向我系统推多线程低并发推送数据 我这边观察日志和数据

  • Ubuntu 16.04 pycharm设置桌面快捷启动方式

    Ubuntu下所有的快捷方式都在 usr share applications 解压 这里我将pycharm下载并解压到了 home snakeson developer文件夹下 这里的pycharm sh是批处理执行文件 prcharm

  • linux设置定时任务(crontab)操作步骤

    1 登录服务器 2 输入密码 登录成功 3 查看定时器任务 crontab l 4 编辑定时器任务 crontab e 5 保存定时器任务 1 按住sec退出 2 按住shift 再按 wq 保存并退出 备注 按住shift 再按 q 强制

  • CSS flex布局最后一个元素的宽度铺满剩余的空间

    当你希望最后一个元素的宽度铺满剩余的空间是 你可以为他设计一下属性 flex grow 1 例子 div div class sma1 div div class sma2 div div big width 200px height 10

  • [1114]mysql-connector-java各种版本下载地址

    mysql connector java下载地址 http mvnrepository com artifact mysql mysql connector java 1 进去后选择自己的版本 2 然后再点击 需要下载其他的jar包 或者依

  • 彻底解决虚拟机浏览器设置、扩展等花屏空白不显示问题

    问题现象 在我们日常使用VirtualBox vmware workstation Hyper V虚拟机软件的时候 不知不觉我们有没有遇到这种情况 chrome浏览器或者win10 win11自带的Edge浏览器的设置栏 浏览器标签预览 浏

  • Java实现 LeetCode 575 分糖果（看看是你的长度小还是我的种类少）

    575 分糖果 给定一个偶数长度的数组 其中不同的数字代表着不同种类的糖果 每一个数字代表一个糖果 你需要把这些糖果平均分给一个弟弟和一个妹妹 返回妹妹可以获得的最大糖果的种类数 示例 1 输入 candies 1 1 2 2 3 3 输出

  • Unity Navigation详解

    Unity Navigation详解 前言 从事unity相关行业以来始终看不清自己的路该怎么走 到今天才明白不需要花时间去迷茫 只管努力莫问前程 从今天开始每天写一点小东西 记录与整理自己走过的路 也一边寻找自己的路 便从unity的自动

  • BuildaFlightTrackerwithCesiumforUnreal_译

    BuildaFlightTrackerwithCesiumforUnreal 译 这个教程会使用真实世界飞机数据控制一个飞机飞过从圣弗朗西斯科到哥本哈根 你会学到怎样 1 输入真实数据到UnrealEngine 2 使用数据和USpline

  • 活动如何造势推广？会议软件帮您忙

    会议管理者辛苦策划了一场活动 如果推广宣传跟不上 那策划的心血岂不白费 如何使用有效且高效的方法为活动推广造势呢 传统推广方式耗费人力大 成本高 但通过会议软件便可以快速推广活动并有效宣传 下面为您介绍如何使用会议软件实现有效推广 01 社

  • python开发面试题

    python基础 1 Python类中的方法类型 在Python类中有四种方法类型 分别是实例方法 静态方法 类方法和普通方法 实例方法 即对象方法 需要实例化对象之后才能调用 接受的第一个参数self就是对象本身 必须使用实例化对象才可以

  • linux 图形分区工具,Linux下的图形分区工具

    在Linux下的许多情况下 分区将不足 这时 我们将需要调整分区 Windows下有很多工具 Linux下也有 您可以使用gparted进行分区 Gparted是parted的前端 图形化 linux下分区工具 通常包含在官方资源中 可以直

  • 2020年校赛网络赛

    51假期那段时间因为水了一段时间的数模校赛 加上专业课的坑越欠越多 因而已经很久很久没有补过题目了 从近到远 先把西电校赛的坑填起来 再把之前的CF牛客Atcoder补起来 qaq C 发现交换律后就显然了 D 双指针 好像第一天晚上还有个

  • 蓝桥杯2022真题：统计子矩阵、字符统计、排列字母、顺子日期、特殊时间、三角回文数、2022、星期计算

    目录 1 统计子矩阵 2 字符统计 3 排列字母 4 顺子日期 5 特殊时间 6 三角回文数 7 2022 8 星期计算 1 统计子矩阵 import os import sys 请在此输入您的代码 n m k map int input

  • chrome扩展结构

    每个打开的页面都运行在web页面环境中 一个正常的web页面环境 会先初始化css 然后建立DOM树 接着加载图片和frame等子资源 然后顺序执行所有js l chrome扩展本身运行在一个进程中 称之为background环境 back

  • 【软件测试学习笔记】白盒测试

    文章目录 一 白盒测试概述 二 分类 1 静态测试 2 动态测试 三 白盒测试原则 四 白盒测试类别 五 不同阶段不同侧重点 1 单元测试 2 集成测试 3 系统测试 4 验收测试 六 测试覆盖率 1 功能点覆盖 2 结构覆盖率 七 逻辑覆

  • LVGL在linux环境搭建篇

    LVGL环境搭建 1 环境准备 1 下载源码 https github com lvgl lvgl https github com lvgl lvgl 2 新建lvgl 文件夹 把src 和lvgl h 和lv conf template

  • 疯狂的采药（完全背包例题详解）

    题目 每种草药可以无限制地采摘 每种草药对应采药时间 草药价值 求在一定的采药时间下 采出的药最大总价值是多少 输入格式 输入第一行有两个整数 分别代表总共能够用来采药的时间 t 和代表山洞里的草药的数目 m 第 2 到第 m 1 行 每行

  • Entity Framework Core系列教程-18-断开模式下删除数据

    Entity Framework Core 断开模式下删除数据 EF Core API会为EntityState为Deleted的实体建立并执行数据库中的DELETE语句 在EF Core中已连接和已断开连接的场景中删除实体没有什么区别 E

  • 【数据结构】二叉树接口的实现及OJ题

    需要云服务器等云产品来学习Linux的同学可以移步 gt 腾讯云 lt gt 阿里云 lt gt 华为云 lt 官网 轻量型云服务器低至112元 年 新用户首次下单享超低折扣 目录 一 二叉树的接口 1 二叉树的结构体 2 手动造一颗二叉树

热门标签