网站导航
> 文章列表 > 二叉树搜索树详解

二叉树搜索树详解

网友: 文章列表 2024-03-22 03:49:55

二叉树搜索树详解

定义

二叉搜索树（BST，Binary Search Tree）

  • 或为一颗空树，或满足一下性质
  • 若它的左子树不为空，则左子树上所有节点的值都小于根节点的值
  • 若它的右子树不为空，则右子树上所有节点的值都大于根节点的值
  • 它的左右子树也分别为二叉搜索树

注：二叉树中元素是单一的，无重复

例子

  • arr = { 8,3,1,4,6,10,7,14,13}
    二叉树搜索树详解

二叉搜索树的功能及实现

节点

struct BSNode
{BSNode(const K& data):_left(nullptr), _right(nullptr), _key(data){}BSNode<K>* _left;BSNode<K>* _right;K _key;
};

如上文讨论，二叉搜索树是一种二叉树，节点与普通二叉树相似

基本结构

class BinarySearchTree
{typedef BSNode<K> Node;typedef Node* PNode;public://构造函数BinarySearchTree();//拷贝构造BinarySearchTree(const BinarySearchTree<K>& t);//赋值重载BinarySearchTree<K>& operator=(BinarySearchTree<K> t);//析构函数~BinarySearchTree();//插入bool Insert(const K& data);//插入的递归实现bool InsertR(const K& data);//中序遍历void InOrder();//删除bool Erase(const K& data);//删除的递归实现bool EraseR(const K& data);//查找bool Find(const K& data);//查找的递归实现bool FindR(const K& data);//树的销毁（用以辅助析构函数）void Destory();private:PNode _root = nullptr;};

构造函数

BinarySearchTree(){}

因以给与_root以默认值，构造函数起始可以省略
该默认值等效为

BinarySearchTree():_root(nullptr){}

使用构造函数构造一个空树即可

拷贝构造

拷贝一棵新树即可

