二叉树详解-第四篇 二叉树链式结构的实现

目录

1.二叉树的遍历

1.1前序遍历：

1.2 中序遍历：

1.3 后序遍历：

2.二叉树链式结构的实现

2.1 Tree.h

2.2 Tree.cpp

2.2.1 前序遍历 void PreOrder(TNode* Root)

2.2.2 中序遍历 void InOrder(TNode* Root)

2.2.3 后序遍历 void BacOrder(TNode* Root)

2.2.4 求树的总节点数 int Treesize(TNode* root)

2.2.5 求叶子结点数 int Leafsize(TNode* root)

2.2.6 求树的高度 int Treeheight(TNode* root)

2.2.7 求二叉树第K层节点数 int Knum(TNode* root,int k)

2.2.8 查找节点为x值所在节点指针 TNode* Treefind(TNode* root, TreeType x)

1.二叉树的遍历

前序遍历：根 左子树 右子树

中序遍历：左子树 根 右子树

后序遍历：左子树 右子树 根

1.1前序遍历：

(根左右)

                                

                        图1                                                                              图2

首先我们要把所有子树空的地方写上N(代表NULL)，如图2。

1.首先从1开始出发，1作为根，2是1的左子树，4是1的右子树，输出1，然后进入2。

遍历序列：1 

2. 进入2后，2作为根，3作为2的左子树，N作为2的右子树，输出2，然后进入3。

遍历序列：1 2

3.进入3后，3作为根，N为3的左子树，N为3的右子树，输出3，然后进入左子树的N。

遍历序列：1 2 3

4.进入N后，遇到了N，就输出N，并返回到根(3)。

遍历序列：1 2 3 N

5.返回3后，根和左子树都已经输出，进入右子树的N。同时遇到了N打印并返回。

遍历序列：1 2 3 N N

6.再次返回到了3，根 左子树 右子树 都已经输出了，所以再次返回3的根(2)。返回2后，2作为根，2的左子树已经输出，所以进入2的右子树(N),因为右子树为N，所以输出N即可。

遍历序列：1 2 3 N N N

7. 2作为根，2的左子树右子树有已经输出了，返回2的根(1)。返回1后，1作为根，1的左子树已经输出，直接进入1的右子树(4)即可，进入4后，4作为根，先输出4，然后在进入4的左子树。

遍历序列：1 2 3 N N N 4

8.进入5后，5作为根，所以先输出5，然后进入5的左子树，左子树为N，输出N，然后进入5的右子树，右子树也为N，输出N。

遍历序列：1 2 3 N N N 4 5 N N 

9. 5和他的左子树右子树都已经输出，此时返回到5的根(4),4作为根，4的左子树已经输出，此时进入4的右子树(6) ,进入6后，6作为根，先输出6；输出6后进入6的左子树，左子树为N，输出N。然后进入6的右子树，右子树为N，输出N。

遍历序列：1 2 3 N N N 4 5 N N 6 N N

1.2 中序遍历：

(左根右)

                                 

                        图1                                                                              图2

1.首先进入1，1作为根，由于是左跟右，所以还不能输出1，要先进入1的左子树(2)，进入2后，2作为根，还要进入2的左子树(3)，进入3后，3作为根，要先进入3的左子树(N)，3的左子树为N，直接输出N，输出N后，左子树已经输出，3作为根，此时可以输出3，3输出后，在进入3的右子树，3的右子树为N，输出N即可。

遍历序列：N 3 N 

2. 3作为根的子树已经全部输出，此时返回到3的根(2),2作为根，2的左子树(3)已经输出，此时输出根(2),输出根后，再输出2的右子树(N)，右子树为N，直接输出N。

遍历序列：N 3 N 2 N 

3. 2作为根的子树已经全部输出，此时返回到2的根(1)，1作为根，1的左子树(2)已经输出，此时输出根(1),输出根后，再进入右子树(4)，4作为根，要先进入4的左子树(5)，5作为根，5的左子树为N，直接输出N，输出N后再输出根(5)，输出5，输出5后再进入5的右子树(N),输出N；

遍历序列：N 3 N 2 N 1 N 5 N 

4.  5的子树全部输出，此时返回到5的根(4)，4作为根，4的左子树(5)输出，此时可以输出根(4)，输出根后，再进入根的右子树(6)，6作为根，要先进入6的左子树，左子树为N，输出N，然后返回到根(6)，此时输出根(6)，输出根后，进入6的右子树，右子树为N，输出N。

