二叉树的链式结构和递归程序的递归流程图

二叉树的链式存储结构是指,用链表来表示一棵二叉树,即用链来指示元素的逻辑关系。 通常的方法是链表中每个结点由三个域组成,数据域和左右指针域,左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址 。链式结构又分为二叉链和三叉链,当前学习二叉链。
在这里插入图片描述
普通二叉树的增删查改没有意义。如果是为了存储数据,线性表更简单,二叉树更复杂,并且插入删除也不好定义。有意义的是通过二叉树引出搜索树,搜索树又有AVL树和红黑树。再搜索树中查找一个节点最多找高度次。

深度优先:前中后序遍历 一般借助递归
广度优先:层序遍历 一般借助队列

typedef char BTDataType;
typedef struct BinaryTreeNode
{BTDataType data;struct BinaryTreeNode* left;struct BinaryTreeNode* right;
}BTNode;// 二叉树前序遍历 递归
void PrevOrder(BTNode* root)
{if(root == NULL){printf("NULL ");return;}// 根 左 右子树 递归 递归过程图在下方printf("%c ",root->data);PrevOrder(root->left);PrevOrder(root->right);
}// 二叉树中序遍历
void InOrder(BTNode* root)
{if(root == NULL){printf("NULL ");return;}// 左 根 右子树 递归 递归过程图在下方InOrder(root->left);printf("%c ",root->data);InOrder(root->right);
}// 二叉树后序遍历
void PostOrder(BTNode* root)
{if(root == NULL){printf("NULL ");return;}// 左 右 根 递归 递归过程图在下方PostOrder(root->left);PostOrder(root->right);printf("%c ",root->data);
}
// 求节点的个数
int TreeSize(BTNode* root)
{// root不是NULL,则个数为左节点个数+右节点个数+1(加的1就是对本节点个数加上去)return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;
}
// 求叶子结点的个数 
// 1.NULL return 0 2.叶子 return 1 3.非空且不是叶子 reutrn 左子树叶子节点个数+右子树叶子节点个数
int TreeLeefSize(BTNode* root)
{if(root == NULL)return 0;if(root->left == NULL && root->right == NULL)return 1;return TreeLeefSize(root->left) + root->left(root->right);
}
// 求第K层节点的个数 设K=3 化解为左子树的第K-1(2)层和右子树的第k -1(2)层
int TreeKLeefSize(BTNode* root, int k)
{if(root == NULL)return 0;if(k == 1)return 1;return TreeKLeefSize(root->left, k-1) + TreeKLeefSize(root->right, k-1);
}
// 查找树里面值为X的那个节点 1.root == NULL return NULL 
// 2.root 不是要找的 先找左树 左树如果没有再找右树 3.左右都没有则当前树没找到 return null
BTNode* TreeFind(BTNode* root, BTDataType x)
{if(root == NULL)return NULL;// 我就是x则返回if(root->data == x){return root;}// 不是x先在左边找再在右边找BTNode* lret = TreeFind(root->left, x); // 找到了返回root 没找到返回NULLif(lret)return lret;BTNode* rret = TreeFind(root->right, x); // 找到了返回root 没找到返回NULLif(rret)return rret;// 左右都没找到return NULL;
}
// 二叉树销毁 形参的改变不会影响实参,因此需要二级指针
void BinaryTreeDestory(BTNode** pproot)
{// if(*pproot == NULL)// 	return;// BinaryTreeDestory(&(*pproot)->left); //先将二级指针转换为一级再取地址变为2级传参// BinaryTreeDestory(&(*pproot)->right);// free(*pproot);// *pproot== NULL;
}
// 一级指针的做法 存在野指针,需要将野指针置空 保持接口一致性
void BinaryTreeDestory(BTNode* root)
{if(root == NULL)return;BinaryTreeDestory(root->left); //先将二级指针转换为一级再取地址变为2级传参BinaryTreeDestory(root->right);free(root);
}
// 创建节点
BTNode* CreateTreeNode (BTDataType x)
{BTNode* n1 = (BTNode*)malloc(sizeof(BTNode));n1->data = x;n1->left = NULL;n1->right = NULL:return node;
}
int main()
{// 手动连接上图中的树BTNode* A = CreateTreeNode('A');BTNode* B = CreateTreeNode('B');BTNode* C = CreateTreeNode('C');BTNode* D = CreateTreeNode('D');BTNode* E = CreateTreeNode('E');BTNode* F = CreateTreeNode('F');A->left = B;A->right = C;B->left = D;C->left = E;c->right = F;// 二级做法BinaryTreeDestory(&A);// 一级做法BinaryTreeDestory(A);A = NULL;
}