		BinarySearchTree(const BinarySearchTree<K>& t){_root = _Copy(t._root);//调用_Copy函数递归构造树}PNode _Copy(PNode root){if (root == nullptr)//当root节点为空树时，返回nullptrreturn nullptr;//拷贝根节点PNode CopyRoot = new Node(root->_key);//拷贝并链接左子树CopyRoot->_left = _Copy(root->_left);//拷贝并链接右子树CopyRoot->_right = _Copy(root->_right);//返回新拷贝出的子树return CopyRoot;}

赋值重载

因拷贝构造已经实现，在函数传参时，非传引用情况下，函数参数会调用拷贝构造去构造一棵新树，交换指针即可
二叉树搜索树详解

拷贝出的树会于函数结束后自动析构

		BinarySearchTree<K>& operator=(BinarySearchTree<K> t){std::swap(_root, t._root);return *this;}

析构函数

析构函数也通过递归调用实现

		~BinarySearchTree(){_Destory(_root);//销毁二叉搜索树_root = nullptr;//并将_root置空，防止越界访问}void _Destory(PNode& root){if (root == nullptr)//空树直接返回return;_Destory(root->_left);//销毁左子树_Destory(root->_right);//销毁右子树delete root;}

插入

常规实现

按照二叉搜索树的性质对元素进行插入
通过指针cur遍历二叉搜索树,pcur指针保存cur的父节点指针

bool Insert(const K& data){if (nullptr == _root)//判断是否为空树{_root = new Node(data);return true;}//通过cur遍历二叉搜索树，cur最后指向的位置及为data插入位置//pcur保存cur的父节点，最后通过pcur链接新节点//_root及是整颗树的根节点，无父节点，先将pcur置空PNode pcur = nullptr;PNode cur = _root;//当cur == nullptr时，找到目标位置while (cur){//保存cur当前位置pcur = cur;K& tmp = cur->_key;//进行数值判断if (data > tmp)cur = cur->_right;else if (data < tmp)cur = cur->_left;//相等时，插入失败elsereturn false;}//虽然将cur的父节点传回，但不知为该节点的左子树还是右子树if (data > pcur->_key)pcur->_right = new Node(data);elsepcur->_left = new Node(data);return true;}

递归实现

如果为空树，则new一个新节点直接赋值给_root
非空树时，按照性质进行插入

  • 插入值与节点值相同时，插入节点失败
  • 插入值大于节点值时，将节点插入右子树
  • 插入值小于节点值时，将节点插入左子树
    重复此操作直至寻到合适位置，将位置传给_InsertR()

传指针时需注意传递的为引用，通过引用十分方便的将父节点与子节点链接了起来

		bool InsertR(const K& data){//递归插入需传递位置//对函数进行进一步封装return _InsertR(_root, data);}bool _InsertR(PNode& root, const K& data){//	root 为空存在两种情况//其一：树为空树，new一个新节点并链接//其二：root当前位置为插入节点的目标所在//因root实际上传的为引用//对root的改变直接改变父节点中的指针//十分方便的实现了节点间的链接if (root == nullptr){root = new Node(data);return true;}//判断data值的位置else if (data > root->_key)return _InsertR(root->_right, data);elsereturn _InsertR(root->_left, data);return false;}

删除

二叉搜索树的删除是十分复杂的
二叉搜索树具有独特的结构，删除结点的同时，也要保持树独特结构的保存
当删除一个节点时，可以分成一下四种情况

  • 要删除的结点无孩子结点
  • 要删除的结点只有左孩子结点
  • 要删除的结点只有右孩子结点
  • 要删除的结点有左、右孩子结点

第一种情况可以和第二种或者第三种合并
实际分类起始为三种

  • 要删除的结点只有右孩子结点 直接删除，将父节点链接右孩子节点
  • 要删除的结点只有左孩子结点 直接删除，将父节点链接左孩子节点
  • 要删除的结点有左、右孩子结点 较为复杂，后文讨论

我们可以将节点的删除分为两个部分

  1. 找到节点
  2. 删除节点

非递归实现

找节点的过程与插入节点的过程相似

		bool Erase(const K& data){if (_root == nullptr)return false;PNode pcur = nullptr;PNode cur = _root;while (cur){K& tmp = cur->_key;if (data > tmp){pcur = cur;cur = cur->_right;}else if (data < tmp){pcur = cur;cur = cur->_left;}else{//找到节点了}}return false;}

查找完成后
cur指针指向的为目标节点
pcur指针指向的为目标节点的父节点

第二步删除节点
据上文讨论删除节点可分三种情况

第一种要删除的结点只有右孩子结点
直接删除，将父节点链接右孩子节点

但也存在一些特殊情况，一般情况下pcur指向的是cur的父节点
但当cur指向的是根节点时，根节点无父节点
此时据查找函数可知，此时pcur为nullptr
二叉树搜索树详解

		//该节点的左孩子为空if (cur->_left == nullptr){//cur为根节点的特殊情况if (cur == _root){_root = cur->_right;}else{	//判断cur是pcur的左子树还是右子树if (pcur->_left == cur)pcur->_left = cur->_right;elsepcur->_right = cur->_right;}//删除cur节点，并将指针置空delete cur;cur = nullptr;}

第二种要删除的结点只有左孩子结点
直接删除，将父节点链接左孩子节点
整体上与第一种类似

		//该节点的右孩子为空else if (cur->_right == nullptr){//cur为根节点的特殊情况if (cur == _root){_root = cur->_left;}else{//判断cur是pcur的左子树还是右子树if (pcur->_left == cur)pcur->_left = cur->_left;elsepcur->_right = cur->_left;}//删除cur节点，并将指针置空delete cur;cur = nullptr;}

第三种情况要删除的结点有左、右孩子结点
这种情况是最复杂的
删除该节点且要保证，二叉搜索树的结构不被破坏
如
二叉树搜索树详解
删除这个节点且要保证结构不破坏
该如何实现呢？
该节点被删除后，还有两颗子树需要处理
比较好的方案便是补上该节点的位置
补上该位置的节点有两点要求

  1. 要大于左节点的值
  2. 要小于右节点的值

有两种方案均满足需求

  1. 取右子树的最小节点
  2. 取左子树的最大节点

本文采取第一种方案
取右子树的最小节点
因右子树中所有元素均大于根节点
左子树中所有元素均小于根节点
右子树中的最小节点能很好的解决这个问题

此问题转化为 取右子树中的最小值
根据平衡二叉树的性质 左子树的值小于根节点
最小的节点一定是位于树的最左侧的

使用parent标记右子树中最小节点的父节点
使用min 标记右子树中最小节点

		else{//查找cur右子树的最小子节点PNode parent = cur;PNode min = cur->_right;//min->left 等于nullptr时 min已经为最小节点while (min->_left != nullptr){parent = min;min = min->_left;}//交换 cur 的值与 min 的值std::swap(min->_key, cur->_key);//min是parent的左孩子时if (parent->_left == min) parent->_left = min->_right;//min是parent的右孩子//min是parent的右孩子，只有一种情况//即右子树只有一个节点//parent指向cur min指向cur->_right;elseparent->_right = min->_right;delete min;return true;}
非递归删除的完整代码
		bool Erase(const K& data){if (_root == nullptr)return false;PNode pcur = nullptr;PNode cur = _root;while (cur){K& tmp = cur->_key;if (data > tmp){pcur = cur;cur = cur->_right;}else if (data < tmp){pcur = cur;cur = cur->_left;}else{if (cur->_left == nullptr){if (cur == _root){_root = cur->_right;}else{if (pcur->_left == cur)pcur->_left = cur->_right;elsepcur->_right = cur->_right;}delete cur;cur = nullptr;}else if (cur->_right == nullptr){if (cur == _root){_root = cur->_left;}else{if (pcur->_left == cur)pcur->_left = cur->_left;elsepcur->_right = cur->_left;}delete cur;cur = nullptr;}else{//查找cur右子树的最小子节点PNode parent = cur;PNode min = cur->_right;while (min->_left != nullptr){parent = min;min = min->_left;}std::swap(min->_key, cur->_key);if (parent->_left == min) parent->_left = min->_right;else parent->_right = min->_right;delete min;return true;}}}return false;}

递归删除

递归删除的的思路如下
使用root传递需要删除元素所在树，同归递归缩小目标范围
通过data传递元素值

当目标元素小于根节点的值时，去左子树搜索
当目标元素大于根节点的值时，去右子树搜索

如果查到空树也没有找到该元素，返回false
查到该元素时，具体的删除思路与非递归一致
使用右子树的最小值或者左子树的最大值
但也存在一些差异，在代码中具体说明

		bool EraseR(const K& data){//递归删除，需要传递位置//对删除函数进行进一步封装return _EraseR(_root,data);}bool _EraseR(PNode& root, const K& data){//空树，查找失败if (root == nullptr)return false;//元素大于节点值，去右子树中查找if (data > root->_key)return _EraseR(root->_right,data);//元素小于节点值，去左子树中查找else if (data < root->_key)return _EraseR(root->_left,data);//找到目标元素else{//元素的三种情况//该元素没有左孩子PNode tmp = root;if (root->_left == nullptr){root = root->_right;}//该元素没有右孩子else if (root->_right == nullptr){root = root->_left;}//该元素存在左孩子与右孩子else{	PNode min = root->_right;PNode parent = root;while (min->_left){parent = min;min = min->_left;}std::swap(min->_key, root->_key);//上文代码与非递归相同//一下是两种删除节点的方法//第一种与非递归相同/*if (parent->_left == min)parent->_left = min->_right;else parent->_right = min->_right;delete min;return true;*///第二章起始为递归调用了_EraseR//被用以与目标元素替换的元素，他的子树数量一定小于等于1//调用删除代码删除时，不会走到此处return _EraseR(root->_right, data);}}}

查找

查找的具体思考，起始在删除与插入均均有使用

  • 树为空树，查找失败，返回false
  • 元素大于根节点，向右子树中查询
  • 元素小于根节点，向左子树中查询
  • 找到目标元素，返回true

非递归实现

		bool Find(const K& data){PNode cur = _root;while (cur){//元素与节点值相同，查询成功if (cur->_key == data)return true;//元素大于节点值，去右子树中查询else if (data > cur->_key)cur = cur->_right;//元素小于节点值，去左子树中查询elsecur = cur->_left;}return false;}

递归实现

		bool FindR(const K& data){return _FindR(_root, data);}bool _FindR(PNode root, const K& data){//空树查找失败if (root == nullptr) return false;//查找成功if (root->_key == data) return true;//元素大于节点值，右子树中查询else if (root->_key < data)return _FindR(root->_right, data);//元素小于节点值，左子树中查询elsereturn _FindR(root->_left, data);}

中序遍历

二叉树的中序遍历，得到的元素是一个升序

二叉搜索树中所有的非空节点均满足一下性质
左节点非空时，一定小于该节点
右节点非空时，一定大于该节点

当对二叉搜索树进行中序遍历时，依照中序遍历的顺序

  • 左子树
  • 根节点
  • 右子树

根据二叉搜索树的性质可知。
左子树中所有元素小于根节点，右子树中所有节点大于根节点
如果按照先遍历左子树，再遍历根节点，最后遍历右子树
那么此时根节点的位置的左侧均小于根节点，右侧均大于根节点
二叉树搜索树详解

及为将树中元素按照升序排列时，根节点中元素应在的位置的位置

当遍历左子树与右子树时，也按照左子树，根节点，右子树的顺序遍历时
所有元素均处于升序数组中的正确位置
及中序遍历二叉搜索树时，遍历出的顺序为升序

递归实现

	void InOrder(){_InOrder(_root);}void _InOrder(PNode root){if (root == nullptr)return;_InOrder(root->_left);std::cout << root->_key << " ";_InOrder(root->_right);}

代码总览

#pragma once
#include<iostream>
template<class K>
struct BSNode
{BSNode(const K& data):_left(nullptr), _right(nullptr), _key(data){}BSNode<K>* _left;BSNode<K>* _right;K _key;
};
template<class K>
class BinarySearchTree
{typedef BSNode<K> Node;typedef Node* PNode;public:~BinarySearchTree(){_Destory(_root);_root = nullptr;}BinarySearchTree(){}BinarySearchTree(const BinarySearchTree<K>& t){_root = _Copy(t._root);}BinarySearchTree<K>& operator=(BinarySearchTree<K> t){std::swap(_root, t._root);return *this;}bool Insert(const K& data){if (nullptr == _root){_root = new Node(data);return true;}PNode pcur = nullptr;PNode cur = _root;while (cur){pcur = cur;K& tmp = cur->_key;if (data > tmp)cur = cur->_right;else if (data < tmp)cur = cur->_left;elsereturn false;}if (data > pcur->_key)pcur->_right = new Node(data);elsepcur->_left = new Node(data);return true;}bool InsertR(const K& data){return _InsertR(_root, data);}void InOrder(){_InOrder(_root);}bool Erase(const K& data){if (_root == nullptr)return false;PNode pcur = nullptr;PNode cur = _root;while (cur){K& tmp = cur->_key;if (data > tmp){pcur = cur;cur = cur->_right;}else if (data < tmp){pcur = cur;cur = cur->_left;}else{if (cur->_left == nullptr){if (cur == _root){_root = cur->_right;}else{if (pcur->_left == cur)pcur->_left = cur->_right;elsepcur->_right = cur->_right;}delete cur;cur = nullptr;}else if (cur->_right == nullptr){if (cur == _root){_root = cur->_left;}else{if (pcur->_left == cur)pcur->_left = cur->_left;elsepcur->_right = cur->_left;}delete cur;cur = nullptr;}else{//查找cur右子树的最小子节点PNode parent = cur;PNode min = cur->_right;while (min->_left != nullptr){parent = min;min = min->_left;}std::swap(min->_key, cur->_key);if (parent->_left == min) parent->_left = min->_right;else parent->_right = min->_right;delete min;return true;}}}return false;}bool EraseR(const K& data){return _EraseR(_root,data);}bool Find(const K& data){PNode cur = _root;while (cur){if (cur->_key == data)return true;else if (data > cur->_key)cur = cur->_right;elsecur = cur->_left;}return false;}bool FindR(const K& data){return _FindR(_root, data);}void Destory(){_Destory(_root);}private:bool _EraseR(PNode& root, const K& data){if (root == nullptr)return false;if (data > root->_key)return _EraseR(root->_right,data);else if (data < root->_key)return _EraseR(root->_left,data);else{PNode tmp = root;if (root->_left == nullptr){root = root->_right;}else if (root->_right == nullptr){root = root->_left;}else{	PNode min = root->_right;PNode parent = root;while (min->_left){parent = min;min = min->_left;}std::swap(min->_key, root->_key);/*if (parent->_left == min)parent->_left = min->_right;else parent->_right = min->_right;delete min;return true;*/return _EraseR(root->_right, data);}}}bool _InsertR(PNode& root, const K& data){if (root == nullptr){root = new Node(data);return true;}else if (data > root->_key)return _InsertR(root->_right, data);elsereturn _InsertR(root->_left, data);return false;}bool _FindR(PNode root, const K& data){if (root == nullptr) return false;if (root->_key == data) return true;else if (root->_key < data)return _FindR(root->_right, data);elsereturn _FindR(root->_left, data);}void _InOrder(PNode root){if (root == nullptr) return;_InOrder(root->_left);std::cout << root->_key << " ";_InOrder(root->_right);}void _Destory(PNode& root){if (root == nullptr)return;_Destory(root->_left);_Destory(root->_right);delete root;}PNode _Copy(PNode root){if (root == nullptr)return nullptr;PNode CopyRoot = new Node(root->_key);CopyRoot->_left = _Copy(root->_left);CopyRoot->_right = _Copy(root->_right);return CopyRoot;}PNode _root = nullptr;};

二叉搜索树的应用

二叉树有两种模型

*K模型：K模型即只有key作为关键码，结构中只需要存储Key即可，关键码即为需要搜索到
的值
比如：给定一个单词，判断该单词是否拼写正确。具体方式如下：

  1. 以单词集合中的每个单词作为key，构建一棵二叉搜索树。
  2. 在二叉搜索树中检索该单词是否存在，存在则拼写正确，不存在则拼写错误。

KV模型：每一个关键码key，都有与之对应的值Value，即<Key, Value>的键值对。
比如：英汉词典就是英文与中文的对应关系，即<word, Chinese>就构成一种键值对。具体方式如下：

  1. 以<单词, 中文含义>为键值对，构建一棵二叉搜索树。注意：二叉搜索树需要进行比较，键值对比较时只比较key。
  2. 查询英文单词时，只需给出英文单词就可以快速找到与其对应的中文含义。
网络标签：

相关问题