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

相关文章

Spring Security基于数据库验证流程详解

Spring Security 校验流程图 相关解释说明(认真看哦) AbstractAuthenticationProcessingFilter 抽象类 /*** 调用 #requiresAuthentication(HttpServletRequest, HttpServletResponse) 决定是否需要进行验证操作。* 如果需要验证,则会调用 #attemptAuthentica

【C++ Primer Plus习题】13.4

大家好,这里是国中之林! ❥前些天发现了一个巨牛的人工智能学习网站,通俗易懂,风趣幽默,忍不住分享一下给大家。点击跳转到网站。有兴趣的可以点点进去看看← 问题: 解答: main.cpp #include <iostream>#include "port.h"int main() {Port p1;Port p2("Abc", "Bcc", 30);std::cout <<

C++包装器

包装器 在 C++ 中,“包装器”通常指的是一种设计模式或编程技巧,用于封装其他代码或对象,使其更易于使用、管理或扩展。包装器的概念在编程中非常普遍,可以用于函数、类、库等多个方面。下面是几个常见的 “包装器” 类型: 1. 函数包装器 函数包装器用于封装一个或多个函数,使其接口更统一或更便于调用。例如,std::function 是一个通用的函数包装器,它可以存储任意可调用对象(函数、函数

OpenHarmony鸿蒙开发( Beta5.0)无感配网详解

1、简介 无感配网是指在设备联网过程中无需输入热点相关账号信息,即可快速实现设备配网,是一种兼顾高效性、可靠性和安全性的配网方式。 2、配网原理 2.1 通信原理 手机和智能设备之间的信息传递,利用特有的NAN协议实现。利用手机和智能设备之间的WiFi 感知订阅、发布能力,实现了数字管家应用和设备之间的发现。在完成设备间的认证和响应后,即可发送相关配网数据。同时还支持与常规Sof

C++11第三弹:lambda表达式 | 新的类功能 | 模板的可变参数

🌈个人主页: 南桥几晴秋 🌈C++专栏: 南桥谈C++ 🌈C语言专栏: C语言学习系列 🌈Linux学习专栏: 南桥谈Linux 🌈数据结构学习专栏: 数据结构杂谈 🌈数据库学习专栏: 南桥谈MySQL 🌈Qt学习专栏: 南桥谈Qt 🌈菜鸡代码练习: 练习随想记录 🌈git学习: 南桥谈Git 🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈�

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

【C++】_list常用方法解析及模拟实现

相信自己的力量,只要对自己始终保持信心,尽自己最大努力去完成任何事,就算事情最终结果是失败了,努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一:什么是list? •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二:list常用接口 •🌰1.默认成员函数 🔥构造函数(⭐) 🔥析构函数 •🌰2.list对象

06 C++Lambda表达式

lambda表达式的定义 没有显式模版形参的lambda表达式 [捕获] 前属性 (形参列表) 说明符 异常 后属性 尾随类型 约束 {函数体} 有显式模版形参的lambda表达式 [捕获] <模版形参> 模版约束 前属性 (形参列表) 说明符 异常 后属性 尾随类型 约束 {函数体} 含义 捕获:包含零个或者多个捕获符的逗号分隔列表 模板形参:用于泛型lambda提供个模板形参的名

浅谈主机加固,六种有效的主机加固方法

在数字化时代,数据的价值不言而喻,但随之而来的安全威胁也日益严峻。从勒索病毒到内部泄露,企业的数据安全面临着前所未有的挑战。为了应对这些挑战,一种全新的主机加固解决方案应运而生。 MCK主机加固解决方案,采用先进的安全容器中间件技术,构建起一套内核级的纵深立体防护体系。这一体系突破了传统安全防护的局限,即使在管理员权限被恶意利用的情况下,也能确保服务器的安全稳定运行。 普适主机加固措施:

webm怎么转换成mp4?这几种方法超多人在用!

webm怎么转换成mp4?WebM作为一种新兴的视频编码格式,近年来逐渐进入大众视野,其背后承载着诸多优势,但同时也伴随着不容忽视的局限性,首要挑战在于其兼容性边界,尽管WebM已广泛适应于众多网站与软件平台,但在特定应用环境或老旧设备上,其兼容难题依旧凸显,为用户体验带来不便,再者,WebM格式的非普适性也体现在编辑流程上,由于它并非行业内的通用标准,编辑过程中可能会遭遇格式不兼容的障碍,导致操