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

数据结构【链试结构二叉树】

news 2025/11/25 15:01:02

 

🌟个人主页：落叶

目录

 ​编辑

实现链式结构⼆叉树

前中后序遍历：

遍历规则

代码实现

前序遍历：

中序遍历：

后序遍历：

图解遍历：

函数递归栈帧图：

结点个数以及高度等

【⼆叉树】结点个数

【二叉树】叶子节点个数

【二叉树】第k层节点个数

【二叉树】的深度/⾼度

【二叉树】查找值为x的结点 

【二叉树】销毁

层序遍历

判断是否为完全二叉树

🔥摘要：设⼆叉树的根结点所在层数 为1，层序遍历就是从所在⼆叉树的根结点出发，⾸先访问第⼀层的树根结点，然后从左到右访问第2 层上的结点，接着是第三层的结点，以此类推，⾃上⽽下，⾃左⾄右逐层访问树的结点的过程就是层 序遍历。根结点的左⼦树和右⼦树分别⼜是由⼦树结点、⼦树结点的左⼦树、⼦树结点的右⼦树组成的，因此 ⼆叉树定义是递归式的,后序链式⼆叉树的操作中基本都是按照该概念实现的。回顾⼆叉树的概念，⼆叉树分为空树和⾮空⼆叉树，⾮空⼆叉树由根结点、根结点的左⼦树、根结点 的右⼦树组成的。根结点、左⼦树、右⼦树。

实现链式结构⼆叉树

⽤链表来表⽰⼀棵⼆叉树，即⽤链来指⽰元素的逻辑关系。通常的⽅法是链表中每个结点由三个域组 成，数据域和左右指针域，左右指针分别⽤来给出该结点左孩⼦和右孩⼦所在的链结点的存储地址， 其结构如下：

创建二叉树数据：

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>typedef int data;
typedef struct Tree
{int arr;    //数值struct Tree* zuo;//左孩子struct Tree* you;//右孩子
}BT;

⼆叉树的创建⽅式⽐较复杂，为了更好的步⼊到⼆叉树内容中，我们先⼿动创建⼀棵链式⼆叉树

我们进行连接后就成下面这个二叉树

当然我们也可以这样看

