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

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。

相关文章

python panda库从基础到高级操作分析

python panda库从基础到高级操作分析

《pythonpanda库从基础到高级操作分析》本文介绍了Pandas库的核心功能,包括处理结构化数据的Series和DataFrame数据结构,数据读取、清洗、分组聚合、合并、时间序列分析及大数据... 目录1. Pandas 概述2. 基本操作：数据读取与查看3. 索引操作：精准定位数据4. Group
阅读更多...
Python操作PDF文档的主流库使用指南

Python操作PDF文档的主流库使用指南

《Python操作PDF文档的主流库使用指南》PDF因其跨平台、格式固定的特性成为文档交换的标准,然而,由于其复杂的内部结构,程序化操作PDF一直是个挑战,本文主要为大家整理了Python操作PD... 目录一、 基础操作1.PyPDF2 (及其继任者 pypdf)2.PyMuPDF / fitz3.Fre
阅读更多...
Python对接支付宝支付之使用AliPay实现的详细操作指南

Python对接支付宝支付之使用AliPay实现的详细操作指南

《Python对接支付宝支付之使用AliPay实现的详细操作指南》支付宝没有提供PythonSDK,但是强大的github就有提供python-alipay-sdk,封装里很多复杂操作,使用这个我们就... 目录一、引言二、准备工作2.1 支付宝开放平台入驻与应用创建2.2 密钥生成与配置2.3 安装ali
阅读更多...
MySQL 强制使用特定索引的操作

MySQL 强制使用特定索引的操作

《MySQL强制使用特定索引的操作》MySQL可通过FORCEINDEX、USEINDEX等语法强制查询使用特定索引,但优化器可能不采纳,需结合EXPLAIN分析执行计划,避免性能下降,注意版本差异... 目录1. 使用FORCE INDEX语法2. 使用USE INDEX语法3. 使用IGNORE IND
阅读更多...
Python使用openpyxl读取Excel的操作详解

Python使用openpyxl读取Excel的操作详解

《Python使用openpyxl读取Excel的操作详解》本文介绍了使用Python的openpyxl库进行Excel文件的创建、读写、数据操作、工作簿与工作表管理,包括创建工作簿、加载工作簿、操作... 目录1 概述1.1 图示1.2 安装第三方库2 工作簿 workbook2.1 创建：Workboo
阅读更多...
MySQL逻辑删除与唯一索引冲突解决方案

MySQL逻辑删除与唯一索引冲突解决方案

《MySQL逻辑删除与唯一索引冲突解决方案》本文探讨MySQL逻辑删除与唯一索引冲突问题,提出四种解决方案：复合索引+时间戳、修改唯一字段、历史表、业务层校验,推荐方案1和方案3,适用于不同场景,感兴... 目录问题背景问题复现解决方案解决方案1.复合唯一索引 + 时间戳删除字段解决方案2：删除后修改唯一字
阅读更多...
Ubuntu 24.04启用root图形登录的操作流程

Ubuntu 24.04启用root图形登录的操作流程

《Ubuntu24.04启用root图形登录的操作流程》Ubuntu默认禁用root账户的图形与SSH登录,这是为了安全,但在某些场景你可能需要直接用root登录GNOME桌面,本文以Ubuntu2... 目录一、前言二、准备工作三、设置 root 密码四、启用图形界面 root 登录1. 修改 GDM 配
阅读更多...
JSONArray在Java中的应用操作实例

JSONArray在Java中的应用操作实例

《JSONArray在Java中的应用操作实例》JSONArray是org.json库用于处理JSON数组的类,可将Java对象（Map/List）转换为JSON格式,提供增删改查等操作,适用于前后端... 目录1. jsONArray定义与功能1.1 JSONArray概念阐释1.1.1 什么是JSONA
阅读更多...
使用Python删除Excel中的行列和单元格示例详解

使用Python删除Excel中的行列和单元格示例详解

《使用Python删除Excel中的行列和单元格示例详解》在处理Excel数据时,删除不需要的行、列或单元格是一项常见且必要的操作,本文将使用Python脚本实现对Excel表格的高效自动化处理,感兴... 目录开发环境准备使用 python 删除 Excphpel 表格中的行删除特定行删除空白行删除含指定
阅读更多...
Linux下删除乱码文件和目录的实现方式

Linux下删除乱码文件和目录的实现方式

《Linux下删除乱码文件和目录的实现方式》：本文主要介绍Linux下删除乱码文件和目录的实现方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录linux下删除乱码文件和目录方法1方法2总结Linux下删除乱码文件和目录方法1使用ls -i命令找到文件或目录
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2