二叉树的各种操作：前序、中序、后序、层序遍历，二叉树搜索、插入和删除等操作

2024-05-08 09:32
文章标签 二叉树 中序 遍历 操作 搜索 层序 删除 插入 后序 前序

本文主要是介绍二叉树的各种操作：前序、中序、后序、层序遍历，二叉树搜索、插入和删除等操作，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1.概述

定义：树是一个或多个节点的有效集合，且其中：

  • 存在一个称为根的特定节点
  • 其余的节点被分成n个互不相交的集合T,其中每个集合都是一棵树，称为子树。
  • 结点的度：一个结点的子树数目称为该结点的度；
  • 树的度：所有结点度当中，度最高的一个。（上图树的度是3）；
  • 叶子结点：度为0的节点；
  • 层(level)：根结点的层定义为1；根的孩子为第二层结点，依此类推
  • 树的深度（depth)或高度（height)：树中最大的结点层

2 二叉树

2.1基本概念

  1. 定义：二叉树（binary tree)是有限多个节点的集合，这个集合或者空集，或者 由一个根节点和两颗互不相交的、分别称为左子树和右子树组成。

  2. 二叉树的性质：

    • 在二叉树中，第i层的节点数最多为 2i−1,i≥1 ；
    • 在深度为k的二叉树中，节点总数最多为 2k−1,k≥1 ；
      叶子节点 n0 的个数与度为2的节点n_2个数之间的关系为：
      n0=n2+1

  3. 满二叉树（full binary tree):是深度为k的满二叉树是具有 2k−1 个节点的二叉树，除了叶结点外每一个结点都有左右子叶且叶子结点都处在最底层的二叉树

  4. 完全二叉树：若设二叉树的高度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第h层有叶子结点，并且叶子结点都是从左到右依次排布，这就是完全二叉树。

2. 2二叉树的存储表示

  1. 数组存储表示：对节点从1到n进行编号，因此可以使用一个一维数组来存储这些点。
    引理：对于一课n个节点的完全二叉树（深度 log2n+1 ）采用顺序存储 表示，那么对于任意一个下标为i节点有：
    • 若 i≠1 ，则其父节点parent(i)的编号为i/2;若i=1,则i是根节点；
    • 若 2i<n ，则其左孩子为2i;
    • 若 2i+1<n ,则其右孩子为2i+1;
  2. 链式存储:
    树的头结点定义：
typedef int ElementType;
typedef struct BinaryTreeNode BinTree;
struct BinaryTreeNode
{ElementType data;BinaryTreeNode* left;BinaryTreeNode* right;
};

2.3 二叉树的遍历

三种遍历：
- LVR:中序遍历（inoder);
- LRV:后续遍历（postorder);
- VLR:前序遍历（preoeder）;

表达式树：表达式树的树叶是操作数，常数或变量，二其他的节点为操作符(operator)，表达式三种遍历顺序与表达式的中缀(infix)、后缀（postfix)和前缀（prefix)形式之间存在一种自然的对应关系。
代码实现：

#ifndef BINARYTREE_H
#define BINARYTREE_Htypedef int ElementType;
struct BinaryTreeNode
{ElementType data;BinaryTreeNode* left;BinaryTreeNode* right;
};void PreOrder(BinaryTreeNode* pRoot);//前序遍历
void PostOrder(BinaryTreeNode* pRoot);//后续遍历
void InOrder(BinaryTreeNode* pRoot);//中序遍历
void LevelOrder(BinaryTreeNode* pRoot);//层序遍历
#endif
#include"BinaryTree.h"
#include<stdio.h>
#include<stdlib.h>
#include<queue>
/*1.递归的实现二叉树的遍历*/
//前序遍历
void PreOrder(BinaryTreeNode* pRoot)
{if (pRoot == NULL)return;printf("%d ", pRoot->data);PreOrder(pRoot->left);PreOrder(pRoot->right);
}//后续遍历
void PostOrder(BinaryTreeNode* pRoot)
{if (pRoot == NULL)return;PreOrder(pRoot->left);PreOrder(pRoot->right);printf("%d ", pRoot->data);}//中序遍历
void InOrder(BinaryTreeNode* pRoot)
{if (pRoot == NULL)return;PreOrder(pRoot->left);printf("%d ", pRoot->data);PreOrder(pRoot->right);
}//层序遍历
void LevelOrder(BinaryTreeNode* pRoot)
{if (pRoot == NULL)return;std::queue<BinaryTreeNode*> tree_node_queue;tree_node_queue.push(pRoot);while (tree_node_queue.size()>0){pRoot = tree_node_queue.front();tree_node_queue.pop();printf("%d ", pRoot->data);if (pRoot->left != NULL)tree_node_queue.push(pRoot->left);if (pRoot->right != NULL)tree_node_queue.push(pRoot->right);}
}

