数据结构--二叉树(C语言实现,超详细!!!)

2024-09-08 05:44

本文主要是介绍数据结构--二叉树(C语言实现,超详细!!!),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

文章目录

  • 二叉树的概念
  • 代码实现
      • 二叉树的定义
      • 创建一棵树并初始化
      • 组装二叉树
      • 前序遍历
      • 中序遍历
      • 后序遍历
      • 计算树的结点个数
      • 求二叉树第K层的结点个数
      • 求二叉树高度
      • 查找X所在的结点
      • 查找指定节点在不在
      • 完整代码

二叉树的概念

二叉树(Binary Tree)是数据结构中一种非常重要的树形结构,它的特点是每个节点最多有两个子节点,通常称为左子节点和右子节点。这种结构使得二叉树在数据存储和查找等方面具有高效性,广泛应用于各种算法和程序中。

节点(Node):二叉树的基本单元,用于存储数据和指向子节点的指针。每个节点可以包含三个部分:数据域、左指针和右指针。数据域用于存储节点的值,左指针指向左子节点,右指针指向右子节点。
特点
有序性:二叉树的每个节点都有明确的左子节点和右子节点之分,这种有序性使得二叉树在数据查找和遍历等方面具有高效性。
递归性:二叉树的很多操作都可以通过递归的方式来实现,例如遍历、插入和删除等。这种递归性使得二叉树的处理变得简洁而统一。
灵活性:二叉树可以根据实际需求进行不同的扩展和变形,例如平衡二叉树、二叉搜索树等,以满足不同的应用场景。

代码实现

以下代码实现的是最普通的二叉树

二叉树的定义

这段代码定义了一个简单的二叉树节点结构体,其中包含指向左子树和右子树的指针以及一个整数值。
通过这种结构,我们可以构建一个二叉树,其中每个节点都有一个值,以及可能存在的左子树和右子树。

