【数据结构】链式二叉树(超详细)

文章目录

  • 前言
  • 二叉树的链式结构
  • 二叉树的遍历方式
    • 二叉树的深度优先遍历
      • 前序遍历(先根遍历)
      • 中序遍历(中根遍历)
      • 后序遍历(后根遍历)
    • 二叉树的广度优先遍历
      • 层序遍历
  • 二叉树链式结构接口实现
    • 二叉树结点个数
    • 二叉树叶子结点个数
    • 二叉树的深度(高度)
    • 二叉树第k层结点个数
    • 二叉树查找x值的结点
    • 销毁二叉树
    • 二叉树的创建及遍历
  • 衍生题
    • 判断二叉树是否为完全二叉树
    • 判断二叉树是否为单值二叉树
    • 判断两颗二叉树是否相同
    • 判断二叉树是否为对称二叉树
    • 判断一颗二叉树是否为另一颗二叉树的子树
    • 判断二叉树是否为平衡二叉树
    • 翻转二叉树

前言

二叉树的顺序结构就是用数组来存储,而「数组」一般只适合表示「满二叉树」或「完全二叉树」,因为不是完全二叉树会有「空间的浪费」。
普通二叉树的增删查改没有意义,主要学习它的结构,要加上搜索树的规则,才有价值。

二叉树的链式结构

二叉树链式结构的实现
在学习二叉树的基本操作前,需先要创建一棵二叉树,这里手动快速创建一棵简单的二叉树

#include<stdio.h>  // perror, printf
#include<stdlib.h> // malloctypedef char BTDataType;
// 定义二叉树的结点
typedef struct BinaryTreeNode
{BTDataType data;struct BinaryTreeNode* left;struct BinaryTreeNode* right;
}BTNode;// 动态申请一个新结点
BTNode* BuyNode(BTDataType x)
{// BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));if (newnode == NULL){perror("malloc");exit(-1);}newnode->data = x;newnode->left = newnode->right = NULL;return newnode;
}// 二叉树的链式结构
BTNode* CreatBinaryTree()
{// 创建多个结点BTNode* node_A = BuyNode('A');BTNode* node_B = BuyNode('B');BTNode* node_C = BuyNode('C');BTNode* node_D = BuyNode('D');BTNode* node_E = BuyNode('E');BTNode* node_F = BuyNode('F');// 用链来指示结点间的逻辑关系node_A->left = node_B;node_A->right = node_C;node_B->left = node_D;node_C->left = node_E;node_C->right = node_F;return node_A;
}

注意:上述代码并不是创建二叉树的方式
在这里插入图片描述

二叉树的遍历方式

二叉树的深度优先遍历

由于被访问的结点必是「某子树的根」,所以N(Node)、L(Left subtree)和R(Right subtree)又可解释为根、根的左子树和根的右子树。NLR、LNR和LRN分别又称为先根遍历、中根遍历和后根遍历。

前序遍历(先根遍历)

遍历顺序:根->左子树->右子树

//前序遍历
void BinaryPrevOrder(BTNode* root)
{if (root == NULL){return;}//根->左子树->右子树printf("%c ", root->data);BinaryPrevOrder(root->left);BinaryPrevOrder(root->right);
}

这里的访问路径是:A B D NULL NULL NULL C E NULL NULL F NULL NULL

在这里插入图片描述

接下来的两个遍历可以自己试试画一下递归图。

中序遍历(中根遍历)

遍历顺序:左子树->根->右子树

void BinaryInOrder(BTNode* root)
{if (root == NULL){return;}//左子树->根->右子树BinaryInOrder(root->left);printf("%c ", root->data);BinaryInOrder(root->right);
}

这里的访问路径是:NULL D NULL B NULL A NULL E NULL C NULL F NULL

后序遍历(后根遍历)

遍历顺序:左子树->右子树->根

//后序遍历
void BinaryPostOrder(BTNode* root)
{if (root == NULL){return;}//左子树->右子树->根BinaryPostOrder(root->left);BinaryPostOrder(root->right);printf("%c ", root->data);
}

这里的访问路径是:NULL NULL D NULL B NULL NULL E NULL NULL F C A

二叉树的广度优先遍历

层序遍历

层序遍历,自上而下,从左往右逐层访问树的结点的过程就是层序遍历。
在这里插入图片描述
我们借助队列来实现:
先入根结点,然后出队列,再入他的两个孩子,然后一样的出孩子,再入孩子的孩子,重复即可。(NULL不入)
在这里插入图片描述