下图为PrevOrder的递归过程图。函数调用该板块完成后会返回到使用该板块的语句。前中后序的本质是一样的,就是打印的时机不同。
在这里插入图片描述

  1. 求节点的个数(前序) 1+左树节点个数+右树节点个数
  2. 求树的高度(后序) max(左树的高度,右树的高度)+1

深度优先:前中后序遍历 一般借助递归
广度优先:层序遍历 一般借助队列

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

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

相关文章

基于Linux系统离线安装oracle数据库

注意事项: 在安装的时候多次涉及root用户和oracle用户的切换,请注意区分,本文已明显 一、环境准备 1、关闭防火墙 [rootlocalhost ~]# systemctl stop firewalld2、 禁用NetworkManager服务(非必须) [rootlocalhost …

STM32—I2C通信外设

1.I2C外设简介 STM32内部集成了硬件I2C收发电路,可以由硬件自动执行时钟生成、起始终止条件生成、应答位收发、数据收发等功能,减轻CPU的负担支持多主机模型(可变多主机)支持7位/10位地址模式(11110......)支持不同的通…

C++:布尔类型,引用,堆区空间

1.布尔类型 #include <iostream>using namespace std;int main() {bool b13;bool b20;cout << "b1" <<b1<< endl;cout << "b2" <<b2<< endl;cout <<boolalpha<< "b1" <<b1<<…

Java语言程序设计基础篇_编程练习题*18.29(某个目录下的文件数目)

题目&#xff1a;*18.29(某个目录下的文件数目) 编写一个程序&#xff0c;提示用户输入一个目录&#xff0c;然后显示该目录下的文件数。 和上一题(18.28)的思路差不多&#xff0c;把找到文件后累加大小到变量变成计数1即可。 Java语言程序设计基础篇_编程练习题*18.28 (非递…

3D点云目标检测数据集标注工具 保姆级教程——CVAT (附json转kitti代码)

前言&#xff1a; 笔者尝试过很多3D标注软件都遇到很多问题&#xff0c;例如CloudCompare不适合做3D目标检测的数据集而且分割地面的时很繁琐&#xff1b;labelCloud没有三视图&#xff0c;视角难以调整标得不够精确&#xff1b;SUSTechPOINTS换帧麻烦、输出时存储在docker里面…

【读书笔记-《30天自制操作系统》-22】Day23

本篇内容比较简单&#xff0c;集中于显示问题。首先编写了应用程序使用的api_malloc&#xff0c;然后实现了在窗口中画点与画线的API与应用程序。有了窗口显示&#xff0c;还要实现关闭窗口的功能&#xff0c;于是在键盘输入API的基础上实现了按下按键关闭窗口。最后发现用上文…

诗文发布模板(python代码打造键盘录入诗文自动排版,MarkDown源码文本)

python最好用的f-string&#xff0c;少量代码打造键盘录入诗文自动排版。 (笔记模板由python脚本于2024年09月19日 19:11:50创建&#xff0c;本篇笔记适合喜欢写诗的pythoner的coder翻阅) 【学习的细节是欢悦的历程】 Python 官网&#xff1a;https://www.python.org/ Free&am…

Apache subversion 编译流程

目录 1. 概述2. 依赖库简介2.1 Expat2.2 Apache apr2.3 Apache apr-iconv2.4 Apache apr-util2.5 Zlib2.6 OpenSSL2.7 Sqlite2.8 Apache Serf2.9 Apache subversion3. 编译3.1 Expat编译3.1.1 源码信息3.1.2 CMake-GUI3.1.3 编译步骤3.2 APR编译3.2.1 源码信息3.2.2 编译步骤3.…

【笔记】2.1 半导体三极管(BJT,Bipolar Junction Transistor)

一、结构和符号 1. 三极管结构 常用的三极管的结构有硅平面管和锗合金管两种类型。各有PNP型和NPN型两种结构。 左图是NPN型硅平面三极管,右图是PNP型锗合金三极管。 从图中可见平面型三极管是先在一块大的金属板上注入杂质使之变成N型,然后再在中间注入杂质使之变成P型,…

倒序循环(一)