3. 二叉搜索树

3.1 概述

  • 关键字唯一
  • 非空左子树的值一定小于子树根节点的值
  • 右节点值一定大于根节点的值
  • 左右子树仍然是二叉搜索树

3.2 二叉搜索树的各种操作

  • 查找
  • 插入
  • 删除
#ifndef BINARYTREE_H
#define BINARYTREE_Htypedef int ElementType;
struct BinaryTreeNode
{ElementType data;BinaryTreeNode* left;BinaryTreeNode* right;
};void PreOrder(BinaryTreeNode* pRoot);//前序遍历
void PostOrder(BinaryTreeNode* pRoot);//后续遍历
void InOrder(BinaryTreeNode* pRoot);//中序遍历
void LevelOrder(BinaryTreeNode* pRoot);//层序遍历
BinaryTreeNode* BinaryTreeSearchRecursive(BinaryTreeNode* pRoot, ElementType key);//二叉搜索树查找（递归）
BinaryTreeNode* BinaryTreeSearch(BinaryTreeNode* pRoot, ElementType key);//二叉搜索树查找（迭代）
bool BinaryTreeInsert(BinaryTreeNode* &pRoot, ElementType key);//二叉树节点插入
bool BinaryTreeDelete(BinaryTreeNode* &pRoot, ElementType key);//二叉树节点删除#endif
#include"BinaryTree.h"
#include<stdio.h>
#include<stdlib.h>
#include<queue>
/*1.递归的实现二叉树的遍历*/
//前序遍历
void PreOrder(BinaryTreeNode* pRoot)
{if (pRoot == NULL)return;printf("%d ", pRoot->data);PreOrder(pRoot->left);PreOrder(pRoot->right);
}//后续遍历
void PostOrder(BinaryTreeNode* pRoot)
{if (pRoot == NULL)return;PreOrder(pRoot->left);PreOrder(pRoot->right);printf("%d ", pRoot->data);}//中序遍历
void InOrder(BinaryTreeNode* pRoot)
{if (pRoot == NULL)return;PreOrder(pRoot->left);printf("%d ", pRoot->data);PreOrder(pRoot->right);
}//层序遍历
void LevelOrder(BinaryTreeNode* pRoot)
{if (pRoot == NULL)return;std::queue<BinaryTreeNode*> tree_node_queue;tree_node_queue.push(pRoot);while (tree_node_queue.size() > 0){pRoot = tree_node_queue.front();tree_node_queue.pop();printf("%d ", pRoot->data);if (pRoot->left != NULL)tree_node_queue.push(pRoot->left);if (pRoot->right != NULL)tree_node_queue.push(pRoot->right);}
}//二叉搜索树查找(递归）
BinaryTreeNode* BinaryTreeSearchRecursive(BinaryTreeNode* pRoot, ElementType key)
{if (pRoot == NULL || key == pRoot->data)return pRoot;if (key < pRoot->data)return BinaryTreeSearchRecursive(pRoot->left, key);elsereturn BinaryTreeSearchRecursive(pRoot->right, key);
}//二叉搜索树查找（迭代）时间复杂度：o(h)
BinaryTreeNode* BinaryTreeSearch(BinaryTreeNode* pRoot, ElementType key)
{while (pRoot != NULL && key != pRoot->data){if (key < pRoot->data)pRoot = pRoot->left;elsepRoot = pRoot->right;}return pRoot;
}
//二叉树插入
bool BinaryTreeInsert(BinaryTreeNode* &pRoot, ElementType key)
{BinaryTreeNode* pParent = NULL;BinaryTreeNode* pNode = pRoot;while (pNode != NULL&&pNode->data != key){pParent = pNode;if (key < pNode->data)pNode = pNode->left;elsepNode = pNode->right;}if (pNode != NULL)//key已经存在return false;BinaryTreeNode* pNodeInsert = (BinaryTreeNode*)malloc(sizeof(BinaryTreeNode));if (pNodeInsert == NULL)//内存申请失败return false;pNodeInsert->data = key;pNodeInsert->left = pNodeInsert->right = NULL;if (pParent == NULL)//树为空，新插入的节点为根节点pRoot = pNodeInsert;else if (key < pParent->data)pParent->left = pNodeInsert;elsepParent->right = pNodeInsert;return true;
}//二叉树节点删除
bool BinaryTreeDelete(BinaryTreeNode* &pRoot, ElementType key)
{BinaryTreeNode *pNext, *pFather = NULL;BinaryTreeNode* pNode = pRoot;int pos = 0;//待删除节点的位置，0代表根节点，-1代表左节点，1代表右节点while (pNode != NULL&&pNode->data != key){pFather = pNode;if (key < pNode->data){pos = -1;pNode = pNode->left;}else{pos = 1;pNode = pNode->right;}}if (pNode == NULL)//节点不存在return false;if (pNode->left != NULL&&pNode->right != NULL)//待删除的节点有两个孩子{pFather = pNode;pos = -1;pNext = pNode->left;//用其左树中的最大元素替代删除元素while (pNext->right != NULL){pos = 1;pFather = pNext;pNext = pNext->right;}pNode->data = pNext->data;//替换pNode = pNext;//更新需要删除的元素}if (pNode->left != NULL)//待删除节点只有左孩子pNext = pNode->left;else if (pNode->right != NULL)//只有右节点pNext = pNode->right;else                //待删除节点没有孩子pNext = NULL;if (pos == 0)//待删除节点为根节点pRoot = pNext;else if (pos == -1)//待删除节点为左孩子pFather->left = pNext;else                         //待删除节点为右孩子pFather->right = pNext;delete pNode;//删除节点pNode = NULL;return true;
}