//层序遍历
void BinaryLevelOrder(BTNode* root)
{Queue q;QueueInit(&q);//初始化队列if (root != NULL)QueuePush(&q, root);int levelSize = 1;while (!QueueEmpty(&q))//当队列不为空时,循环继续{//一层一层出while (levelSize--){BTNode* front = QueueFront(&q);//读取队头元素QueuePop(&q);//删除队头元素printf("%c ", front->data);//打印出队的元素if (front->left){QueuePush(&q, front->left);//出队元素的左孩子入队列}if (front->right){QueuePush(&q, front->right);//出队元素的右孩子入队列}}printf("\n");levelSize = QueueSize(&q);}printf("\n");QueueDestroy(&q);//销毁队列
}

二叉树链式结构接口实现

二叉树结点个数

子问题拆解:
 1.若为空,则结点个数为0。
 2.若不为空,则结点个数 = 左子树结点个数 + 右子树结点个数 + 1(自己)。

//结点的个数
int BinaryTreeSize(BTNode* root)
{//结点个数 = 左子树的结点个数 + 右子树的结点个数 + 自己return root == NULL ? 0 : BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;
}

在这里插入图片描述

二叉树叶子结点个数

子问题拆解:
 1.若为空,则叶子结点个数为0。
 2.若结点的左指针和右指针均为空,则叶子结点个数为1。
 3.除上述两种情况外,说明该树存在子树,其叶子结点个数 = 左子树的叶子结点个数 + 右子树的叶子结点个数。

//叶子结点的个数
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);
}

在这里插入图片描述

二叉树的深度(高度)

子问题拆解:

  1. 先判断当前树的根结点是否为空
  2. 当前树的根结点不为空,分别计算其左右子树的深度
  3. 比较当前树左右子树的深度,最大的那个+1 就是当前树的深度
// 二叉树的深度(高度)
int BinaryTreeMaxDepth(BTNode* root)
{// 先判断当前树的根结点是否为空if (root == NULL){return 0;}// 当前树的根结点不为空,分别计算其左右子树的深度int leftDepth = BinaryTreeMaxDepth(root->left);int rightDepth = BinaryTreeMaxDepth(root->right);// 比较当前树左右子树的深度,最大的那个+1 就是当前树的深度return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
}

在这里插入图片描述

二叉树第k层结点个数

//第k层结点的个数O(N)
int BinaryTreeKLevelSize(BTNode* root, int k)
{assert(k > 0);if (root == NULL)return 0;if (k == 1)//第一层结点个数return 1;//相对于父结点的第k层的结点个数 = 相对于两个孩子结点的第k-1层的结点个数之和return BinaryTreeKLevelSize(root->left, k - 1) + BinaryTreeKLevelSize(root->right, k - 1);
}

在这里插入图片描述

二叉树查找x值的结点

//查找值为x的结点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{if (root == NULL)//空树return NULL;if (root->data == x)//先判断根结点return root;BTNode* leftret = BinaryTreeFind(root->left, x);//在左子树中找if (leftret)return leftret;BTNode* rightret = BinaryTreeFind(root->right, x);//在右子树中找if (rightret)return rightret;return NULL;//根结点和左右子树中均没有找到
}

在这里插入图片描述

销毁二叉树

这里要用后序遍历来销毁,左子树->右子树->根

