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

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 ZIP文件操作技巧详解

Python ZIP文件操作技巧详解

《PythonZIP文件操作技巧详解》在数据处理和系统开发中,ZIP文件操作是开发者必须掌握的核心技能,Python标准库提供的zipfile模块以简洁的API和跨平台特性,成为处理ZIP文件的首选... 目录一、ZIP文件操作基础三板斧1.1 创建压缩包1.2 解压操作1.3 文件遍历与信息获取二、进阶技
阅读更多...
Java中字符串转时间与时间转字符串的操作详解

Java中字符串转时间与时间转字符串的操作详解

《Java中字符串转时间与时间转字符串的操作详解》Java的java.time包提供了强大的日期和时间处理功能,通过DateTimeFormatter可以轻松地在日期时间对象和字符串之间进行转换,下面... 目录一、字符串转时间（一）使用预定义格式（二）自定义格式二、时间转字符串（一）使用预定义格式（二）自
阅读更多...
redis过期key的删除策略介绍

redis过期key的删除策略介绍

《redis过期key的删除策略介绍》：本文主要介绍redis过期key的删除策略,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录第一种策略：被动删除第二种策略：定期删除第三种策略：强制删除关于big key的清理UNLINK命令FLUSHALL/FLUSHDB命
阅读更多...
Java字符串操作技巧之语法、示例与应用场景分析

Java字符串操作技巧之语法、示例与应用场景分析

《Java字符串操作技巧之语法、示例与应用场景分析》在Java算法题和日常开发中,字符串处理是必备的核心技能,本文全面梳理Java中字符串的常用操作语法,结合代码示例、应用场景和避坑指南,可快速掌握字... 目录引言1. 基础操作1.1 创建字符串1.2 获取长度1.3 访问字符2. 字符串处理2.1 子字
阅读更多...
Python 中的 with open文件操作的最佳实践

Python 中的 with open文件操作的最佳实践

《Python中的withopen文件操作的最佳实践》在Python中,withopen()提供了一个简洁而安全的方式来处理文件操作,它不仅能确保文件在操作完成后自动关闭,还能处理文件操作中的异... 目录什么是 with open()？为什么使用 with open()？使用 with open() 进行
阅读更多...
Linux ls命令操作详解

Linux ls命令操作详解

《Linuxls命令操作详解》通过ls命令,我们可以查看指定目录下的文件和子目录,并结合不同的选项获取详细的文件信息,如权限、大小、修改时间等,：本文主要介绍Linuxls命令详解,需要的朋友可... 目录1. 命令简介2. 命令的基本语法和用法2.1 语法格式2.2 使用示例2.2.1 列出当前目录下的文
阅读更多...
使用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 启动工具。但有时候，应
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2