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

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。

相关文章

使用Java填充Word模板的操作指南

使用Java填充Word模板的操作指南

《使用Java填充Word模板的操作指南》本文介绍了Java填充Word模板的实现方法,包括文本、列表和复选框的填充,首先通过Word域功能设置模板变量,然后使用poi-tl、aspose-words... 目录前言一、设置word模板普通字段列表字段复选框二、代码1. 引入POM2. 模板放入项目3.代码
阅读更多...
Linux命令rm如何删除名字以“-”开头的文件

Linux命令rm如何删除名字以“-”开头的文件

《Linux命令rm如何删除名字以“-”开头的文件》Linux中,命令的解析机制非常灵活,它会根据命令的开头字符来判断是否需要执行命令选项,对于文件操作命令（如rm、ls等）,系统默认会将命令开头的某... 目录先搞懂：为啥“-”开头的文件删不掉？两种超简单的删除方法（小白也能学会）方法1：用“--”分隔命
阅读更多...
利用Python操作Word文档页码的实际应用

利用Python操作Word文档页码的实际应用

《利用Python操作Word文档页码的实际应用》在撰写长篇文档时,经常需要将文档分成多个节,每个节都需要单独的页码,下面：本文主要介绍利用Python操作Word文档页码的相关资料,文中通过代码... 目录需求：文档详情：要求：该程序的功能是：总结需求：一次性处理24个文档的页码。文档详情：1、每个
阅读更多...
Python内存管理机制之垃圾回收与引用计数操作全过程

Python内存管理机制之垃圾回收与引用计数操作全过程

《Python内存管理机制之垃圾回收与引用计数操作全过程》SQLAlchemy是Python中最流行的ORM（对象关系映射）框架之一,它提供了高效且灵活的数据库操作方式,本文将介绍如何使用SQLAlc... 目录安装核心概念连接数据库定义数据模型创建数据库表基本CRUD操作创建数据读取数据更新数据删除数据查
阅读更多...
Go语言中json操作的实现

Go语言中json操作的实现

《Go语言中json操作的实现》本文主要介绍了Go语言中的json操作的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧... 目录 一、jsOChina编程N 与 Go 类型对应关系️ 二、基本操作：编码与解码 三、结构体标签（Struc
阅读更多...
C#自动化实现检测并删除PDF文件中的空白页面

C#自动化实现检测并删除PDF文件中的空白页面

《C#自动化实现检测并删除PDF文件中的空白页面》PDF文档在日常工作和生活中扮演着重要的角色,本文将深入探讨如何使用C#编程语言,结合强大的PDF处理库,自动化地检测并删除PDF文件中的空白页面,感... 目录理解PDF空白页的定义与挑战引入Spire.PDF for .NET库核心实现：检测并删除空白页
阅读更多...
Java 字符串操作之contains 和 substring 方法最佳实践与常见问题

Java 字符串操作之contains 和 substring 方法最佳实践与常见问题

《Java字符串操作之contains和substring方法最佳实践与常见问题》本文给大家详细介绍Java字符串操作之contains和substring方法最佳实践与常见问题,本文结合实例... 目录一、contains 方法详解1. 方法定义与语法2. 底层实现原理3. 使用示例4. 注意事项二、su
阅读更多...
Python实现自动化删除Word文档超链接的实用技巧

Python实现自动化删除Word文档超链接的实用技巧

《Python实现自动化删除Word文档超链接的实用技巧》在日常工作中,我们经常需要处理各种Word文档,本文将深入探讨如何利用Python,特别是借助一个功能强大的库,高效移除Word文档中的超链接... 目录为什么需要移除Word文档超链接准备工作：环境搭建与库安装核心实现：使用python移除超链接的
阅读更多...
Java Stream流与使用操作指南

Java Stream流与使用操作指南

《JavaStream流与使用操作指南》Stream不是数据结构,而是一种高级的数据处理工具,允许你以声明式的方式处理数据集合,类似于SQL语句操作数据库,本文给大家介绍JavaStream流与使用... 目录一、什么是stream流二、创建stream流1.单列集合创建stream流2.双列集合创建str
阅读更多...
SpringBoot分段处理List集合多线程批量插入数据方式

SpringBoot分段处理List集合多线程批量插入数据方式

《SpringBoot分段处理List集合多线程批量插入数据方式》文章介绍如何处理大数据量List批量插入数据库的优化方案：通过拆分List并分配独立线程处理,结合Spring线程池与异步方法提升效率... 目录项目场景解决方案1.实体类2.Mapper3.spring容器注入线程池bejsan对象4.创建
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2