BSTree二叉树讲解

2023-10-30 09:20
文章标签 二叉树 讲解 bstree

本文主要是介绍BSTree二叉树讲解,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

二叉搜索树的概念:

        二叉搜索树又称二叉排序树,它或者是一棵空树,或者是具有以下性质的二叉树:

  •                 若它的左子树不为空,则左子树上所有节点的值都小于根节点的值
  •                 若它的右子树不为空,则右子树上所有节点的值都大于根节点的值
  •                 它的左右子树也分别为二叉搜索树

二叉树的运用:(改代码就是KV模型的二叉搜索树)

1. K模型K模型即只有key作为关键码,结构中只需要存储Key即可,关键码即为需要搜索到
的值。
        比如:给一个单词word,判断该单词是否拼写正确,具体方式如下:
以词库中所有单词集合中的每个单词作为key,构建一棵二叉搜索树


在二叉搜索树中检索该单词是否存在,存在则拼写正确,不存在则拼写错误。
2. KV模型每一个关键码key,都有与之对应的值Value,即<Key, Value>的键值对。该种方
式在现实生活中非常常见:
        比如英汉词典就是英文与中文的对应关系,通过英文可以快速找到与其对应的中文,英
文单词与其对应的中文<word, chinese>就构成一种键值对;
        再比如统计单词次数,统计成功后,给定单词就可快速找到其出现的次数,单词与其出
现次数就是<word, count>就构成一种键值对。

二叉树的查找:

        a、从根开始比较,查找,比根大则往右边走查找,比根小则往左边走查找。
        b、最多查找高度次,走到到空,还没找到,这个值不存在。

	Node* _Find(Node* root,const K& key){if (root == nullptr)//遇到空节点就返回{return nullptr;}if (root->_kv.first == key){return root;}else if (root->_kv.first > key){_Find(root->_left, key);}else{_Find(root->_right, key);}}

 二叉搜索树的插入:

插入的具体过程如下:
        a. 树为空,则直接新增节点,赋值给root指针
        b. 树不空,按二叉搜索树性质查找插入位置,插入新节点

	bool _Insert(const pair<K, V>& kv)//这里使用pair——key,value模型 如字典{if (_root == nullptr)//如果该二叉树的树为空 就给个节点然后返回{_root = new Node(kv);return true;}//不为空就进行寻找 找到太该呆的位置 Node* parent = nullptr;Node* cur = _root;while (cur){if (cur->_kv.first > kv.first){parent = cur;cur = cur->_left;}else if (cur->_kv.first < kv.first){parent = cur;cur = cur->_right;}else{return false;}}//判断该节点在父节点的左边还是右边if (parent->_kv.first > kv.first){parent->_left = new Node(kv);}else{parent->_right = new Node(kv);}}Node* _root = nullptr;
};

二叉搜索树的删除:

首先查找元素是否在二叉搜索树中,如果不存在,则返回, 否则要删除的结点可能分下面四种情
况:
        a. 要删除的结点无孩子结点
        b. 要删除的结点只有左孩子结点
        c. 要删除的结点只有右孩子结点
        d. 要删除的结点有左、右孩子结点