//销毁二叉树
void BinaryTreeDestroy(BTNode* root)
{if (root == NULL)return;BinaryTreeDestroy(root->left);BinaryTreeDestroy(root->right);free(root);//没有用二级指针,这里只是实参的拷贝,需要用完主动置空再函数外置空}

二叉树的创建及遍历

编一个程序,读入用户输入的一串先序遍历字符串,根据此字符串建立一个二叉树(以指针方式存储)。
例如如下的先序遍历字符串: ABC##DE#G##F### 其中“#”表示的是空格,空格字符代表空树。建立起此二叉树以后,再对二叉树进行中序遍历,输出遍历结果。

在这里插入图片描述

依次读取字符,拆分成子问题:
1.如果不是#,创建结点,存值,然后递归其左子树和右子树;
2.如果是#,说明不能构建结点了,直接返回NULL;

#include <stdio.h>typedef char  BTDataType;
typedef struct BinaryTreeNode{BTDataType data;struct BinaryTreeNode*left;struct BinaryTreeNode*right;}BTNode;BTNode*BinaryTreeCreat(char*arr,int*pi)
{if(arr[*pi]=='#'){(*pi)++;return NULL;}BTNode*node=(BTNode*)malloc(sizeof(BTNode));node->data=arr[*pi];(*pi)++;node->left=NULL;node->right=NULL;
node->left=BinaryTreeCreat(arr,pi);//递归构建左子树
node->right=BinaryTreeCreat(arr,pi);//递归构建右子树
return node;
}//中序遍历
void BinaryInOrder(BTNode*root)
{if(root==NULL)return;BinaryInOrder(root->left);printf("%c ",root->data);BinaryInOrder(root->right);
}int main() {
char ret[100];
scanf("%s",&ret );
int i=0;
BTNode*root= BinaryTreeCreat(ret,&i);
BinaryInOrder(root);
printf("\n");return 0;
}

衍生题

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

用一个队列来判断
将根从队尾入列,然后从队头出数据,出根的时候入它的左孩子和右孩子,NULL也入列。重复次操作,当出数据第一次遇到NULL时,停止入队列并且检查队列中是否还有数据,如果全部为NULL则此树时完全二叉树
如果队列中还有数据,则不是完全二叉树。

// 判断二叉树是否是完全二叉树
bool BinaryTreeComplete(BTNode* root)
{Queue q;QueueInit(&q);//初始化队列if (root != NULL)QueuePush(&q, root);while (!QueueEmpty(&q))//当队列不为空时,循环继续{BTNode* front = QueueFront(&q);//读取队头元素QueuePop(&q);//删除队头元素//遇到第一个NULL结点直接跳出循环if (front == NULL)break;QueuePush(&q, front->left);//出队元素的左孩子入队列(NULL也入)QueuePush(&q, front->right);//出队元素的右孩子入队列(NULL也入)}//前面遇到空以后,后面还有非空就不是完全二叉树while (!QueueEmpty(&q))//当队列不为空时,循环继续{BTNode* front = QueueFront(&q);//读取队头元素QueuePop(&q);//删除队头元素if (front){QueueDestroy(&q);//销毁队列return false;}}//没有遇到说明是完全二叉树QueueDestroy(&q);//销毁队列return true;
}

判断二叉树是否为单值二叉树

单值二叉树,所有结点的值都相同的二叉树即为单值二叉树,判断某一棵二叉树是否是单值二叉树的一般步骤如下:
 1.判断根的左孩子的值与根结点是否相同。
 2.判断根的右孩子的值与根结点是否相同。
 3.判断以根的左孩子为根的二叉树是否是单值二叉树。
 4.判断以根的右孩子为根的二叉树是否是单值二叉树。
若满足以上情况,则是单值二叉树。

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);
}

判断两颗二叉树是否相同

拆分成子问题:
先判断根是否为空
再比较根的左子树是否相同
再比较跟根的右子树是否相同

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 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->right)&&isSameTree(p->right,q->left);}bool isSymmetric(struct TreeNode* root) {if(root==NULL)return true;return isSameTree(root->left,root->right);}

判断一颗二叉树是否为另一颗二叉树的子树

两个树都是空树,返回true
如果两个树一个是空,一个不是空,不包含
两个树都是非空,比较根节点的值是不是相等,如果相等的话,比较一下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)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(isSameTree(root->left,subRoot))return true;return isSubtree(root->left,subRoot)||isSubtree(root->right,subRoot);}

判断二叉树是否为平衡二叉树

如果某二叉树中任意节点的左右子树的深度相差不超过1,那么它就是一棵平衡二叉树。
子问题:
求出左子树的深度。
求出右子树的深度。
若左子树与右子树的深度差的绝对值不超过1,并且左右子树也是平衡二叉树,则该树是平衡二叉树。

int max(int x,  int y)
{return x>y?x:y;
}
int height(struct TreeNode* root)
{if (root == NULL) return 0;return max(height(root->left), height(root->right)) + 1;
}bool isBalanced(struct TreeNode* root)
{if (root == NULL) return true;//左右子树高度差的绝对值不超过1 && 其左子树是平衡二叉树 && 其右子树是平衡二叉树return fabs(height(root->left) - height(root->right)) <= 1 && isBalanced(root->left) &&isBalanced(root->right);//fabs取绝对值,要用要包含头文件#include<math.h>
}