#include"BinaryTree.h"
#include<stdlib.h>
#include<stdio.h>int main()
{BinaryTreeNode* pRootNode = NULL;BinaryTreeNode* pFind;BinaryTreeInsert(pRootNode, 30);BinaryTreeInsert(pRootNode, 5);BinaryTreeInsert(pRootNode, 2);BinaryTreeInsert(pRootNode, 40);BinaryTreeInsert(pRootNode, 35);BinaryTreeInsert(pRootNode, 80);BinaryTreeInsert(pRootNode, 32);BinaryTreeInsert(pRootNode, 38);PreOrder(pRootNode);printf("1.前序遍历\n");InOrder(pRootNode);printf("2.中序遍历\n");PostOrder(pRootNode);printf("3.后序遍历\n");LevelOrder(pRootNode);printf("4.层序遍历\n");pFind = BinaryTreeSearch(pRootNode, 35);if (pFind)printf("5.找到的节点为：%d\n", pFind->data);elseprintf("5.未找到节点");pFind = BinaryTreeSearchRecursive(pRootNode, 33);if (pFind)printf("6.找到的节点为：%d\n", pFind->data);elseprintf("6.未找到节点\n");if (BinaryTreeInsert(pRootNode, 33)){printf("7.插入成功\n");LevelOrder(pRootNode);}if (BinaryTreeDelete(pRootNode, 33)){printf("8.删除成功\n");LevelOrder(pRootNode);}if (BinaryTreeDelete(pRootNode, 35)){printf("8.删除成功\n");LevelOrder(pRootNode);}return 0;
}

这篇关于二叉树的各种操作：前序、中序、后序、层序遍历，二叉树搜索、插入和删除等操作的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/969960。

相关文章

Linux使用fdisk进行磁盘的相关操作

Linux使用fdisk进行磁盘的相关操作