//申请空间
BT* koj(data x)
{//申请节点BT* tab = (BT*)malloc(sizeof(BT));if (tab == NULL){perror("malloic");exit(1);}tab->arr = x;tab->zuo= tab->you = NULL;return tab;
}
void p()
{//创建节点BT* n1 = koj(1);BT* n2 = koj(2);BT* n3 = koj(3);BT* n4 = koj(4);//进行连接n1->zuo = n2;n1->you = n3;n2->zuo = n4;}int main()
{p();return 0;
}

回顾⼆叉树的概念，⼆叉树分为空树和⾮空⼆叉树，⾮空⼆叉树由根结点、根结点的左⼦树、根结点 的右⼦树组成的

根结点的左⼦树和右⼦树分别⼜是由⼦树结点、⼦树结点的左⼦树、⼦树结点的右⼦树组成的，因此 ⼆叉树定义是递归式的,后序链式⼆叉树的操作中基本都是按照该概念实现的。

前中后序遍历：

⼆叉树的操作离不开树的遍历，我们先来看看⼆叉树的遍历有哪些⽅式

遍历规则

按照规则，⼆叉树的遍历有：前序/中序/后序的递归结构遍历：

（1）前序遍历(PreorderTraversal亦称先序遍历)：访问根结点的操作发⽣在遍历其左右⼦树之前

访问顺序为：根结点、左⼦树、右⼦树

（2）中序遍历(InorderTraversal)：访问根结点的操作发⽣在遍历其左右⼦树之中（间）

访问顺序为：左⼦树、根结点、右⼦树

（3）后序遍历(PostorderTraversal)：访问根结点的操作发⽣在遍历其左右⼦树之后

访问顺序为：左⼦树、右⼦树、根结点

代码实现
前序遍历：

访问顺序为：根结点、左⼦树、右⼦树

//前序遍历-（根-左-右）
void qian(BT* root)
{if (root == NULL){return;}printf("%d ", root->arr);//左子树qian(root->zuo);//右子树qian(root->you);
}

结果：

//申请空间
BT* koj(data x)
{//申请节点BT* tab = (BT*)malloc(sizeof(BT));if (tab == NULL){perror("malloic");exit(1);}tab->arr = x;tab->zuo= tab->you = NULL;return tab;
}
void p()
{//创建节点BT* n1 = koj(1);BT* n2 = koj(2);BT* n3 = koj(3);BT* n4 = koj(4);//进行连接n1->zuo = n2;n1->you = n3;n2->zuo = n4;qian(n1);printf("\n");}int main()
{p();return 0;
}
中序遍历：

访问顺序为：左⼦树、根结点、右⼦树

//中序遍历-（左-根-右）
void zho(BT* root)
{if (root == NULL){return;}//左子树zho(root->zuo);printf("%d ", root->arr);//右子树zho(root->you);
}

结果：

//申请空间
BT* koj(data x)
{//申请节点BT* tab = (BT*)malloc(sizeof(BT));if (tab == NULL){perror("malloic");exit(1);}tab->arr = x;tab->zuo= tab->you = NULL;return tab;
}
void p()
{//创建节点BT* n1 = koj(1);BT* n2 = koj(2);BT* n3 = koj(3);BT* n4 = koj(4);//进行连接n1->zuo = n2;n1->you = n3;n2->zuo = n4;/*qian(n1);printf("\n");*/zho(n1);printf("\n");}int main()
{p();return 0;
}
后序遍历：

访问顺序为：左⼦树、右⼦树、根结点

//后序遍历
void ho(BT* root)
{if (root == NULL){return;}//左子树ho(root->zuo);//右子树ho(root->you);printf("%d ", root->arr);
}

结果：

//申请空间
BT* koj(data x)
{//申请节点BT* tab = (BT*)malloc(sizeof(BT));if (tab == NULL){perror("malloic");exit(1);}tab->arr = x;tab->zuo= tab->you = NULL;return tab;
}
void p()
{//创建节点BT* n1 = koj(1);BT* n2 = koj(2);BT* n3 = koj(3);BT* n4 = koj(4);//进行连接n1->zuo = n2;n1->you = n3;n2->zuo = n4;/*qian(n1);printf("\n");*//*zho(n1);printf("\n");*/ho(n1);}int main()
{p();return 0;
}
图解遍历：

以前序遍历为例：

函数递归栈帧图：

前序遍历结果：123456

中序遍历结果：321546

后序遍历结果：315641

结点个数以及高度等
【⼆叉树】结点个数

// ⼆叉树结点个数 
int BinaryTreeSize(BT* root)
{if (root == NULL){return 0;}//                左子树                     右子树return 1+ BinaryTreeSize(root->zuo)+ BinaryTreeSize(root->you);
}

结果：

//申请空间
BT* koj(data x)
{//申请节点BT* tab = (BT*)malloc(sizeof(BT));if (tab == NULL){perror("malloic");exit(1);}tab->arr = x;tab->zuo= tab->you = NULL;return tab;
}
void p()
{//创建节点BT* n1 = koj(1);BT* n2 = koj(2);BT* n3 = koj(3);BT* n4 = koj(4);//进行连接n1->zuo = n2;n1->you = n3;n2->zuo = n4;/*qian(n1);printf("\n");*//*zho(n1);printf("\n");*///ho(n1);// ⼆叉树结点个数 printf("size:%d \n", BinaryTreeSize(n1));}int main()
{p();return 0;
}
【二叉树】叶子节点个数

// ⼆叉树叶⼦结点个数 
int BinaryTreeLeafSize(BT* root)
{if (root == NULL){return 0;}//左子树和右子树都等于空，就是叶子节点if (BinaryTreeLeafSize(root->zuo) == NULL && BinaryTreeLeafSize(root->you) == NULL){return 1;}return BinaryTreeLeafSize(root->zuo) + BinaryTreeLeafSize(root->you);
}

结果：

#define _CRT_SECURE_NO_WARNINGS 1
#include"Tree.h"
//申请空间
BT* koj(data x)
{//申请节点BT* tab = (BT*)malloc(sizeof(BT));if (tab == NULL){perror("malloic");exit(1);}tab->arr = x;tab->zuo= tab->you = NULL;return tab;
}
void p()
{//创建节点BT* n1 = koj(1);BT* n2 = koj(2);BT* n3 = koj(3);BT* n4 = koj(4);//进行连接n1->zuo = n2;n1->you = n3;n2->zuo = n4;/*qian(n1);printf("\n");*//*zho(n1);printf("\n");*///ho(n1);// ⼆叉树结点个数 //printf("size:%d \n", BinaryTreeSize(n1));//叶子节点个数printf("叶子节点：%d\n", BinaryTreeLeafSize(n1));}int main()
{p();return 0;
}
【二叉树】第k层节点个数

// ⼆叉树第k层结点个数 
int BinaryTreeLevelKSize(BT* root, int k)
{if (root == NULL){return 0;}//k等于1了就返回1if (k == 1){return 1;}return BinaryTreeLevelKSize(root->zuo, k - 1) + BinaryTreeLevelKSize(root->you, k - 1);
}

结果：

这里加了2个节点5和6，就和上面那张图一样了。

#define _CRT_SECURE_NO_WARNINGS 1
#include"Tree.h"
//申请空间
BT* koj(data x)
{//申请节点BT* tab = (BT*)malloc(sizeof(BT));if (tab == NULL){perror("malloic");exit(1);}tab->arr = x;tab->zuo= tab->you = NULL;return tab;
}
void p()
{//创建节点BT* n1 = koj(1);BT* n2 = koj(2);BT* n3 = koj(3);BT* n4 = koj(4);//进行连接n1->zuo = n2;n1->you = n3;n2->zuo = n4;/*qian(n1);printf("\n");*//*zho(n1);printf("\n");*///ho(n1);// ⼆叉树结点个数 //printf("size:%d \n", BinaryTreeSize(n1));// 叶子节点个数//printf("叶子节点：%d\n", BinaryTreeLeafSize(n1));//k层节点个数printf("k: %d \n", BinaryTreeLevelKSize(n1, 3));}int main()
{p();return 0;
}
【二叉树】的深度/⾼度

//⼆叉树的深度/⾼度
int BinaryTreeDepth(BT* root)
{if (root == NULL){return 0;}//遍历左子树，把值给zuoint zuo = BinaryTreeDepth(root->zuo);//遍历右子树,把值给youint you = BinaryTreeDepth(root->you);//进行判断return zuo > you ? zuo + 1:you + 1;
}

结果：

#define _CRT_SECURE_NO_WARNINGS 1
#include"Tree.h"
//申请空间
BT* koj(data x)
{//申请节点BT* tab = (BT*)malloc(sizeof(BT));if (tab == NULL){perror("malloic");exit(1);}tab->arr = x;tab->zuo= tab->you = NULL;return tab;
}
void p()
{//创建节点BT* n1 = koj(1);BT* n2 = koj(2);BT* n3 = koj(3);BT* n4 = koj(4);//进行连接n1->zuo = n2;n1->you = n3;n2->zuo = n4;/*qian(n1);printf("\n");*//*zho(n1);printf("\n");*///ho(n1);// ⼆叉树结点个数 //printf("size:%d \n", BinaryTreeSize(n1));// 叶子节点个数//printf("叶子节点：%d\n", BinaryTreeLeafSize(n1));k层节点个数//printf("k: %d \n", BinaryTreeLevelKSize(n1, 3));//⼆叉树的深度/⾼度printf("高度:%d \n", BinaryTreeDepth(n1));}int main()
{p();return 0;
}
【二叉树】查找值为x的结点 

// ⼆叉树查找值为x的结点 
BT* BinaryTreeFind(BT* root, data x)
{if (root == NULL){return NULL;}//等于x，返回当前节点if (root->arr == x){return root;}//zuo接收节点BT* zuo = BinaryTreeFind(root->zuo, x);if (zuo){//返回节点return zuo;}//you接收节点BT* you = BinaryTreeFind(root->you, x);if (you){//返回节点return you;}
}

左子树找不到，就找右子树

结果：

#define _CRT_SECURE_NO_WARNINGS 1
#include"Tree.h"
//申请空间
BT* koj(data x)
{//申请节点BT* tab = (BT*)malloc(sizeof(BT));if (tab == NULL){perror("malloic");exit(1);}tab->arr = x;tab->zuo= tab->you = NULL;return tab;
}
void p()
{//创建节点BT* n1 = koj(1);BT* n2 = koj(2);BT* n3 = koj(3);BT* n4 = koj(4);//BT* n5 = koj(5);//BT* n6 = koj(6);//进行连接n1->zuo = n2;n1->you = n3;n2->zuo = n4;//n2->you = n5;//n3->zuo = n6;/*qian(n1);printf("\n");*//*zho(n1);printf("\n");*///ho(n1);// ⼆叉树结点个数 //printf("size:%d \n", BinaryTreeSize(n1));// 叶子节点个数//printf("叶子节点：%d\n", BinaryTreeLeafSize(n1));k层节点个数//printf("k: %d \n", BinaryTreeLevelKSize(n1, 3));⼆叉树的深度/⾼度//printf("高度:%d \n", BinaryTreeDepth(n1));// ⼆叉树查找值为x的结点 BT* tab = BinaryTreeFind(n1, 4);printf("%s\n", tab == NULL ? "没找到" : "找到了");}int main()
{p();return 0;
}
【二叉树】销毁

// ⼆叉树销毁
void BinaryTreeDestory(BT** root)
{if (*root == NULL){return;}//二级指针，需要传一级指针地址BinaryTreeDestory(&(*root)->zuo);BinaryTreeDestory(&(*root)->you);//释放空间free(*root);*root = NULL;
}

图解析：

结果：

我们可以看到全部销毁了。

层序遍历

除了先序遍历、中序遍历、后序遍历外，还可以对⼆叉树进⾏层序遍历。设⼆叉树的根结点所在层数 为1，层序遍历就是从所在⼆叉树的根结点出发，⾸先访问第⼀层的树根结点，然后从左到右访问第2 层上的结点，接着是第三层的结点，以此类推，⾃上⽽下，⾃左⾄右逐层访问树的结点的过程就是层 序遍历

实现层序遍历需要额外借助数据结构：队列

创建队列，初始化，把根节点入队列

循环队列不为空，取队头打印，出队头。

然后判断左子树和右子树，是不是空，不是空就入队列。

销毁队列。

//层序遍历
//借助数据结构--队列
void LevelOrder(BT* root)
{Queue add;//初始化Queuecsh(&add);//入数据Queue_ruwei(&add, root);while (!buer(&add)){//取队头-打印BT* tab = qto(&add);printf("%d ", tab->arr);//出队Queue_chu(&add);//判断是不是空， 队头节点的左右孩子入，队列if (tab->zuo){Queue_ruwei(&add, tab->zuo);}if (tab->you){Queue_ruwei(&add, tab->you);}}//队列销毁Queuexiaoh(&add);
}

结果：

判断是否为完全二叉树

注意：

如果是完全二叉树，跳出循环之后队列里都是NULL。

如果不是完全二叉树，跳出循环之后队列里，还有非空节点。

思路：

创建一个队列，把根节点入队列，循环队列里不为空。

取队头节点，然后出队，判断这个节点是不是空，是空跳出循环。

不是空，左子树和右子树入队列。

是完全二叉树的话剩下的都是空，

循环取出队头数据，出队，进行判断，不等于空的话还有非空节点，那就是不完全二叉树了，返回false。

最后循环都为空，是完全二叉树，返回true。

bool pdercs(BT* root)
{Queue add;//队列初始化Queuecsh(&add);//入队列Queue_ruwei(&add, root);while (!buer(&add)){//取队头数据BT* tab =  qto(&add);//出队Queue_chu(&add);if (tab == NULL){//等于空结束循环break;}//不为空让左右子树入队列//左子树_入队列Queue_ruwei(&add, tab->zuo);//右子树_入队列Queue_ruwei(&add, tab->you);}//循环判断队列，有一个数值不是完全二叉树，都是NULL就是完全二叉树while (!buer(&add)){//取队头BT* app = qto(&add);//出队Queue_chu(&add);//判断如果还有非空节点，返回falseif (app != NULL){Queuexiaoh(&add);return false;}}//循环完，说明队列里都是NULL,是完全二叉树，返回true//队列销毁Queuexiaoh(&add);return true;
}

结果：


http://www.mrgr.cn/news/7327.html

相关文章：

  • 分享一个基于文本挖掘的微博舆情分析系统Python网络舆情监控系统Flask爬虫项目大数据（源码、调试、LW、开题、PPT）
  • 【机器人学】7-2.六自由度机器人自干涉检测-计算圆柱体的上下圆心坐标【附MATLAB代码】
  • Python TensorFlow进阶篇
  • 数据导入导出（EasyExcel）框架入门指南
  • scrapy框架--快速了解
  • 2024年Google开发者大会：AI赋能的Web、移动和云开发
  • 路线规划之Neo4j
  • 基于java的少儿编程网上报名系统+vue
  • ASP.NET下Webshell编译产物免杀
  • 计算机毕业设计--基于深度学习(PSPNet、空洞卷积Atrous Convolutions)的多类型图像通用分割模型
  • 游卡，得物，三七互娱，顺丰（提前批），快手，oppo，埃科光电，康冠科技25届秋招内推
  • leetcode 3 无重复字符的最长子串
  • 大数据技术之Zookeeper服务器动态上下线监听（6）
  • 2024网络安全学习路线 非常详细 推荐学习
  • AI时代的价值盈利②：人工智能将如何改变SaaS应用的定价指标
  • C++运算符重载
  • 【Ansible】Ansible playbook
  • 基于STM32开发的智能温室控制系统
  • 【速览】CSS（更新中）
  • 严重腰椎滑脱、无法走路，江山邦尔骨科医院机器人辅助手术为患者完美复位