看起来有待删除节点有4中情况,实际情况a可以与情况b或者c合并起来,因此真正的删除过程
如下:
        情况b:删除该结点且使被删除节点的双亲结点指向被删除节点的左孩子结点--直接删除
        情况c:删除该结点且使被删除节点的双亲结点指向被删除结点的右孩子结点--直接删除
        情况d:在它的右子树中寻找中序下的第一个结点(关键码最小),用它的值填补到被删除节点
        中,再来处理该结点的删除问题--替换法删除

	bool _Erase(Node* root, const K& key){Node* parent = nullptr;Node* cur = root;while (cur){if (cur->_kv.first == key)//如果key与要搜索的值相等 就进行删除{if (cur->_left == nullptr)//左子树为空 右子树不为空{//再考虑要删除的节点是他父节点的左子树还是右子树 将该节点接到其父节点上if (cur == parent->_left){parent->_left = cur->_right;}else{parent->_right = cur->_right;}delete cur;//将该节点进行释放}else if (cur->_right == nullptr)//右子树不存在 左子树存在 同上{if (cur == parent->_left){parent->_left = cur->_left;}else{parent->_right = cur->_left;}delete cur;}else//左右子树都存在 需要寻找一个可以代替该节点值的值 {//在左子树中找最小的值 (就是左子树最左边的那个节点)右节点就找右子树中最大的节点 (就是右子树最右边的那个节点)Node* parent1 = nullptr;Node* tmp = cur;while (tmp->_left)//寻找左节点{parent1 = tmp;tmp = tmp->_left;}swap(&cur->_kv, &tmp->_kv);//找到进行值的交换parent1->_left = tmp->_right;//如果最小的左节点的左子树为空右子树不为空 将右子树接到该节点的父亲上 但是如果右子树为空 也可以将空节点接到其父节点上 不产生影响delete tmp;//释放节点}}else{if (root->_kv.first > key){parent = cur;cur = cur->_left;}else{parent = cur;cur = cur->_right;}}}}

二叉树的遍历:(中序遍历)(将二叉树中key的值按顺序打印)

	void _InOrder(Node* root){if (root == nullptr){return;}_InOrder(root->_left);cout << root->_kv.first << " " << root->_kv.second << endl;_InOrder(root->_right);}

以下就是二叉搜索树的完整代码 以及对应的测试用例,可以自行去调用测试。

#include<iostream>
#include<string>
using namespace std;template<class K,class V>
struct BSTreeNode
{typedef BSTreeNode<K, V> Node;BSTreeNode(const pair<K, V>& x):_kv(x), _left(nullptr), _right(nullptr){}pair<K, V> _kv;Node* _left;Node* _right;
};template<class K, class V>
class BSTree
{typedef BSTreeNode<K, V> Node;
public:bool Insert(const K& key, const V& value){pair<K, V> kv(key, value);return _Insert(kv);}Node* Find(const K& key){return _Find(_root,key);}bool Erase(const K& key){return _Erase(_root, key);}void InOrder(){_InOrder(_root);}
private:bool _Erase(Node* root, const K& key){Node* parent = nullptr;Node* cur = root;while (cur){if (cur->_kv.first == key){if (cur->_left == nullptr){if (cur == parent->_left){parent->_left = cur->_right;}else{parent->_right = cur->_right;}delete cur;}else if (cur->_right == nullptr){if (cur == parent->_left){parent->_left = cur->_left;}else{parent->_right = cur->_left;}delete cur;}else{Node* parent1 = nullptr;Node* tmp = cur;while (tmp->_left){parent1 = tmp;tmp = tmp->_left;}swap(&cur->_kv, &tmp->_kv);parent1->_left = tmp->_right;delete tmp;}}else{if (root->_kv.first > key){parent = cur;cur = cur->_left;}else{parent = cur;cur = cur->_right;}}}}void _InOrder(Node* root){if (root == nullptr){return;}_InOrder(root->_left);cout << root->_kv.first << " " << root->_kv.second << endl;_InOrder(root->_right);}Node* _Find(Node* root,const K& key){if (root == nullptr){return nullptr;}if (root->_kv.first == key){return root;}else if (root->_kv.first > key){_Find(root->_left, key);}else{_Find(root->_right, key);}}bool _Insert(const pair<K, V>& kv){if (_root == nullptr){_root = new Node(kv);return true;}Node* parent = nullptr;Node* cur = _root;while (cur){if (cur->_kv.first > kv.first){parent = cur;cur = cur->_left;}else if (cur->_kv.first < kv.first){parent = cur;cur = cur->_right;}else{return false;}}if (parent->_kv.first > kv.first){parent->_left = new Node(kv);}else{parent->_right = new Node(kv);}}Node* _root = nullptr;
};void TestBSTree()
{BSTree<string, string> dict;dict.Insert("insert", "插入");dict.Insert("erase", "删除");dict.Insert("left", "左边");dict.Insert("string", "字符串");string str;while (cin >> str){auto ret = dict.Find(str);if (ret){cout << str << ":" << ret->_kv.second << endl;}else{cout << "单词拼写错误" << endl;}}string strs[] = { "苹果", "西瓜", "苹果", "樱桃", "苹果", "樱桃", "苹果", "樱桃", "苹果" };// 统计水果出现的次BSTree<string, int> countTree;for (auto str : strs){auto ret = countTree.Find(str);if (ret == NULL){countTree.Insert(str, 1);}else{ret->_kv.second++;}}countTree.InOrder();
}

这篇关于BSTree二叉树讲解的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/306906

相关文章

Java集合中的List超详细讲解

《Java集合中的List超详细讲解》本文详细介绍了Java集合框架中的List接口,包括其在集合中的位置、继承体系、常用操作和代码示例,以及不同实现类(如ArrayList、LinkedList和V... 目录一,List的继承体系二,List的常用操作及代码示例1,创建List实例2,增加元素3,访问元

Python使用国内镜像加速pip安装的方法讲解

《Python使用国内镜像加速pip安装的方法讲解》在Python开发中,pip是一个非常重要的工具,用于安装和管理Python的第三方库,然而,在国内使用pip安装依赖时,往往会因为网络问题而导致速... 目录一、pip 工具简介1. 什么是 pip?2. 什么是 -i 参数?二、国内镜像源的选择三、如何

Python itertools中accumulate函数用法及使用运用详细讲解

《Pythonitertools中accumulate函数用法及使用运用详细讲解》:本文主要介绍Python的itertools库中的accumulate函数,该函数可以计算累积和或通过指定函数... 目录1.1前言:1.2定义:1.3衍生用法:1.3Leetcode的实际运用:总结 1.1前言:本文将详

Redis的Zset类型及相关命令详细讲解

《Redis的Zset类型及相关命令详细讲解》:本文主要介绍Redis的Zset类型及相关命令的相关资料,有序集合Zset是一种Redis数据结构,它类似于集合Set,但每个元素都有一个关联的分数... 目录Zset简介ZADDZCARDZCOUNTZRANGEZREVRANGEZRANGEBYSCOREZ

Go中sync.Once源码的深度讲解

《Go中sync.Once源码的深度讲解》sync.Once是Go语言标准库中的一个同步原语,用于确保某个操作只执行一次,本文将从源码出发为大家详细介绍一下sync.Once的具体使用,x希望对大家有... 目录概念简单示例源码解读总结概念sync.Once是Go语言标准库中的一个同步原语,用于确保某个操

计算机毕业设计 大学志愿填报系统 Java+SpringBoot+Vue 前后端分离 文档报告 代码讲解 安装调试

🍊作者:计算机编程-吉哥 🍊简介:专业从事JavaWeb程序开发,微信小程序开发,定制化项目、 源码、代码讲解、文档撰写、ppt制作。做自己喜欢的事,生活就是快乐的。 🍊心愿:点赞 👍 收藏 ⭐评论 📝 🍅 文末获取源码联系 👇🏻 精彩专栏推荐订阅 👇🏻 不然下次找不到哟~Java毕业设计项目~热门选题推荐《1000套》 目录 1.技术选型 2.开发工具 3.功能

leetcode105 从前序与中序遍历序列构造二叉树

根据一棵树的前序遍历与中序遍历构造二叉树。 注意: 你可以假设树中没有重复的元素。 例如,给出 前序遍历 preorder = [3,9,20,15,7]中序遍历 inorder = [9,3,15,20,7] 返回如下的二叉树: 3/ \9 20/ \15 7   class Solution {public TreeNode buildTree(int[] pr

PHP实现二叉树遍历(非递归方式,栈模拟实现)

二叉树定义是这样的:一棵非空的二叉树由根结点及左、右子树这三个基本部分组成,根据节点的访问位置不同有三种遍历方式: ① NLR:前序遍历(PreorderTraversal亦称(先序遍历)) ——访问结点的操作发生在遍历其左右子树之前。 ② LNR:中序遍历(InorderTraversal) ——访问结点的操作发生在遍历其左右子树之中(间)。 ③ LRN:后序遍历(PostorderT

ispunct函数讲解 <ctype.h>头文件函数

目录 1.头文件函数 2.ispunct函数使用  小心!VS2022不可直接接触,否则..!没有这个必要,方源一把抓住VS2022,顷刻 炼化! 1.头文件函数 以上函数都需要包括头文件<ctype.h> ,其中包括 ispunct 函数 #include<ctype.h> 2.ispunct函数使用 简述: ispunct函数一种判断字符是否为标点符号的函

深度学习速通系列:深度学习算法讲解

深度学习算法是一系列基于人工神经网络的算法,它们通过模拟人脑处理信息的方式来学习和解决复杂问题。这些算法在图像识别、语音识别、自然语言处理、游戏等领域取得了显著的成就。以下是一些流行的深度学习算法及其基本原理: 1. 前馈神经网络(Feedforward Neural Networks, FNN) 原理:FNN 是最基本的神经网络结构,它由输入层、隐藏层和输出层组成。信息从输入层流向隐藏层,最