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

数据结构自学Day9: 二叉树的遍历

一、二叉树的遍历

“遍历”就是按某种规则 依次访问树中的每个节点,确保 每个节点都被访问一次且只访问一次

        遍历:前序 中序 后序(深度优先),层序(广度优先)

类型

遍历方法

特点

深度优先遍历

前序、中序、后序

类似“先走到尽头,再回头”

广度优先遍历

层序遍历(Level-order)

按层访问,从上到下

二、深度优先遍历

任何一个二叉数、都要看做3个部分:

        1、根节点;2、左子树;3、右子树。

前序:(先根遍历)根 左子树 右子树 -->子树遇到空才结束,用途: 复制树、表达式树转前缀表达式等

中序:(中根遍历) 左子树 根 右子树 ,用途: 如果是二叉搜索树(BST),中序遍历输出的是升序序列 

后序:(中根遍历) 左子树 右子树 根 ,用途: 删除树(先删子树再删根)、表达式树转后缀表达式等

示意图:

遍历方式

访问顺序

前序

A B D E C F

中序

D B E A C F

后序

D E B F C A

二叉树的前序遍历实现(利用递归的思想):

        

代码实现:

1、二叉树的初始化

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include <string.h>#define Init_Capcity 5
typedef char BTDataType;
typedef struct BNTreeNode
{BTDataType _data;struct BNTreeNode* left_child;struct BNTreeNode* right_child;
}BNTreeNode;BNTreeNode* BNTreeNode_Init(){BNTreeNode* pt = (BNTreeNode*)malloc(sizeof(BNTreeNode));pt ->left_child =NULL;pt->right_child = NULL;return pt;
}

2、新增子节点

//新增子节点
BNTreeNode* BuyTreeNode(BTDataType val){BNTreeNode* NewNode = (BNTreeNode*)malloc(sizeof(BNTreeNode));NewNode->_data = val;NewNode->left_child = NULL;NewNode->right_child = NULL;return NewNode;
}

3、二叉树的前序遍历以及主函数的实现

void BNTraverse(BNTreeNode* root){if(root == NULL){return;}printf("%c  ",root->_data);BNTraverse(root->left_child);BNTraverse(root->right_child);
}int main(){BNTreeNode* Root = BNTreeNode_Init();Root->_data = 'A';Root->left_child = BuyTreeNode('B');Root->right_child = BuyTreeNode('C');(Root->left_child)->left_child = BuyTreeNode('D');(Root->left_child)->right_child = BuyTreeNode('E');(Root->right_child)->left_child = BuyTreeNode('F');BNTraverse(Root);
}

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

void InOrder(BNTreeNode* root){if(root == NULL){return;}InOrder(root->left_child);printf("%c  ",root->_data);InOrder(root->right_child);
}
void PostOrder(BNTreeNode* root){if(root == NULL){return;}PostOrder(root->left_child);PostOrder(root->right_child);printf("%c  ",root->_data);
}

输出结果:

A  B  D  NULL NULL E  NULL NULL C  F  NULL NULL NULL 
NULL D  NULL B  NULL E  NULL A  NULL F  NULL C  NULL 
NULL NULL D  NULL NULL E  B  NULL NULL F  NULL C  A
 

利用类似的递归思路求解,二叉树的元素个数,叶节点个数,深度等

1、二叉树元素的个数 -->遇到空节点停止

//两种方法
void TreeSize(BNTreeNode* root,int* psize){if(root == NULL){return;}//static int size = 0; //静态变量只有当前文件能使用(*psize)++;TreeSize(root->left_child,psize);TreeSize(root->right_child,psize);
}
//不需要额外参数
int TreeSize(BNTreeNode* root){if(root == NULL){return 0;}else{return 1+TreeSize(root->left_child)+TreeSize(root->right_child);}
}

2、叶节点个数-->遍历到无子节点(叶节点)

//统计叶节点个数
int TreeLeafSize(BNTreeNode* root){if(root == NULL){return 0;}if(root->left_child == NULL && root->right_child == NULL){return 1;}return TreeLeafSize(root->left_child)+TreeLeafSize(root->right_child);
}

3、需要比较左右子树的深度 -->遇到空节点停止

int TreeDepth(BNTreeNode* root) {if (root == NULL) {return 0;}int left_depth = TreeDepth(root->left_child);int right_depth = TreeDepth(root->right_child);return 1 + (left_depth > right_depth ? left_depth : right_depth);
}

三、广度优先遍历(BFS / 层序遍历)

使用队列实现,按照“从上到下、从左到右”的层级顺序访问:堆的访问顺序

访问顺序: A → B → C → D → E → F 

算法:

  1. 把根节点放入队列;

  2. 每次从队列中取出一个节点,访问它;

  3. 如果它有左子、右子节点,把它们加入队列;

  4. 循环直到队列为空。

等价于数组的访问顺序,我们直到其实堆就是按数组进行存放的

好了本期内容我们就到这里结束了!谢谢大家的点赞和收藏!

http://www.lryc.cn/news/591590.html

相关文章:

  • Git简介与特点:从Linux到分布式版本控制的革命
  • redis中间件
  • git merge-base查看某个分支从哪里拉出来的、主main分支上的某个时间之后某人的提交合并到特定分支(使用 cherry-pick 的场景)
  • 【MySQL事务】事务的隔离级别
  • 逆向破解京东评论加密参数|Python动态Cookie解决方案
  • 开源Agent平台Dify源码剖析系列(五)核心模块core/agent之CotChatAgentRunner
  • 文字转图片的字符画生成工具
  • 今日行情明日机会——20250717
  • Web3.0 实战项目、简历打造、精准投递+面试准备
  • springboot 整合spring-kafka客户端:SASL_SSL+PLAINTEXT方式
  • 流式数据处理实战:用状态机 + scan 优雅过滤 AI 响应中的 `<think>` 标签
  • 面试高频题 力扣 200.岛屿数量 洪水灌溉 深度优先遍历 暴力搜索 C++解题思路 每日一题
  • 【Lua】题目小练1
  • 50天50个小项目 (Vue3 + Tailwindcss V4) ✨ | GoodCheapFast(Good - Cheap - Fast三选二开关)
  • yolo8+ASR+NLP+TTS(视觉语音助手)
  • RK3566开发板调试记录:从编译配置到功能优化
  • 杰理AC70NN项目用脚本自定义添加.mk文件,直接链接进主Makefile脚本编译
  • 微服务的编程测评系统3-加密-日志-apifox-nacos-全局异常
  • 用Python实现神经网络(一)
  • RuoYi-Cloud 定制微服务
  • 微服务网站开发学习路线与RuoYi-Cloud实战指南
  • 迅速高效从web2到web3转型 ,开启远程工作
  • 验证损失判断过拟合情况
  • VTK体绘制中的抗锯齿技巧总结
  • LAMP迁移LNMP Nginx多站点配置全流程
  • AUTOSAR进阶图解==>AUTOSAR_SWS_BusMirroring
  • 线性回归策略
  • 水安考试:水利水电安全员 B 证考取指南及报考要求
  • OpenFeign的简单实践
  • C++11新特性(上)——右值引用,移动语义,引用折叠,完美转发,初始化列表,可变参数模版,lambda,包装器