遍历序列：N 3 N 2 N 1 N 5 N 4 N 6 N

1.3 后序遍历：

(左右根)

                                 

                        图1                                                                              图2

1.首先进入1，1作为根，先进入1的左子树(2)，2作为根，先进入2的左子树(3)，3作为根，先进入3的左子树(N)，输出N并返回到根(3)，再进入3的右子树(N)，输出N并返回到根(3)，3作为根，3的左子树和右子树都已经输出，所以此时输出3，输出3后返回到3的根(2)。

遍历序列：N N 3

2. 进入2后，2作为根，2的左子树已经输出，再进入2的右子树，2的右子树为N， 输出N并且返回到根，2作为根，2的左子树和右子树都已经输出，此时可以输出根(2)，输出2并且返回2的根(1)。

遍历序列：N N 3 N 2 

3.进入1后，1作为根，1的左子树已经输出，再进入1的右子树(4)，4作为根，先进入4的左子树(5)，5作为根，先进入5的左子树(N)，左子树为N，输出N并且返回到根(5)，5作为根，再进入5的右子树，5的右子树为N，输出N并返回到根，5的左子树和右子树都已经输出，此时输出5并且返回到5的根(4)。

遍历序列：N N 3 N 2 N N 5

4. 进入4后，4作为根，4的左子树已经输出，进入4的右子树(6)，6左右根，先进入6的左子树N，输出N并返回到根，再进入6的右子树N，输出N并返回到根。6作为根，其左子树和右子树都已经输出，此时输出6并且返回到6的根(4)，4作为根，4的左子树和右子树都已经输出，此时输出4并且返回到4的根(1)。

遍历序列：N N 3 N 2 N N 5 N N 6 4

5.进入1后，1作为根，1的左子树和右子树都已经输出，此时输出1。

遍历序列：N N 3 N 2 N N 5 N N 6 4 1

2.二叉树链式结构的实现

2.1 Tree.h

源码：

#define _CRT_SECURE_NO_WARNINGS 1#pragma once
#include<iostream>
#include<algorithm>
using namespace std;typedef int TreeType;typedef struct Tree
{TreeType val;struct Tree* left;struct Tree* right;
}TNode;void PreOrder(TNode* root);//前序遍历
void InOrder(TNode* Root);//中序遍历
void BacOrder(TNode* Root);//后序遍历
int Treesize(TNode* root);//求节点数
int Leafsize(TNode* root);//求叶子节点数
int Treeheight(TNode* root);//求树高度
int Knum(TNode* root, int k);//第K层结点数
TNode* Treefind(TNode* root, TreeType x);//查找节点为x值所在节点指针

2.2 Tree.cpp

源码：

#include"Tree.h"void PreOrder(TNode* Root)
{if (Root == NULL){cout << "N ";return;}cout << Root->val << " ";PreOrder(Root->left);PreOrder(Root->right);}void InOrder(TNode* Root)
{if (Root == NULL){cout << "N ";return;}InOrder(Root->left);cout << Root->val << " ";InOrder(Root->right);}void BacOrder(TNode* Root)
{if (Root == NULL){cout << "N ";return;}BacOrder(Root->left);BacOrder(Root->right);cout << Root->val << " ";
}int Treesize(TNode* root)//求节点数
{if (root == NULL){return 0;}else{return Treesize(root->left) + Treesize(root->right) + 1;}}int Leafsize(TNode* root)//求叶子节点数
{if (root == NULL) {return 0;}if (root->left == root->right == NULL) {return 1;}return Leafsize(root->left) + Leafsize(root->right);}int Treeheight(TNode* root)//求树高度
{if (root == NULL) {return 0;}int leftnum = Treeheight(root->left);int rightnum = Treeheight(root->right);return leftnum > rightnum ? leftnum + 1 : rightnum + 1;}int Knum(TNode* root,int k)//二叉树第k层节点个数
{if (root == NULL){return 0;}if (k == 1){return 1;}return Knum(root->left,k-1) + Knum(root->right,k-1);}TNode* Treefind(TNode* root, TreeType x)//查找节点为x值所在节点指针
{if (root == NULL) {return NULL;}if (root->val == x) {return root;}TNode* ret1 = Treefind(root->left, x);if (ret1) {return ret1;}TNode* ret2 = Treefind(root->right, x);if (ret2) {return ret2;}return NULL;}