// 首先,定义一个结构体类型别名BinTreeNode,这个结构体用于表示二叉树的节点。  
typedef struct BinTreeNode {  // left是一个指向左子树根节点的指针。  // 在二叉树中,每个节点最多有两个子节点,这里left表示节点的左子树。  struct BinTreeNode* left;   // right是一个指向右子树根节点的指针。  // 与left相似,right表示节点的右子树。  struct BinTreeNode* right;  // val表示节点存储的数据值,这里是一个整型值。  int val;  } BTNode; // BTNode是这个结构体的类型别名,方便后续在代码中使用。  

创建一棵树并初始化

BuyNode函数是一个用于创建和初始化二叉树节点的函数。
它接受一个整数val作为参数,动态分配内存来创建一个新的BTNode结构体实例, 并将该实例的left和right指针初始化为NULL,val成员设置为传入的参数值。
如果内存分配失败,则打印错误信息并返回NULL。
如果成功,则返回指向新创建节点的指针。

// 函数用于创建一个新的二叉树节点,并初始化它  
BTNode* BuyNode(int val) {  // 使用malloc动态分配内存空间,大小为BTNode结构体的大小  // 并将分配到的内存地址强制转换为BTNode指针类型,赋值给newnode  BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));  // 检查malloc是否成功分配了内存  // 如果newnode为NULL,说明内存分配失败  if (newnode == NULL) {  // 如果内存分配失败,则打印错误信息  perror("malloc fail");  // 并返回NULL,表示节点创建失败  return NULL;  }  // 初始化新节点的左子树指针为NULL,表示当前没有左子树  newnode->left = NULL;  // 初始化新节点的右子树指针为NULL,表示当前没有右子树  newnode->right = NULL;  // 将传入的val值赋给新节点的val成员,设置节点的值  newnode->val = val; // 注意这里的val是函数参数,表示节点的数据值  // 返回新创建的节点指针,供外部使用  return newnode; // 节点创建成功,返回其地址  
}  

组装二叉树

CreatNode函数是一个用于组装特定二叉树的函数。
它首先调用BuyNode函数来创建6个独立的节点,并分别给它们赋值。
然后,它将这些节点通过它们的left和right指针连接起来,形成一个具有特定结构的二叉树。
最后,它返回根节点的指针,以便外部可以访问和操作这棵树。

// 函数用于组装(创建并连接)一个具体的二叉树,并返回其根节点指针  
BTNode* CreatNode() {  // 调用BuyNode函数创建6个新的二叉树节点,并分别初始化它们的值为1到6  BTNode* n1 = BuyNode(1); // 创建值为1的节点,并作为根节点  BTNode* n2 = BuyNode(2); // 创建值为2的节点  BTNode* n3 = BuyNode(3);  BTNode* n4 = BuyNode(4);  BTNode* n5 = BuyNode(5); BTNode* n6 = BuyNode(6);  // 下面的代码将这些节点连接起来,形成一个具体的二叉树结构  n1->left = n2;      // 将n2节点设置为n1节点的左子树  n1->right = n4;     // 将n4节点设置为n1节点的右子树  n2->left = n3;      // 将n3节点设置为n2节点的左子树(n2没有右子树)  n4->left = n5;      // 将n5节点设置为n4节点的左子树  n4->right = n6;     // 将n6节点设置为n4节点的右子树  //以上是我们人工建的一颗二叉树// 返回根节点的指针,这样外部就可以通过这个指针来访问整棵树了  return n1; // 根节点是n1,所以返回n1的指针  
}  

前序遍历

从这个函数开始,后面的函数基本都是递归了,强烈建议在刚开始学的时候多画几遍递归展开图,理解每个函数的运行过程,熟练之后就可以直接在脑海里理解过程了。
PreOrder函数实现了二叉树的前序遍历。
前序遍历的顺序是:先访问根节点,然后遍历左子树,最后遍历右子树。
在遍历过程中,如果遇到空节点(即子树不存在),则打印"N "。这里打印N是为了更易于理解。
这个函数通过递归的方式简洁地实现了前序遍历的逻辑。

// 定义前序遍历函数,参数为二叉树的根节点指针  
void PreOrder(BTNode* root) {  // 首先检查根节点是否为空  if (root == NULL) {  // 如果根节点为空,则打印"N "表示此处无节点(NULL的简写)  printf("N ");  // 然后直接返回,不再继续遍历  return;  }  // 如果根节点不为空,则首先打印根节点的值  printf("%d ", root->val);  // 接着递归地调用前序遍历函数,传入左子树的根节点  // 这样会先遍历整个左子树  PreOrder(root->left);  // 最后递归地调用前序遍历函数,传入右子树的根节点  // 这样会遍历整个右子树  PreOrder(root->right);  
}  

中序遍历

InOrder函数递归地先处理左子树,然后打印当前节点的值,最后处理右子树,直到所有节点都被访问并打印出来。如果树中存在空指针(即某个节点没有左子节点或右子节点),则打印"N "来表示该位置为空。
中序遍历的顺序是:先遍历左子树,然后访问根节点,最后遍历右子树。
在遍历过程中,如果遇到空节点(即子树不存在),则打印"N "。这里打印N是为了更易于理解。
这个函数也是通过递归的方式实现的,每次递归都处理当前节点的左子树、自身和右子树。

// 定义中序遍历函数,参数为二叉树的根节点指针  
void InOrder(BTNode* root) {  // 首先检查根节点是否为空  if (root == NULL) {  // 如果当前节点为空(即已经遍历到叶子节点下面,或者子树不存在)  // 则打印"N "表示此处无节点值可输出  printf("N ");  // 打印完毕后直接返回,不再继续遍历  return;  }  // 如果当前节点不为空,则先递归调用中序遍历函数,传入左子节点  // 这样可以确保在打印当前节点之前,先遍历并打印整个左子树  InOrder(root->left);  // 遍历完左子树后,回到当前节点,并打印当前节点的值  printf("%d ", root->val);  // 打印完当前节点值后,递归调用中序遍历函数,传入右子节点  // 这样可以确保在打印完当前节点后,继续遍历并打印整个右子树  InOrder(root->right);  
}  

后序遍历

PostOrder函数实现了二叉树的后序遍历。
后序遍历的顺序是:先遍历左子树,然后遍历右子树,最后访问根节点。
这个过程一直进行到所有节点都被访问并打印出来为止。
遍历过程中,若遇到空节点(即某节点没有左子节点或右子节点,或子树不存在),则打印"N "。
函数通过递归方式实现,递归的基准情况是节点为空时返回。

// 定义后序遍历函数,参数为二叉树的根节点指针  
void PostOrder(BTNode* root) {  // 首先检查传入的根节点是否为空  if (root == NULL) {  // 如果根节点为空,表示已经遍历到了叶子节点下面或者子树不存在  // 在此处打印"N ",作为空节点(NULL)的占位符输出  printf("N ");  // 打印完空节点后,直接返回,不再继续递归遍历  return;  }  // 如果当前节点不为空,则先递归调用后序遍历函数,传入左子节点  // 后序遍历的顺序是先遍历左子树  PostOrder(root->left);  // 接着递归调用后序遍历函数,传入右子节点  // 后序遍历接下来遍历右子树  PostOrder(root->right);  // 在确保左右子树都已经遍历完成后,打印当前节点的值  // 后序遍历的最后一步是访问(打印)根节点  printf("%d ", root->val);  
}  

计算树的结点个数

TreeSize函数用于递归地计算一棵二叉树中节点的总数。
函数首先检查传入的根节点是否为空,如果为空则返回0,表示没有节点。
如果根节点不为空,则函数递归地调用自身来计算左子树和右子树的节点数,
然后将这两个数相加,并加上1(代表当前根节点),从而得到整棵树的节点总数。
对于每个非空节点,函数会分别计算其左子树和右子树的节点数,然后将这两个数目相加,并加上当前节点自身(计数为1),从而得到以当前节点为根的子树的节点总数。这个过程会一直递归进行,直到遍历完整棵树,最终返回整棵树的节点总数。
递归方法写的代码一般都比较短,但是比一般方法更难以理解

// 定义计算二叉树节点个数的函数,参数为二叉树的根节点指针  
int TreeSize(BTNode* root) {  // 使用三目运算符(条件运算符)判断根节点是否为空  // 如果root为空,说明已经遍历到了叶子节点下面或者子树不存在,直接返回0  // 否则,递归地计算左子树的节点个数和右子树的节点个数,并将它们相加,再加上根节点自身(即+1)  return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;  
}  

求二叉树第K层的结点个数

TreeKLevel函数通过递归的方式求解二叉树第k层的节点个数。
以下方法的核心是:当前树的第k层个数 ==左子树的第k-1层个数 +左子树的第k-1层个数
递归的基准情况有两种:一是当节点为空时返回0,二是当k等于1时返回1。
对于其他情况,函数会递归地调用自身来计算左子树和右子树中第k-1层的节点数,
然后将这两个数相加得到结果。这个过程会一直进行下去,直到达到基准情况为止。
小结:这段代码的核心思想是利用递归逐层向下遍历二叉树,同时记录当前所在的层数。当遍历到目标层时,返回该层的节点数。由于二叉树的层数是从根节点开始计算的,因此在每次递归调用时,都需要将目标层数k减去1,以正确地定位到下一层。通过这种方式,函数能够准确地计算出二叉树中任意一层的节点个数。

// 定义函数TreeKLevel,用于求二叉树第k层的节点个数  
// 参数root为二叉树的根节点指针,k为目标层数  
int TreeKLevel(BTNode* root, int k) {  // 如果根节点为空,说明已经遍历到空树或者子树不存在  // 直接返回0,表示第k层没有节点  if (root == NULL) {  return 0;  }  // 如果k等于1,说明当前层就是第一层(根节点所在的层)  // 直接返回1,因为根节点是唯一一个在第1层的节点  if (k == 1) {  return 1;  }  // 如果k大于1,说明目标层在根节点的下面  // 递归地调用TreeKLevel函数,分别传入左子树和右子树的根节点,以及k-1作为新的层数  // 然后将两个递归调用的结果相加,得到第k层的节点总数  // 注意这里k要减1,是因为往下一层递归时,层数要相应地减少  return TreeKLevel(root->left, k - 1) + TreeKLevel(root->right, k - 1);  
}  

求二叉树高度

该函数通过递归的方式计算二叉树的高度。
递归的基准情况是当节点为空时,返回1(表示空树或不存在的高度,加1是为了方便递归计算)。
/对于非空节点,函数会分别计算其左子树和右子树的高度,然后取两者中的较大值,并加1作为当前树的高度。
返回值是整棵树的高度。

// 定义函数TreeHigh,用于求二叉树的高度  
// 参数root为二叉树的根节点指针  
int TreeHigh(BTNode* root) {  // 如果根节点为空,说明当前子树不存在或为空树  // 按照常规定义,空树的高度为0,但这里为了递归方便,返回1表示高度为0的层级上加1  // 注意:这种定义在递归的上下文中是合理的,但在实际应用中可能需要调整,以确保空树高度为0  if (root == NULL) {  return 1;  }  // 递归调用TreeHigh函数,计算左子树的高度  int leftHigh = TreeHigh(root->left);  // 递归调用TreeHigh函数,计算右子树的高度  int rightHigh = TreeHigh(root->right);  // 使用三目运算符比较左子树和右子树的高度  // 返回较高的一边的高度,并加上1(加上根节点所在的这一层)  return leftHigh > rightHigh ? leftHigh + 1 : rightHigh + 1;  
}  

查找X所在的结点

TreeFind函数是一个递归函数,用于在二叉树中查找值为x的节点。
它首先检查根节点是否为空或者是否就是要找的节。如果根节点为空,则返回NULL表示未找到。如果根节点的值等于x,则返回根节点的指针。
否则,函数会递归地在左子树和右子树中查找,直到找到目标节点或者遍历完整棵树。
如果在整棵树中都没有找到值为x的节点,则最终返回NULL。

// 定义函数TreeFind,用于在二叉树中查找值为x的节点,并返回该节点的指针  
// 参数root为二叉树的根节点指针,x为要查找的值  
BTNode* TreeFind(BTNode* root, int x) {  // 如果根节点为空,说明已经遍历到了空子树或者树本身为空  // 直接返回NULL,表示在当前子树中没有找到值为x的节点  if (root == NULL) {  return NULL;  }  // 如果根节点的值等于x,说明找到了目标节点  // 直接返回根节点的指针  if (root->val == x) {  return root;  }  // 递归调用TreeFind函数,在左子树中查找值为x的节点  // 将返回的节点指针赋值给ret1  BTNode* ret1 = TreeFind(root->left, x);  // 如果ret1不为空,说明在左子树中找到了值为x的节点  // 直接返回ret1,即找到了目标节点的指针  if (ret1) {  return ret1;  }  // 如果左子树中没有找到,继续递归调用TreeFind函数,在右子树中查找值为x的节点  // 将返回的节点指针赋值给ret2  BTNode* ret2 = TreeFind(root->right, x);  // 如果ret2不为空,说明在右子树中找到了值为x的节点  // 直接返回ret2,即找到了目标节点的指针  if (ret2) {  return ret2;  }  // 如果左右子树中都没有找到值为x的节点,说明整个树中都不存在该节点  // 返回NULL,表示没有找到目标节点  return NULL;  
}

查找指定节点在不在

// 参数:root 是指向二叉树根节点的指针,x 是要查找的节点值  
// 返回值:bool 类型,如果找到指定节点则返回 true,否则返回 false,这个通常用于条件语句或者循环语句里,返回true时执行,返回false时不执行  
// 功能:在二叉树中查找指定的节点值是否存在  
bool TreeFindExit(BTNode* root, int x) {  // 如果当前节点为空(即已经遍历到叶子节点之后的位置),则返回 false  if (root == NULL) {  return false;  }  // 如果当前节点的值等于要查找的值 x,则说明找到了指定的节点  // 直接返回 true  if (root->val == x) {  return true;  }  // 如果当前节点的值不是要查找的值,则递归地在左子树和右子树中查找  // 使用逻辑或操作符 ||,表示如果左子树或右子树中任何一个找到了指定节点就返回 true  // 如果左右子树都没有找到,最终会返回 false  return TreeFindExit(root->left, x) || TreeFindExit(root->right, x);  
}

完整代码

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>//二叉树的定义
typedef struct BinTreeNode {struct BinTreeNode* left;struct BinTreeNode* right;int val;
}BTNode;//创建一棵树并初始化
BTNode* BuyNode(int val) {BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));if (newnode == NULL) {perror("malloc fail");return;//注意这里应该是return NULL}newnode->left = NULL;newnode->right = NULL;newnode->val = val;//这里是valreturn newnode;//创建了就要返回
}//组装二叉树
BTNode* CreatNode() {BTNode* n1 = BuyNode(1);BTNode* n2 = BuyNode(2);BTNode* n3 = BuyNode(3);BTNode* n4 = BuyNode(4);BTNode* n5 = BuyNode(5);BTNode* n6 = BuyNode(6);n1->left = n2;n1->right = n4;n2->left = n3;n4->left = n5;n4->right = n6;return n1;//记得返回
}//前序遍历
void PreOrder(BTNode* root) {if (root == NULL) {printf("N ");return;}printf("%d ", root->val);PreOrder(root->left);PreOrder(root->right);
}//中序遍历
void InOrder(BTNode* root) {if (root == NULL) {printf("N ");return;}InOrder(root->left);printf("%d ",root->val);InOrder(root->right);
}//后序遍历
void PostOrder(BTNode* root) {if (root == NULL) {printf("N ");return;}PostOrder(root->left);PostOrder(root->right);printf("%d ",root->val);
}//计算树的结点个数
int TreeSize(BTNode* root) {return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;
}//求二叉树第K层的结点个数
int TreeKLevel(BTNode* root,int k) {if (root == NULL) {return 0;}if (k == 1) {//k=1时不需要再往下求了return 1;}return TreeKLevel(root->left, k - 1) + TreeKLevel(root->right, k - 1);
}
//求二叉树高度
int TreeHigh(BTNode* root) {if (root== NULL) {return 1;}int leftHigh = TreeHigh(root->left);int rightHigh = TreeHigh(root->right);return leftHigh > rightHigh ? leftHigh + 1 : rightHigh + 1;
}//查找X所在的结点
BTNode*TreeFind(BTNode*root,int x){if (root == NULL) {return NULL;}if (root->val == x) {return root;}BTNode* ret1=TreeFind(root->left, x);if (ret1) {return ret1;}BTNode* ret2 = TreeFind(root->right, x);if (ret2) {return ret2;}return NULL;}//查找指定节点在不在
bool TreeFindExit(BTNode* root, int x) {if (root == NULL) {return false;}if (root->val == x) {return true;}return TreeFindExit(root->left, x) || TreeFindExit(root->right, x);
}int main() {BTNode* root = CreatNode();PreOrder(root);printf("\n");InOrder(root);printf("\n");PostOrder(root);printf("\n");int high = TreeHigh(root);printf("%d\n", high);int a= TreeKLevel(root,2);printf("%d\n", a);BTNode* b = TreeFind(root, 1);printf("%d\n", b->val);if (TreeFindExit(root, 2)) {printf("存在\n");}else {printf("不存在\n");}return 0;
}

这篇关于数据结构--二叉树(C语言实现,超详细!!!)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1147281

相关文章

hdu1043(八数码问题,广搜 + hash(实现状态压缩) )

利用康拓展开将一个排列映射成一个自然数,然后就变成了普通的广搜题。 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#inclu

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

【C++】_list常用方法解析及模拟实现

相信自己的力量,只要对自己始终保持信心,尽自己最大努力去完成任何事,就算事情最终结果是失败了,努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一:什么是list? •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二:list常用接口 •🌰1.默认成员函数 🔥构造函数(⭐) 🔥析构函数 •🌰2.list对象

【Prometheus】PromQL向量匹配实现不同标签的向量数据进行运算

✨✨ 欢迎大家来到景天科技苑✨✨ 🎈🎈 养成好习惯,先赞后看哦~🎈🎈 🏆 作者简介:景天科技苑 🏆《头衔》:大厂架构师,华为云开发者社区专家博主,阿里云开发者社区专家博主,CSDN全栈领域优质创作者,掘金优秀博主,51CTO博客专家等。 🏆《博客》:Python全栈,前后端开发,小程序开发,人工智能,js逆向,App逆向,网络系统安全,数据分析,Django,fastapi

让树莓派智能语音助手实现定时提醒功能

最初的时候是想直接在rasa 的chatbot上实现,因为rasa本身是带有remindschedule模块的。不过经过一番折腾后,忽然发现,chatbot上实现的定时,语音助手不一定会有响应。因为,我目前语音助手的代码设置了长时间无应答会结束对话,这样一来,chatbot定时提醒的触发就不会被语音助手获悉。那怎么让语音助手也具有定时提醒功能呢? 我最后选择的方法是用threading.Time

Android实现任意版本设置默认的锁屏壁纸和桌面壁纸(两张壁纸可不一致)

客户有些需求需要设置默认壁纸和锁屏壁纸  在默认情况下 这两个壁纸是相同的  如果需要默认的锁屏壁纸和桌面壁纸不一样 需要额外修改 Android13实现 替换默认桌面壁纸: 将图片文件替换frameworks/base/core/res/res/drawable-nodpi/default_wallpaper.*  (注意不能是bmp格式) 替换默认锁屏壁纸: 将图片资源放入vendo

C#实战|大乐透选号器[6]:实现实时显示已选择的红蓝球数量

哈喽,你好啊,我是雷工。 关于大乐透选号器在前面已经记录了5篇笔记,这是第6篇; 接下来实现实时显示当前选中红球数量,蓝球数量; 以下为练习笔记。 01 效果演示 当选择和取消选择红球或蓝球时,在对应的位置显示实时已选择的红球、蓝球的数量; 02 标签名称 分别设置Label标签名称为:lblRedCount、lblBlueCount

科研绘图系列:R语言扩展物种堆积图(Extended Stacked Barplot)

介绍 R语言的扩展物种堆积图是一种数据可视化工具,它不仅展示了物种的堆积结果,还整合了不同样本分组之间的差异性分析结果。这种图形表示方法能够直观地比较不同物种在各个分组中的显著性差异,为研究者提供了一种有效的数据解读方式。 加载R包 knitr::opts_chunk$set(warning = F, message = F)library(tidyverse)library(phyl

透彻!驯服大型语言模型(LLMs)的五种方法,及具体方法选择思路

引言 随着时间的发展,大型语言模型不再停留在演示阶段而是逐步面向生产系统的应用,随着人们期望的不断增加,目标也发生了巨大的变化。在短短的几个月的时间里,人们对大模型的认识已经从对其zero-shot能力感到惊讶,转变为考虑改进模型质量、提高模型可用性。 「大语言模型(LLMs)其实就是利用高容量的模型架构(例如Transformer)对海量的、多种多样的数据分布进行建模得到,它包含了大量的先验

Kubernetes PodSecurityPolicy:PSP能实现的5种主要安全策略

Kubernetes PodSecurityPolicy:PSP能实现的5种主要安全策略 1. 特权模式限制2. 宿主机资源隔离3. 用户和组管理4. 权限提升控制5. SELinux配置 💖The Begin💖点点关注,收藏不迷路💖 Kubernetes的PodSecurityPolicy(PSP)是一个关键的安全特性,它在Pod创建之前实施安全策略,确保P