5.数据结构-c/c++二叉树详解(上篇)(遍历方法,完全二叉树)

2024-09-03 02:20

本文主要是介绍5.数据结构-c/c++二叉树详解(上篇)(遍历方法,完全二叉树),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

目录

一. 二叉树的基本介绍

1.2 满二叉树

1.3 完全二叉树

1.4 搜索二叉树

1.5 平衡二叉搜索树

二. 二叉树的常用操作

2.1 二叉树的定义

2.2 创建一个新的节点

2.3 构建一颗树

2.5 销毁一棵树

三.二叉树的前序,中序,后序,层序遍历方法

3.1 前序遍历

3.2 中序遍历

3.3 后序遍历

3.4 层序遍历

四.下篇内容(算法面试题)


一. 二叉树的基本介绍

        二叉树是一种每一个节点最多只有两个子树的树结构。

树的5种基本结构如下图

几种特殊的二叉树结构

1.2 满二叉树

        二叉树的每一层是满的,节点数量为2*h-1        h为树的高度

下图两种树都为满二叉树

1.3 完全二叉树

        在一颗二叉树中,只有最后两层节点的度小于2,且所有的叶子节点都依次集中在左侧

1.4 搜索二叉树

在一颗二叉树中,该树可以为空。如果不为空,则要满足下列条件

1.树中的每一个子树的左子树都小于其根节点

2.树中每一颗子树的右子树都大于其根节点

3.所有子树都是二叉搜索树

1.5 平衡二叉搜索树

       1. 二叉搜索树的左右子树高度差不超过1

       2.左右子树都是二叉搜索树

       3.节点中包含平衡因子

满足以上三点的二叉搜索树就是平衡二叉搜索树

二. 二叉树的常用操作

2.1 二叉树的定义

//定义节点
typedef int BTDataType;typedef struct BinaryTreeNode
{BTDataType data;struct BinaryTreeNode* left;struct BinaryTreeNode* right;
}BTNode;

2.2 创建一个新的节点

//创建一个新节点
BTNode* CreatNode(int x)
{BTNode* node = (BTNode*)malloc(sizeof(BTNode));assert(node);//更新节点的值,并将左右指针置空node->data = x;node->left = nullptr;node->right = nullptr;return node;
}

2.3 构建一颗树

	//根据需求依次构建节点并连接即可BTNode* A = CreatNode('A');BTNode* B = CreatNode('B');BTNode* C = CreatNode('C');BTNode* D = CreatNode('D');BTNode* E = CreatNode('E');BTNode* F = CreatNode('F');BTNode* G = CreatNode('G');A->left = B;A->right = C;B->left = D;B->right = E;C->left = F;C->right= G;

2.5 销毁一棵树

利用前序遍历,依次释放每一个节点即可

//销毁一棵树//使用后续销毁
void TreeDestory(BTNode* root)
{if (root == NULL)return;TreeDestory(root->left);TreeDestory(root->right);free(root);
} 

三.二叉树的前序,中序,后序,层序遍历方法

3.1 前序遍历

利用递归思想,要访问一棵树的所有节点,访问根节点后,访问子树的节点

//前序遍历
void PrevOrder(BTNode* root)
{if (root == nullptr){cout << "NULL ";return;}cout << root->data << " ";	//访问根节点PrevOrder(root->left);		//访问左子树PrevOrder(root->right);		//访问右子树
}

3.2 中序遍历

//中序遍历
void InOrder(BTNode* root)
{if (root == nullptr){cout << "NULL ";return;}//中序遍历前访问左子树,再访问根节点,最后访问右子树InOrder(root->left);		//访问左子树cout << (char)root->data << " ";	//访问根节点InOrder(root->right);		//访问右子树
}

3.3 后序遍历

//后序遍历
void NextOrder(BTNode* root)
{if (root == nullptr){cout << "NULL ";return;}//后序遍历先访问左子树,在访问右子树。最后访问根节点NextOrder(root->left);		//访问左子树NextOrder(root->right);		//访问右子树cout << (char)root->data << " ";	//访问根节点
}

3.4 层序遍历

利用队列的先进先出特点。

将一层的节点都放入队列中,然后依次访问队首的数据并将其左右子节点放入队列中

如下图

代码 