2.2.1 前序遍历 void PreOrder(TNode* Root)

void PreOrder(TNode* Root)
{if (Root == NULL){cout << "N ";return;}cout << Root->val << " ";PreOrder(Root->left);PreOrder(Root->right);}

1.先输出节点的值，再进行左子树遍历和右子树遍历

2.2.2 中序遍历 void InOrder(TNode* Root)

void InOrder(TNode* Root)
{if (Root == NULL){cout << "N ";return;}InOrder(Root->left);cout << Root->val << " ";InOrder(Root->right);}

1.先递归左子树，在输出节点值，再递归右子树。

2.2.3 后序遍历 void BacOrder(TNode* Root)

void BacOrder(TNode* Root)
{if (Root == NULL){cout << "N ";return;}BacOrder(Root->left);BacOrder(Root->right);cout << Root->val << " ";
}

1.先递归左子树和右子树，最后输出节点值。

2.2.4 求树的总节点数 int Treesize(TNode* root)

int Treesize(TNode* root)//求节点数
{if (root == NULL){return 0;}else{return Treesize(root->left) + Treesize(root->right) + 1;}}

1.如果遇到空节点(N),就返回0，其余情况返回左右子树递归+1。

2.2.5 求叶子结点数 int Leafsize(TNode* root)

int Leafsize(TNode* root)//求叶子节点数
{if (root == NULL) {return 0;}if (root->left == root->right == NULL) {return 1;}return Leafsize(root->left) + Leafsize(root->right);}

1.遇到空节点就返回0。

2.叶子节点的特点是其左右孩子都为空，则当if (root->left == root->right == NULL)成立时，返回1.

3.其余情况返回左子树递归+右子树递归。

2.2.6 求树的高度 int Treeheight(TNode* root)

int Treeheight(TNode* root)//求树高度
{if (root == NULL) {return 0;}int leftnum = Treeheight(root->left);int rightnum = Treeheight(root->right);return leftnum > rightnum ? leftnum + 1 : rightnum + 1;}

1.当为空节点时，返回0。

2.用leftnum存储左子树的层数，用rightnum存储右子树的层数，两者返回最大者+1.

2.2.7 求二叉树第K层节点数 int Knum(TNode* root,int k)

int Knum(TNode* root,int k)//二叉树第k层节点个数
{if (root == NULL){return 0;}if (k == 1){return 1;}return Knum(root->left,k-1) + Knum(root->right,k-1);}

1.如果时空节点，则返回0。

2.当k==1时，则此时在第K层的某个节点上，则返回1即可。

3.其余情况返回Knum(root->left,k-1) + Knum(root->right,k-1)。

2.2.8 查找节点为x值所在节点指针 TNode* Treefind(TNode* root, TreeType x)

TNode* Treefind(TNode* root, TreeType x)//查找节点为x值所在节点指针
{if (root == NULL) {return NULL;}if (root->val == x) {return root;}TNode* ret1 = Treefind(root->left, x);if (ret1) {return ret1;}TNode* ret2 = Treefind(root->right, x);if (ret2) {return ret2;}return NULL;}

1.如果当前节点的值等于要查找的值，则返回该节点的地址。

2.用ret1和ret2接收Treefind(root->left, x)的返回值和Treefind(root->right, x)的返回值，如果其中有一个不为空指针，则说明找到了，就立马返回这个地址。

3.其余情况返回NULL即可。

本篇完

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

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

相关文章

基于opencv[python]的人脸检测

基于opencv[python]的人脸检测

1 图片爬虫 这里的代码转载自&#xff1a;http://t.csdnimg.cn/T4R4F # 获取图片数据 import os.path import fake_useragent import requests from lxml import etree# UA伪装 head {"User-Agent": fake_useragent.UserAgent().random}pic_name 0 def request_pic…
阅读更多...
DVWA的安装和使用

DVWA的安装和使用