题目描述 输入一个正整数n&#xff0c;输出从 n~ 1 递减的序列。 输入格式 一行一个整数 n 输出格式 n 行&#xff0c;每行一个符合题目要求的整数 样例数据 样例输入#1 5样例输出#1 5 4 3 2 1样例输入#2 6样例输出#2 6 5 4 3 2 1数据范围 对于100%的数据&#xff…

Java企业面试题2

1.语言的分代&#xff1a; 第1代&#xff1a;机器语言 机器语言是最底层的计算机编程语言&#xff0c;它是由二进制数构成的一系列指令&#xff0c;直接与计算机硬件交互。每个二进制位模式代表一条特定的指令或数据地址。因为它是直接在硬件上执行的&#xff0c;所以运行效率…

Java 23 的12 个新特性!!

Java 23 来啦&#xff01;和 Java 22 一样&#xff0c;这也是一个非 LTS&#xff08;长期支持&#xff09;版本&#xff0c;Oracle 仅提供六个月的支持。下一个长期支持版是 Java 25&#xff0c;预计明年 9 月份发布。 Java 23 一共有 12 个新特性&#xff01; 有同学表示&…

xmake与包管理:又一个现代c++构建工具?

个人博客:Sekyoro的博客小屋 个人网站:Proanimer的个人网站 主要起因是我在逛Reddit帖子时,看到关于一些c构建系统的评价. cmake似乎有些过于复杂,它与vcpkg,conan的包管理之间的"融合"可能在有些时候也显得麻烦. 一些人尝试了我没见过的选项, 所以这里主要试试除了…

Java重修笔记 第五十七天 坦克大战(七)多线程基础 - 编程练习

1. 线程之间的协调控制&#xff08;通知方式&#xff09; public class Homework04 {public static void main(String[] args) {// 在 main 方法中启动两个线程// 第一个线程内循环打印 1 到 100 以内的整数// 直到第二个线程从键盘读取到 "Q" 指令后结束第一个线程…

深入剖析大模型原理——Qwen Blog

1. 输入部分 Text&#xff1a;原始输入文本&#xff0c;模型需要处理的自然语言数据。Tokenizer&#xff1a;分词器&#xff0c;将输入文本转换为词汇表中的索引&#xff08;ID&#xff09;&#xff0c;便于后续处理。Input_ids&#xff1a;经过分词处理后的ID序列&#xff0c…

交流回馈老化测试负载的智能升级

在电子设备的生产过程中&#xff0c;老化测试是不可或缺的环节。老化测试主要是通过模拟设备长时间工作的情况&#xff0c;检测设备在经过一定时间的使用后&#xff0c;其性能是否会发生降低&#xff0c;是否存在安全隐患等。老化测试负载是老化测试中的重要组成部分&#xff0…

今日所学啊

ArcGIS打不开焦点统计如何解决_arcgis焦点统计打不开-CSDN博客 好吧其实最后焦点统计还是不行&#xff0c;我就去ArcGIS Pro里做焦点统计了哈哈哈哈哈哈哈 visual studio多工程项目管理_visual studio 的模块管理-CSDN博客 1.今天成功#include <QNetworkReply>不画红线…

【MYSQL表的增删改查(基础)】

MYSQL表的增删改查&#xff08;基础&#xff09; 一、CRUD二、新增&#xff08;Create&#xff09;2.1 单行数据全列插入2.2 多行数据指定列插入 三、查询&#xff08;Retrieve&#xff09;3.1 全列查询3.2 指定列查询3.3 查询字段为表达式3.3.1 表达式不包含字段3.3.2 表达式包…

react是什么?

文章目录 核心特点1. **组件化**2. **虚拟 DOM** 3. **声明式编程**4. **单向数据流**5. **JSX 语法**6. **Hooks** react的优势劣势 React 是一个由 Facebook 开发和维护的开源 JavaScript 库&#xff0c;用于构建用户界面&#xff0c;特别是单页应用程序&#xff08;SPA&…

[PICO VR眼镜]眼动追踪串流Unity开发与使用方法,眼动追踪打包报错问题解决(Eye Tracking/手势跟踪)

前言 最近在做一个工作需要用到PICO4 Enterprise VR头盔里的眼动追踪功能&#xff0c;但是遇到了如下问题&#xff1a; 在Unity里面没法串流调试眼动追踪功能&#xff0c;根本获取不到Device&#xff0c;只能将整个场景build成APK&#xff0c;安装到头盔里&#xff0c;才能在…