翻转二叉树

子问题:
 翻转左子树。
 翻转右子树。
 交换左右子树的位置。

//翻转二叉树
struct TreeNode* invertTree(struct TreeNode* root)
{if (root == NULL)//根为空,直接返回return root;struct TreeNode* left = invertTree(root->left);//翻转左子树struct TreeNode* right = invertTree(root->right);//翻转右子树//左右子树位置交换root->left = right;root->right = left;return root;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/333086.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

el-switch自动触发更新事件

比如有这样一个列表&#xff0c;允许修改单条数据的状态。希望在更改el-switch状态时能够有个弹框做二次确认&#xff0c;没问题&#xff0c;el-switch已经帮我们想到了&#xff0c;所以它提供了beforeChange&#xff0c;根据beforeChange的结果来决定是否修改状态。一般确认修…

Java入门-java的集合框架

集合概念 集合&#xff0c;有时也称作容器(Container), 是对象的持有者&#xff0c;它们可以有助于高效访问的方式存储的组织对象。以生活中的案例为例&#xff1a; 集合就像装衣服的柜子&#xff0c;衣服就是集合中的元素。 集合框架图 Collection中每次操作的都是一个对象&a…

android-mvp模式

mvvm可以理解成使用databing的mvp模式&#xff0c;modleview 通过接口让view和Presenter层解耦 从图中就可以看出&#xff0c;最明显的差别就是view层和model层不再相互可知&#xff0c;完全的解耦&#xff0c;取而代之的presenter层充当了桥梁的作用&#xff0c;用于操作view…

56. UE5 RPG 给敌人添加AI实现跟随玩家

在这一篇里&#xff0c;我们要实现一下敌人的AI&#xff0c;敌人也需要一系列的行为&#xff0c;比如朝向英雄攻击&#xff0c;移动&#xff0c;在满足条件时施放技能。这些敌人的行为可以通过使用UE的内置的AI系统去实现。 在UE里&#xff0c;只要是基于Character类创建的蓝图…

java欢迪迈手机商城设计与实现源码(springboot+vue+mysql)

风定落花生&#xff0c;歌声逐流水&#xff0c;大家好我是风歌&#xff0c;混迹在java圈的辛苦码农。今天要和大家聊的是一款基于springboot的欢迪迈手机商城设计与实现。项目源码以及部署相关请联系风歌&#xff0c;文末附上联系信息 。 项目简介&#xff1a; 欢迪迈手机商城…

D - Permutation Subsequence(AtCoder Beginner Contest 352)

题目链接: D - Permutation Subsequence (atcoder.jp) 题目大意&#xff1a; 分析&#xff1a; 相对于是记录一下每个数的位置 然后再长度为k的区间进行移动 然后看最大的pos和最小的pos的最小值是多少 有点类似于滑动窗口 用到了java里面的 TreeSet和Map TreeSet存的是数…

【C语言】结构体内存对齐:热门面试话题

&#x1f525;引言 书接上文&#xff0c;我们了解关于结构体的基本知识&#xff0c;这篇将深入剖析结构体中一个重要的知识点:内存对齐 关于内存对齐是属于热门面试话题&#xff0c;对此单独放在一篇来分享 &#x1f308;个人主页&#xff1a;是店小二呀 &#x1f308;C语言笔记…

Docker Portainer使用

Portainer是什么 Docker Portainer是一个轻量级的 Web UI 管理界面,可以用来管理Docker环境。它提供了一个直观的控制台,用户可以通过它来管理Docker主机、容器、网络、卷等Docker资源。 Portainer的主要功能和特点包括: 容器管理:可以查看、启动、停止、删除容器,以及查看容器…

计算机毕业设计 | springboot+vue房屋租赁管理系统(附源码)

1&#xff0c;绪论 1.1 课题来源 随着社会的不断发展以及大家生活水平的提高&#xff0c;越来越多的年轻人选择在大城市发展。在大城市发展就意味着要在外面有一处安身的地方。在租房的过程中&#xff0c;大家也面临着各种各样的问题&#xff0c;比如需要费时费力去现场看房&…

host修改

前言 想要修改 hosts 文件&#xff0c;您需要具有对系统文件的适当访问权限&#xff0c;并且知道如何编辑文本文件。hosts 文件是一个用于域名解析的本地文件&#xff0c;它允许您为特定的 IP 地址指定主机名。 以下是在不同操作系统中修改 hosts 文件的步骤&#xff1a; 一、…

项目集成SkyWalking,基于k8s搭建

一、搭建SkyWalking 官方文档&#xff08;英文&#xff09;&#xff1a;skywalking/docs at master apache/skywalking 中文可以使用&#xff1a;GitHub - SkyAPM/document-cn-translation-of-skywalking: [已过期,请使用官网AI文档] The CN translation version of Apache…

【qt】自定义代理类

自定义代理类 一.应用场景二.创建自定义代理类1.创建一个类2.共有继承父类3.添加宏4.初始化父类5.拿到我们需要重写的虚函数 三.实现父类的4个虚函数1.创建代理组件2.设置代理组件数据3.设置模型数据4.跟新代理组件的位置 四.使用代理类1.头文件2.私有成员3.视图设置代理 五.其…

Web上机:JSP+Servlet+JDBC的交互流程

目录 需求与设计 基础需求&#xff1a; 项目结构&#xff1a; 项目逻辑&#xff1a; 运行图示&#xff1a; 代码实现 Login.jsp InsertServlet SelectServlet Table.jsp user mysql表结构 Web开发技术迭代速度日新月异&#xff0c;对于技术的更新往往是基于底层一…

基于Python+flask+echarts的气象数据采集与分析系统,可实现lstm算法进行预测

背景 基于PythonFlaskEcharts的气象数据采集与分析系统结合了强大的数据处理能力和可视化展示技术&#xff0c;旨在实现对气象数据的实时采集、存储和分析。通过Python编程语言实现数据采集模块&#xff0c;利用Flask框架搭建后端系统&#xff0c;实现数据处理、存储和分析功能…

Python小游戏——俄罗斯方块

文章目录 项目介绍环境配置代码设计思路1.初始化和导入库&#xff1a;2.定义颜色和屏幕尺寸&#xff1a;3.定义游戏逻辑&#xff1a;4.游戏循环&#xff1a; 源代码效果图 项目介绍 俄罗斯方块游戏是一款经典的益智游戏&#xff0c;玩家通过旋转和移动各种形状的方块&#xff…

深入剖析—【服务器硬件】与【Nginx配置】:从基础到实战

服务器硬件部分&#xff1a; Processor (CPU)&#xff1a;服务器的计算核心&#xff0c;负责处理数据和执行程序。Memory (RAM)&#xff1a;用于暂时存储和快速访问数据&#xff0c;决定了系统的运行速度和并发处理能力。Storage (HDD/SSD)&#xff1a;长期存储数据的设备&…

爱设计AiPPT.cn赵充:营销工作的AI进化

爱设计&AiPPT.cn是一家 AIGC 数字科技企业&#xff0c;致力于打造「下一代个人与组织的 Ai 工作站」 。目前旗下产品包括AiPPT.cn、爱设计AIGC 内容中台、365 编辑器、爱设计在线设计工具、AiH5 等超过 10 余款应用 AI 能力的内容创作工具。日前&#xff0c;爱设计&AiP…

期货学习笔记-横盘行情学习1

横盘行情的特征及分类 横盘行情的概念 横盘行情时中继形态的一种&#xff0c;一般常出现在大涨或大跌之后出现横盘行情是对当前趋势行情的修正&#xff0c;是对市场零散筹码的清理&#xff0c;是为了集中筹码更便于后期行情的展开 横盘行情的特征 1.水平运动&#xff1a;该…

从零自制docker-15-【实现 mydocker run -d 支持后台运行容器】

文章目录 实现目的莫名奇妙的问题对之前upper层出现root补充对run某些命令出现找不到文件或目录的原因代码效果 实现目的 docker run -d时容器在后台运行&#xff0c;而不会进入命令行交互形式 首先是需要添加-d选项然后设置当添加-d选项时候主进程不会等待子进程&#xff0c…

从Python代码到pip包:打包Python项目

大家好&#xff0c;在软件开发的世界中&#xff0c;共享和重用代码是至关重要的。Python社区为我们提供了丰富的资源&#xff0c;使得我们能够轻松地与他人分享我们的工作&#xff0c;并从他人的工作中受益。将代码打包成pip包&#xff08;Python包管理器&#xff09;是一种常见…