//层序遍历(广度优先遍历),该遍历需要我们使用到队列先进先出的特点
void TreeLeverOrder(BTNode* root)
{if (root == nullptr){return;}queue<BTNode*> q;q.push(root);while (!q.empty()){BTNode* front = q.front();if (front->left){q.push(front->left);}if (front->right){q.push(front->right);}cout << (char)q.front()->data << " ";q.pop();}cout << endl;
}

四.下篇内容(算法面试题)

求二叉树 第k层的节点

查找一个节点是否在二叉树中

求二叉树节点的个数

求二叉树叶子节点的个数

求树的深度

判断一棵树是否为完全二叉树

这篇关于5.数据结构-c/c++二叉树详解(上篇)(遍历方法,完全二叉树)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

Java实现优雅日期处理的方案详解

《Java实现优雅日期处理的方案详解》在我们的日常工作中,需要经常处理各种格式,各种类似的的日期或者时间,下面我们就来看看如何使用java处理这样的日期问题吧,感兴趣的小伙伴可以跟随小编一起学习一下... 目录前言一、日期的坑1.1 日期格式化陷阱1.2 时区转换二、优雅方案的进阶之路2.1 线程安全重构2

Java中的JSONObject详解

《Java中的JSONObject详解》:本文主要介绍Java中的JSONObject详解,需要的朋友可以参考下... Java中的jsONObject详解一、引言在Java开发中,处理JSON数据是一种常见的需求。JSONObject是处理JSON对象的一个非常有用的类,它提供了一系列的API来操作J

Python中__init__方法使用的深度解析

《Python中__init__方法使用的深度解析》在Python的面向对象编程(OOP)体系中,__init__方法如同建造房屋时的奠基仪式——它定义了对象诞生时的初始状态,下面我们就来深入了解下_... 目录一、__init__的基因图谱二、初始化过程的魔法时刻继承链中的初始化顺序self参数的奥秘默认

HTML5中的Microdata与历史记录管理详解

《HTML5中的Microdata与历史记录管理详解》Microdata作为HTML5新增的一个特性,它允许开发者在HTML文档中添加更多的语义信息,以便于搜索引擎和浏览器更好地理解页面内容,本文将探... 目录html5中的Mijscrodata与历史记录管理背景简介html5中的Microdata使用M

html5的响应式布局的方法示例详解

《html5的响应式布局的方法示例详解》:本文主要介绍了HTML5中使用媒体查询和Flexbox进行响应式布局的方法,简要介绍了CSSGrid布局的基础知识和如何实现自动换行的网格布局,详细内容请阅读本文,希望能对你有所帮助... 一 使用媒体查询响应式布局        使用的参数@media这是常用的

HTML5表格语法格式详解

《HTML5表格语法格式详解》在HTML语法中,表格主要通过table、tr和td3个标签构成,本文通过实例代码讲解HTML5表格语法格式,感兴趣的朋友一起看看吧... 目录一、表格1.表格语法格式2.表格属性 3.例子二、不规则表格1.跨行2.跨列3.例子一、表格在html语法中,表格主要通过< tab

Spring 基于XML配置 bean管理 Bean-IOC的方法

《Spring基于XML配置bean管理Bean-IOC的方法》:本文主要介绍Spring基于XML配置bean管理Bean-IOC的方法,本文给大家介绍的非常详细,对大家的学习或工作具有一... 目录一. spring学习的核心内容二. 基于 XML 配置 bean1. 通过类型来获取 bean2. 通过

Linux之计划任务和调度命令at/cron详解

《Linux之计划任务和调度命令at/cron详解》:本文主要介绍Linux之计划任务和调度命令at/cron的使用,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录linux计划任务和调度命令at/cron一、计划任务二、命令{at}介绍三、命令语法及功能 :at

Linux下如何使用C++获取硬件信息

《Linux下如何使用C++获取硬件信息》这篇文章主要为大家详细介绍了如何使用C++实现获取CPU,主板,磁盘,BIOS信息等硬件信息,文中的示例代码讲解详细,感兴趣的小伙伴可以了解下... 目录方法获取CPU信息:读取"/proc/cpuinfo"文件获取磁盘信息:读取"/proc/diskstats"文

Java使用SLF4J记录不同级别日志的示例详解

《Java使用SLF4J记录不同级别日志的示例详解》SLF4J是一个简单的日志门面,它允许在运行时选择不同的日志实现,这篇文章主要为大家详细介绍了如何使用SLF4J记录不同级别日志,感兴趣的可以了解下... 目录一、SLF4J简介二、添加依赖三、配置Logback四、记录不同级别的日志五、总结一、SLF4J