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

相关文章

Python基础文件操作方法超详细讲解(详解版)

《Python基础文件操作方法超详细讲解(详解版)》文件就是操作系统为用户或应用程序提供的一个读写硬盘的虚拟单位,文件的核心操作就是读和写,:本文主要介绍Python基础文件操作方法超详细讲解的相... 目录一、文件操作1. 文件打开与关闭1.1 打开文件1.2 关闭文件2. 访问模式及说明二、文件读写1.

C++变换迭代器使用方法小结

《C++变换迭代器使用方法小结》本文主要介绍了C++变换迭代器使用方法小结,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧... 目录1、源码2、代码解析代码解析:transform_iterator1. transform_iterat

详解C++中类的大小决定因数

《详解C++中类的大小决定因数》类的大小受多个因素影响,主要包括成员变量、对齐方式、继承关系、虚函数表等,下面就来介绍一下,具有一定的参考价值,感兴趣的可以了解一下... 目录1. 非静态数据成员示例:2. 数据对齐(Padding)示例:3. 虚函数(vtable 指针)示例:4. 继承普通继承虚继承5.

C++中std::distance使用方法示例

《C++中std::distance使用方法示例》std::distance是C++标准库中的一个函数,用于计算两个迭代器之间的距离,本文主要介绍了C++中std::distance使用方法示例,具... 目录语法使用方式解释示例输出:其他说明:总结std::distance&n编程bsp;是 C++ 标准

前端高级CSS用法示例详解

《前端高级CSS用法示例详解》在前端开发中,CSS(层叠样式表)不仅是用来控制网页的外观和布局,更是实现复杂交互和动态效果的关键技术之一,随着前端技术的不断发展,CSS的用法也日益丰富和高级,本文将深... 前端高级css用法在前端开发中,CSS(层叠样式表)不仅是用来控制网页的外观和布局,更是实现复杂交

Linux换行符的使用方法详解

《Linux换行符的使用方法详解》本文介绍了Linux中常用的换行符LF及其在文件中的表示,展示了如何使用sed命令替换换行符,并列举了与换行符处理相关的Linux命令,通过代码讲解的非常详细,需要的... 目录简介检测文件中的换行符使用 cat -A 查看换行符使用 od -c 检查字符换行符格式转换将

SpringBoot实现数据库读写分离的3种方法小结

《SpringBoot实现数据库读写分离的3种方法小结》为了提高系统的读写性能和可用性,读写分离是一种经典的数据库架构模式,在SpringBoot应用中,有多种方式可以实现数据库读写分离,本文将介绍三... 目录一、数据库读写分离概述二、方案一:基于AbstractRoutingDataSource实现动态

详解C#如何提取PDF文档中的图片

《详解C#如何提取PDF文档中的图片》提取图片可以将这些图像资源进行单独保存,方便后续在不同的项目中使用,下面我们就来看看如何使用C#通过代码从PDF文档中提取图片吧... 当 PDF 文件中包含有价值的图片,如艺术画作、设计素材、报告图表等,提取图片可以将这些图像资源进行单独保存,方便后续在不同的项目中使

Java中的String.valueOf()和toString()方法区别小结

《Java中的String.valueOf()和toString()方法区别小结》字符串操作是开发者日常编程任务中不可或缺的一部分,转换为字符串是一种常见需求,其中最常见的就是String.value... 目录String.valueOf()方法方法定义方法实现使用示例使用场景toString()方法方法

Java中List的contains()方法的使用小结

《Java中List的contains()方法的使用小结》List的contains()方法用于检查列表中是否包含指定的元素,借助equals()方法进行判断,下面就来介绍Java中List的c... 目录详细展开1. 方法签名2. 工作原理3. 使用示例4. 注意事项总结结论:List 的 contain