《Linux使用fdisk进行磁盘的相关操作》fdisk命令是Linux中用于管理磁盘分区的强大文本实用程序,这篇文章主要为大家详细介绍了如何使用fdisk进行磁盘的相关操作,需要的可以了解下... 目录简介基本语法示例用法列出所有分区查看指定磁盘的区分管理指定的磁盘进入交互式模式创建一个新的分区删除一个存
阅读更多...
Golang操作DuckDB实战案例分享

Golang操作DuckDB实战案例分享

《Golang操作DuckDB实战案例分享》DuckDB是一个嵌入式SQL数据库引擎,它与众所周知的SQLite非常相似,但它是为olap风格的工作负载设计的,DuckDB支持各种数据类型和SQL特性... 目录DuckDB的主要优点环境准备初始化表和数据查询单行或多行错误处理和事务完整代码最后总结Duck
阅读更多...
C# 读写ini文件操作实现

C# 读写ini文件操作实现

《C#读写ini文件操作实现》本文主要介绍了C#读写ini文件操作实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧... 目录一、INI文件结构二、读取INI文件中的数据在C#应用程序中，常将INI文件作为配置文件，用于存储应用程序的
阅读更多...
Python使用qrcode库实现生成二维码的操作指南

Python使用qrcode库实现生成二维码的操作指南

《Python使用qrcode库实现生成二维码的操作指南》二维码是一种广泛使用的二维条码,因其高效的数据存储能力和易于扫描的特点,广泛应用于支付、身份验证、营销推广等领域,Pythonqrcode库是... 目录一、安装 python qrcode 库二、基本使用方法1. 生成简单二维码2. 生成带 Log
阅读更多...
Java操作ElasticSearch的实例详解

Java操作ElasticSearch的实例详解

《Java操作ElasticSearch的实例详解》Elasticsearch是一个分布式的搜索和分析引擎,广泛用于全文搜索、日志分析等场景,本文将介绍如何在Java应用中使用Elastics... 目录简介环境准备1. 安装 Elasticsearch2. 添加依赖连接 Elasticsearch1. 创
阅读更多...
Oracle数据库使用 listagg去重删除重复数据的方法汇总

Oracle数据库使用 listagg去重删除重复数据的方法汇总

《Oracle数据库使用listagg去重删除重复数据的方法汇总》文章介绍了在Oracle数据库中使用LISTAGG和XMLAGG函数进行字符串聚合并去重的方法,包括去重聚合、使用XML解析和CLO... 目录案例表第一种：使用wm_concat() + distinct去重聚合第二种：使用listagg，
阅读更多...
java Stream操作转换方法

java Stream操作转换方法

《javaStream操作转换方法》文章总结了Java8中流(Stream)API的多种常用方法,包括创建流、过滤、遍历、分组、排序、去重、查找、匹配、转换、归约、打印日志、最大最小值、统计、连接、... 目录流创建1、list 转 map2、filter（）过滤3、foreach遍历4、groupingB
阅读更多...
Java操作PDF文件实现签订电子合同详细教程

Java操作PDF文件实现签订电子合同详细教程

《Java操作PDF文件实现签订电子合同详细教程》：本文主要介绍如何在PDF中加入电子签章与电子签名的过程,包括编写Word文件、生成PDF、为PDF格式做表单、为表单赋值、生成文档以及上传到OB... 目录前言：先看效果：1.编写word文件1.2然后生成PDF格式进行保存1.3我这里是将文件保存到本地后
阅读更多...
Python使用Colorama库美化终端输出的操作示例

Python使用Colorama库美化终端输出的操作示例

《Python使用Colorama库美化终端输出的操作示例》在开发命令行工具或调试程序时,我们可能会希望通过颜色来区分重要信息,比如警告、错误、提示等,而Colorama是一个简单易用的Python库... 目录python Colorama 库详解：终端输出美化的神器1. Colorama 是什么？2.
阅读更多...
Redis过期键删除策略解读

Redis过期键删除策略解读

《Redis过期键删除策略解读》Redis通过惰性删除策略和定期删除策略来管理过期键,惰性删除策略在键被访问时检查是否过期并删除,节省CPU开销但可能导致过期键滞留,定期删除策略定期扫描并删除过期键,... 目录1.Redis使用两种不同的策略来删除过期键，分别是惰性删除策略和定期删除策略1.1惰性删除策略
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2