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

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。

相关文章

使用C#代码在PDF文档中添加、删除和替换图片

使用C#代码在PDF文档中添加、删除和替换图片

《使用C#代码在PDF文档中添加、删除和替换图片》在当今数字化文档处理场景中,动态操作PDF文档中的图像已成为企业级应用开发的核心需求之一,本文将介绍如何在.NET平台使用C#代码在PDF文档中添加、... 目录引言用C#添加图片到PDF文档用C#删除PDF文档中的图片用C#替换PDF文档中的图片引言在当
阅读更多...
Mysql表的简单操作(基本技能)

Mysql表的简单操作(基本技能)

《Mysql表的简单操作(基本技能)》在数据库中,表的操作主要包括表的创建、查看、修改、删除等,了解如何操作这些表是数据库管理和开发的基本技能,本文给大家介绍Mysql表的简单操作,感兴趣的朋友一起看... 目录3.1 创建表 3.2 查看表结构3.3 修改表3.4 实践案例：修改表在数据库中，表的操作主要
阅读更多...
C# WinForms存储过程操作数据库的实例讲解

C# WinForms存储过程操作数据库的实例讲解

《C#WinForms存储过程操作数据库的实例讲解》：本文主要介绍C#WinForms存储过程操作数据库的实例,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、存储过程基础二、C# 调用流程1. 数据库连接配置2. 执行存储过程（增删改）3. 查询数据三、事务处
阅读更多...
macOS无效Launchpad图标轻松删除的4 种实用方法

macOS无效Launchpad图标轻松删除的4 种实用方法

《macOS无效Launchpad图标轻松删除的4种实用方法》mac中不在appstore上下载的应用经常在删除后它的图标还残留在launchpad中，并且长按图标也不会出现删除符号，下面解决这个问... 在 MACOS 上，Launchpad（也就是「启动台」）是一个便捷的 App 启动工具。但有时候，应
阅读更多...
Java使用Curator进行ZooKeeper操作的详细教程

Java使用Curator进行ZooKeeper操作的详细教程

《Java使用Curator进行ZooKeeper操作的详细教程》ApacheCurator是一个基于ZooKeeper的Java客户端库,它极大地简化了使用ZooKeeper的开发工作,在分布式系统... 目录1、简述2、核心功能2.1 CuratorFramework2.2 Recipes3、示例实践3
阅读更多...
Java利用JSONPath操作JSON数据的技术指南

Java利用JSONPath操作JSON数据的技术指南

《Java利用JSONPath操作JSON数据的技术指南》JSONPath是一种强大的工具,用于查询和操作JSON数据,类似于SQL的语法,它为处理复杂的JSON数据结构提供了简单且高效... 目录1、简述2、什么是 jsONPath？3、Java 示例3.1 基本查询3.2 过滤查询3.3 递归搜索3.4
阅读更多...
Mysql删除几亿条数据表中的部分数据的方法实现

Mysql删除几亿条数据表中的部分数据的方法实现

《Mysql删除几亿条数据表中的部分数据的方法实现》在MySQL中删除一个大表中的数据时,需要特别注意操作的性能和对系统的影响,本文主要介绍了Mysql删除几亿条数据表中的部分数据的方法实现,具有一定... 目录1、需求2、方案1. 使用 DELETE 语句分批删除2. 使用 INPLACE ALTER T
阅读更多...
MySQL INSERT语句实现当记录不存在时插入的几种方法

MySQL INSERT语句实现当记录不存在时插入的几种方法

《MySQLINSERT语句实现当记录不存在时插入的几种方法》MySQL的INSERT语句是用于向数据库表中插入新记录的关键命令,下面：本文主要介绍MySQLINSERT语句实现当记录不存在时... 目录使用 INSERT IGNORE使用 ON DUPLICATE KEY UPDATE使用 REPLACE
阅读更多...
Python使用DrissionPage中ChromiumPage进行自动化网页操作

Python使用DrissionPage中ChromiumPage进行自动化网页操作

《Python使用DrissionPage中ChromiumPage进行自动化网页操作》DrissionPage作为一款轻量级且功能强大的浏览器自动化库,为开发者提供了丰富的功能支持,本文将使用Dri... 目录前言一、ChromiumPage基础操作1.初始化Drission 和 ChromiumPage
阅读更多...
利用Go语言开发文件操作工具轻松处理所有文件

利用Go语言开发文件操作工具轻松处理所有文件

《利用Go语言开发文件操作工具轻松处理所有文件》在后端开发中,文件操作是一个非常常见但又容易出错的场景,本文小编要向大家介绍一个强大的Go语言文件操作工具库,它能帮你轻松处理各种文件操作场景... 目录为什么需要这个工具？核心功能详解1. 文件/目录存javascript在性检查2. 批量创建目录3. 文件
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2