背景介绍 DVWA是Damn Vulnerable Web Application的缩写&#xff0c;是一个用于安全脆弱性检测的开源Web应用。它旨在为安全专业人员提供一个合法的测试环境&#xff0c;帮助他们测试自己的专业技能和工具&#xff0c;同时也帮助web开发者更好地理解web应用安全防范的过程。DV…
阅读更多...
微信小程序-本地部署(前端）

微信小程序-本地部署(前端）

遇到问题&#xff1a;因为是游客模式所以不能修改appID. 参考链接&#xff1a;微信开发者工具如何从游客模式切换为开发者模式&#xff1f;_微信开发者工具如何修改游客模式-CSDN博客 其余参考&#xff1a;Ego微商项目部署&#xff08;小程序项目&#xff09;&#xff08;全网…
阅读更多...
Wonder3D 论文学习

Wonder3D 论文学习

论文链接&#xff1a;https://arxiv.org/abs/2310.15008 代码链接&#xff1a;https://github.com/xxlong0/Wonder3D 解决了什么问题&#xff1f; 随着扩散模型的提出&#xff0c;3D 生成领域取得了长足进步。从单张图片重建出 3D 几何是计算机图形学和 3D 视觉的基础任务&am…
阅读更多...
k8s安装

k8s安装

说明 本事件适合刚刚装系统的新机子&#xff0c;前提是可以ping通www.baidu。yum可以下载软件 本实验模拟单机k8s&#xff0c;主机ip为172.26.50.222 关闭防火墙 systemctl status firewalld systemctl stop firewalld systemctl disable firewalld getenforce setenforce …
阅读更多...
【React】详解样式控制：从基础到进阶应用的全面指南

【React】详解样式控制：从基础到进阶应用的全面指南

文章目录 一、内联样式1. 什么是内联样式&#xff1f;2. 内联样式的定义3. 基本示例4. 动态内联样式 二、CSS模块1. 什么是CSS模块&#xff1f;2. CSS模块的定义3. 基本示例4. 动态应用样式 三、CSS-in-JS1. 什么是CSS-in-JS&#xff1f;2. styled-components的定义3. 基本示例…
阅读更多...
llama模型，nano

llama模型，nano

目录 llama模型 Llama模型性能评测 nano模型是什么 Gemini Nano模型 参数量 MMLU、GPQA、HumanEval 1. MMLU（Massive Multi-task Language Understanding） 2. GPQA（Grade School Physics Question Answering） 3. HumanEval llama模型 Large Language Model AI Ll…
阅读更多...
【React】详解 Redux 状态管理

【React】详解 Redux 状态管理

文章目录 一、Redux 的基本概念1. 什么是 Redux&#xff1f;2. Redux 的三大原则 二、Redux 的核心组件1. Store2. Action3. Reducer 三、Redux 的使用流程1. 安装 Redux 及其 React 绑定2. 创建 Action3. 创建 Reducer4. 创建 Store5. 在 React 应用中使用 Store6. 连接 React…
阅读更多...
【Redis】主从复制分析-基础

【Redis】主从复制分析-基础

1 主从节点运行数据的存储 在主从复制中, 对于主节点, 从节点就是自身的一个客户端, 所以和普通的客户端一样, 会被组织为一个 client 的结构体。 typedef struct client {// 省略 } client;同时无论是从节点, 还是主节点, 在运行中的数据都存放在一个 redisServer 的结构体中…
阅读更多...
使用C#手搓Word插件

使用C#手搓Word插件

WordTools主要功能介绍 编码语言&#xff1a;C#【VSTO】 1、选择 1.1、表格 作用&#xff1a;全选文档中的表格&#xff1b; 1.2、表头 作用&#xff1a;全选文档所有表格的表头【第一行】&#xff1b; 1.3、表正文 全选文档中所有表格的除表头部分【除第一行部分】 1.…
阅读更多...
Vue常用指令及其生命周期

Vue常用指令及其生命周期

作者&#xff1a;CSDN-PleaSure乐事 欢迎大家阅读我的博客 希望大家喜欢 目录 1.常用指令 1.1 v-bind 1.2 v-model 注意事项 1.3 v-on 注意事项 1.4 v-if / v-else-if / v-else 1.5 v-show 1.6 v-for 无索引 有索引 生命周期 定义 流程 1.常用指令 Vue当中的指令…
阅读更多...
福派斯牛肉高脂猫粮，为何成猫舍首选？揭秘其神奇功效！

福派斯牛肉高脂猫粮，为何成猫舍首选？揭秘其神奇功效！

&#x1f43e; 说到猫咪的伙食&#xff0c;咱们当铲屎官的可是操碎了心&#xff01;想让自家毛孩子吃得健康又开心&#xff0c;选对猫粮真的太重要了。今天就来聊聊为啥福派斯牛肉高脂猫粮能成为众多猫舍的首选&#xff0c;以及它到底能帮咱们的小猫咪哪些忙吧&#xff01; 1️…
阅读更多...
数据传输安全--SSL VPN

数据传输安全--SSL VPN

目录 IPSEC在Client to LAN场景下比较吃力的表现 SSL VPV SSL VPN优势 SSL协议 SSL所在层次 SSL工作原理 SSL握手协议、SSL密码变化协议、SSL警告协议三个协议作用 工作过程 1、进行TCP三次握手、建立网络连接会话 2、客户端先发送Client HELLO包&#xff0c;下图是包…
阅读更多...
springboot项目从jdk8升级为jdk17过程记录

springboot项目从jdk8升级为jdk17过程记录

背景&#xff1a;公司有升级项目jdk的规划&#xff0c;计划从jdk8升级到jdk11 开始 首先配置本地的java_home 参考文档&#xff1a;Mac环境下切换JDK版本及不同的maven-CSDN博客 将pom.xml中jdk1.8相关的版本全部改为jdk17&#xff0c;主要是maven编译插件之类的&#xff0c…
阅读更多...
ubuntu22.04 安装 NVIDIA 驱动以及CUDA

ubuntu22.04 安装 NVIDIA 驱动以及CUDA

目录 1、事前问题解决 2、安装 nvidia 驱动 3、卸载 nvidia 驱动方法 4、安装 CUDA 5、安装 Anaconda 6、安装 PyTorch 1、事前问题解决 在安装完ubuntu之后&#xff0c;如果进入ubuntu出现黑屏情况&#xff0c;一般就是nvidia驱动与linux自带的不兼容&#xff0c;可以通…
阅读更多...
找工作准备刷题Day10 回溯算法 (卡尔41期训练营 7.24）

找工作准备刷题Day10 回溯算法 (卡尔41期训练营 7.24）

回溯算法今天这几个题目做过&#xff0c;晚上有面试&#xff0c;今天水一水。 第一题&#xff1a;Leetcode77. 组合 题目描述 解题思路 从题目示例来看&#xff0c;k个数是不能重合的&#xff0c;但是题目没有明确说明这一点。 使用回溯算法解决此问题&#xff0c;利用树形…
阅读更多...
数据结构 —— B+树和B*树及MySQL底层引擎

数据结构 —— B+树和B*树及MySQL底层引擎

数据结构 —— B树和B*树及MySQL底层引擎 B树B*树B树的应用B树在MySQL中的应用MyISAMInnoDB 我们之前学习了B树的基本原理&#xff0c;今天我们来看看B树的一些改良版本——B树和B*树。如果还没有了解过的小伙伴可以点击这里&#xff1a; https://blog.csdn.net/qq_67693066/ar…
阅读更多...
【MySQL进阶之路 | 高级篇】MVCC三剑客：隐藏字段，Undo Log，ReadView

【MySQL进阶之路 | 高级篇】MVCC三剑客：隐藏字段，Undo Log，ReadView

1. 再谈隔离级别 我们知道事务有四个隔离级别&#xff0c;可能存在三种并发问题&#xff1a; 在MySQL中&#xff0c;默认的隔离级别是可重复读&#xff0c;可以解决脏读和不可重复读的问题&#xff0c;如果仅从定义的角度来看&#xff0c;它并不能解决幻读问题。如果我们想要解…
阅读更多...
Nacos-2.4.0最新版本docker镜像，本人亲自制作，部署十分方便，兼容postgresql最新版本17和16，奉献给大家了

Nacos-2.4.0最新版本docker镜像，本人亲自制作，部署十分方便，兼容postgresql最新版本17和16，奉献给大家了

基于Postgresql数据库存储的nacos最新版本2.4.0，采用docker镜像安装方式 因业务需要，为了让nacos支持postgresql，特意花了两天时间修改了源码，然后制作了docker镜像，如果你也在找支持postgresql的nacos最新版本，恭喜你，你来的正好~ nacos-2.4.0 postgresql的数据库脚本…
阅读更多...
安宝特方案｜解放双手，解决死角，AR带来质量监督新体验

安宝特方案｜解放双手，解决死角，AR带来质量监督新体验

AR质量监督 解放双手&#xff0c;解决死角 在当今制造业快速发展的背景下&#xff0c;质量监督成为确保产品高质量和完善的管理制度的关键环节。然而&#xff0c;传统的质量监督方式存在诸多挑战&#xff0c;如人工操作带来的效率低下、查岗不及时、摄像头死角等问题。 为了解…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023