赞
踩
普通的二叉树单纯用来存储数据意义不大,还不如用数组和链表。
普通数组和链表,面对一些需要频繁查找、插入、删除的场景,也很麻烦。
所以这里引入了二叉搜索树。
二叉搜索树又称二叉排序树,它或者是一棵空树,或者是具有以下性质的二叉树:
二叉搜索树的结构特点带来的好处:
定义二叉搜索树节点类模板:
#include<iostream> using namespace std; // 定义二叉搜索树节点 template<class K> struct BinarySearchTreeNode // cpp中不用typedef { K _key; BinarySearchTreeNode<K>* _left; BinarySearchTreeNode<K>* _right; // 构造函数 BinarySearchTreeNode(const K& key) :_key(key) ,_left(nullptr) ,_right(nullptr) {} };
定义二叉搜索树类模板:
// 定义二叉搜索树 template<class K> class BinarySearchTree { typedef BinarySearchTreeNode<K> Node; // 重命名树节点类名 private: Node* _root = nullptr; // 根节点 public: // 构造函数 BinarySearchTree(); // 拷贝构造函数 BinarySearchTree(const BinarySearchTree<K>& tree); // 引用 // 赋值运算符重载函数 BinarySearchTree<K>& operator=(BinarySearchTree<K> tree); // 传值 // 析构函数 ~BinarySearchTree(); // 插入元素key bool Insert(const K& key); // 常引用:减少传参时的拷贝,保护形参不会被更改 // 查找元素key,查找到了返回节点地址,否则返回nullptr Node* Find(const K& key); // 删除元素key bool Erase(const K& key); // 插入元素key(递归版本) bool InsertR(const K& key); // 查找元素key(递归版本) Node* FindR(const K& key); // 删除元素key(递归版本) bool EraseR(const K& key); // 中序遍历 void InOrder(); private: // 拷贝构造子函数 Node* _Copy(Node* _root); // 析构子函数 void _Destroy(Node* root); // 插入元素key子函数(递归版本) bool _InsertR(Node*& root, const K& key); // 形参为引用,这里很妙 // 查找元素key子函数(递归版本) Node* _FindR(Node* root, const K& key); // 删除元素key子函数(递归版本) bool _EraseR(Node*& root, const K& key); // 形参为引用,这里很妙 // 中序遍历子函数 void _InOrder(Node* _root); };
//...
public:
// 构造函数
BinarySearchTree()
:_root(nullptr)
{}
//...
//... public: // 拷贝构造函数 BinarySearchTree(const BinarySearchTree<K>& tree) { // 深拷贝,用已存在的树tree去拷贝一个新树,然后返回新树的根 _root = _Copy(tree._root); } private: // 拷贝构造子函数 Node* _Copy(Node* _root) { // 树为空 if (_root == nullptr) { return nullptr; } // 树不为空,开始递归拷贝构建新的树,按照根-左-右的顺序拷贝构造 Node* newRoot = new Node(_root->_key); newRoot->_left = _Copy(_root->_left); newRoot->_right = _Copy(_root->_right); // 返回当前拷贝的新树 return newRoot; } //...
//...
public:
// 赋值运算符重载函数
BinarySearchTree<K>& operator=(BinarySearchTree<K> tree) // 传值
{
// 现代写法
// 比如 t1 = t2,tree是t2的深拷贝,tree就是t1想要的,
// 所以t1和tree换个头(根节点地址),但不换身体(整颗树),t1就指向了tree整棵树,然后返回去
std::swap(_root, tree._root);
return *this;
}
//...
//... public: // 析构函数 ~BinarySearchTree() { _Destroy(_root); } private: // 析构子函数 void _Destroy(Node* root) { // 根节点不为空 if (root) { // 建议使用后序遍历,左-右-根 _Destroy(root->_left); _Destroy(root->_right); delete root; root = nullptr; } } //...
如果根节点为空,返回 nullptr
如果根节点不为空,从根节点开始,查找 key:
// 查找元素key,查找到了返回节点地址,否则返回nullptr Node* Find(const K& key) { // 树为空 if (_root == nullptr) { return nullptr; } // 树不为空,从根节点开始查找元素key Node* cur = _root; while (cur) // 当cur为空,停止循环,说明没找到 { if (key > cur->_key) { cur = cur->_right; } else if (key < cur->_key) { cur = cur->_left; } else // 查找到了,返回节点地址 { return cur; break; } } // 没有找到 return nullptr; }
分而治之的思想:
每一级递归时,在我们眼中,当前树就是这样的,只有 root
、left
、right
三个节点。
递归算法思路:
根据「二叉搜索树性质」,查找 key,太简单了,略……
// 定义二叉搜索树 template<class K> class BinarySearchTree { typedef BinarySearchTreeNode<K> Node; // 重命名 private: Node* _root = nullptr; // 根节点 public: // 查找元素key(递归版本) // 调用函数需要传递树的根,根是私有成员,所以套一层函数InsertR来间接调用,从而保护根 Node* FindR(const K& key) { return _FindR(_root, key); } private: // 查找元素key子函数(递归版本) Node* _FindR(Node* root, const K& key) { // 递归出口(终止条件),当前树的根节点为空 if (root == nullptr) { return nullptr; // 没找到,返回nullptr } // 当前树的根节点不为空 if (key > root->_key) { return _FindR(root->_right, key); } else if (key < root->_key) { return _FindR(root->_left, key); } else { // 找到了,返回该节点地址 return root; } } }
树为空,直接插入。
树不为空,根据「二叉搜索树性质」,从根节点开始,查找到适合插入 key 的空位置,然后插入。
代码如下:
// 插入元素key bool Insert(const K& key) // 常引用:减少传参时的拷贝,保护形参 不会被更改 { // 树为空 if (_root == nullptr) { _root = new Node(key); // 直接插入新节点 return true; } // 树不为空,从根节点开始,先查找到插入key的位置 Node* cur = _root; // 记录cur的父节点,因为新节点最终会插入在cur的父节点左右孩子的位置 Node* parent = nullptr; while (cur) // 当cur为空,说明找到插入key的位置了 { if (key < cur->_key) // key比当前节点小 { parent = cur; cur = cur->_left; // 去当前节点的左子树查找 } else if (key > cur->_key) // key比当前节点大 { parent = cur; cur = cur->_right; // 去当前节点的右子树查找 } else { // key等于当前节点,说明元素已经在树中存在,二叉搜索树不允许冗余,则返回false return false; } } // 申请一个新节点 cur = new Node(key); // 判断下新节点应该链接在其父节点的左边还是右边 if (key > parent->_key) { parent->_right = cur; // key比父节点大,链接在右边 } else { parent->_left = cur; // key比父节点小,链接在左边 } // 插入成功,返回true return true; }
注意一点:
插入元素的顺序不同,树的结构也会不同,但中序遍历的结果是一样的。
分而治之的思想:
每一级递归时,在我们眼中,当前树就是这样的,只有 root
、left
、right
三个节点。
递归算法思路:
如果当前树的根节点为空,则直接插入;
如果当前树的根节点不为空:
// 定义二叉搜索树 template<class K> class BinarySearchTree { typedef BinarySearchTreeNode<K> Node; // 重命名 private: Node* _root = nullptr; // 根节点 public: // 插入元素key(递归版本) // 调用函数需要传递树的根,根是私有成员,所以套一层函数InsertR来间接调用,从而保护根 bool InsertR(const K& key) { return _InsertR(_root, key); } private: // 插入元素key子函数(递归版本) bool _InsertR(Node*& root, const K& key) // 形参是根节点的引用,这里很巧妙 { // 当前树的根节点为空 if (root == nullptr) { root = new Node(key); // 插入新节点 return true; // 返回true } // 当前树的根节点不为空 if (key > root->_key) { // 去往当前树的右子树中插入 return _InsertR(root->_right, key); } else if (key < root->_key) { // 去往当前树的左子树中插入 return _InsertR(root->_left, key); } else { // 二叉搜索树不允许数据冗余,返回false return false; } } }
函数形参是根节点的引用 bool _InsertR(Node*& root, const K& key);
,这里很巧妙,我们在函数体内就不用定义一个变量来保存要插入的节点的父节点了。
我们以插入节点 10 为例,分析下原理:
这样一来,我通过改变 root,从而控制 root 父节点(节点 9)右指针的指向。
注意一点:
我们在类外面,用对象调用函数时需要传递树的根,但根是私有成员,只能再去写一个 GetRoot 接口来传递树的根,但这样根又被暴露出去了,所以我们在这里,套一层无参函数 InOrder()
来调用有参函数 _InOrder(Node* _root)
,从而保护了根节点。
template<class K> class BinarySearchTree { typedef BinarySearchTreeNode<K> Node; // 重命名树节点类名 private: Node* _root = nullptr; // 根节点 public: // 其它成员函数...... // 中序遍历 // void InOrder(Node* _root) // 调用函数需要传递树的根,根是私有成员,所以套一层无参函数InOrder()来间接调用,从而保护根 void InOrder() { _InOrder(_root); // 调用中序遍历子函数 cout << endl; } private: // 中序遍历子函数 void _InOrder(Node* root) { if (root) { _InOrder(root->_left); cout << root->_key << " "; _InOrder(root->_right); } } };
二叉搜索树的删除比较复杂,要分情况讨论:
首先查找元素 key 是否在二叉搜索树中,如果不存在,则返回 false,否则删除结点,分下面几种情况:
情况1和2:要删除的结点「无孩子」结点(叶子节点),或者要删除的结点「只有左孩子」结点
- 先判断被删除节点 cur 是父节点 parent 的 左孩子 还是 右孩子。
- 让父结点 parent 的左 / 右指针指向被删除节点的 左孩子 (我被删除了,我的父亲要帮我接管左孩子)
- 然后删除该节点。
【注意】:
还有一种情况需要考虑到,删除的是根节点,cur 没有父节点,所以直接把 cur 的左孩子变为根:
情况3:要删除的结点「只有右孩子」结点
先判断被删除节点 cur 是父节点 parent 的 左孩子 还是 右孩子。
让父结点 parent 的左 / 右指针指向被删除节点的 右孩子。(我被删除了,我的父亲要帮我接管右孩子)
然后删除该节点。
这里就不详细画图演示了,和上面的类似。
【注意】:
还有一种情况需要考虑到,删除的是根节点,cur 没有父节点,所以直接把 cur 的右孩子变为根:
情况4:要删除的结点「有左右孩子」结点
有两个孩子,不好直接删除,所以我们用替代法删除:
找一个「替代节点」,比被删除节点的左孩子值大,比被删除节点右孩子的值小。
即被删除节点左子树中的最大节点或者右子树中的最小节点。
- 左子树中的最大节点 --> 即左子树的最右侧节点(它的右孩子一定为空)
- 右子树中的最小节点 --> 即右子树的最左侧节点(它的左孩子一定为空)
「替代节点」找到后,将替代节点中的值赋给「要的删除节点」,转换成删除替代节点。
以找被删除节点 左子树中的最大节点 作为替代节点为例,删除思路如下:
【注意】:
在第 3 步:
先要判断一下最大节点 maxleft 是父节点 maxleft_parent 的 左孩子 还是 右孩子。
让父结点 maxleft_parent 的左 / 右指针指向被删除节点的 左孩子 (我被删除了,我的父亲要帮我接管左孩子,因为左子树的最大节点没有的右孩子)
代码如下:
// 删除元素key bool Erase(const K& key) { // 树为空,删除失败 if (_root == nullptr) { return false; } // 树不为空,从根节点开始,查找元素key Node* cur = _root; // 记录元素key的位置 Node* parent = nullptr; // 记录cur的父节点 while (cur) // 如果cur为空,说明没有找到元素key的位置 { if (key > cur->_key) { parent = cur; cur = cur->_right; } else if (key < cur->_key) { parent = cur; cur = cur->_left; } else // 找到要删除的元素key了,分为以下几种情况: { // 1、要删除的节点没有左右孩子,或者要删除的节点只有一个左孩子 if (cur->_right == nullptr) { if (cur == _root) // 如果要删除的cur是树的根节点,cur没有父节点 { _root = cur->_left; } else { // 判断下 if (cur == parent->_left) // 被删除节点cur是父节点的左孩子 { parent->_left = cur->_left; // 让父节点左指针指向cur左孩子 } else // 被删除节点cur是父节点的右孩子 { parent->_right = cur->_left; // 让父节点右指针指向cur左孩子 } } // 删除 delete cur; } // 2、要删除的节点只有一个右孩子 else if (cur->_left == nullptr) { if (cur == _root) // 如果要删除的cur是树的根节点,cur没有父节点 { _root = cur->_right; } else { // 判断下 if (cur == parent->_left) // 被删除节点cur是父节点的左孩子 { parent->_left = cur->_right; // 让父节点左指针指向cur右孩子 } else // 被删除节点cur是父节点的右孩子 { parent->_right = cur->_right; // 让父节点左指针指向cur右孩子 } } // 删除 delete cur; } // 3、要删除的节点有左、右两个孩子 else { // 找替代节点:被删除节点的左子树中的最大节点,即左子树的最右节点(它的右孩子一定为空) Node* maxleft = cur->_left; // 从左子树的根节点开始找 Node* maxleft_parent = cur; // 记录最大节点的父亲 // 3.1 找最大节点 while (maxleft->_right) // 右孩子为空时,说明找到最大节点了 { maxleft_parent = maxleft; maxleft = maxleft->_right; // 继续往右找 } // 3.2 把最大节点的值赋给被删除节点 cur->_key = maxleft->_key; // 3.3 判断一下 if (maxleft == maxleft_parent->_left) // 如果最大节点是父节点左孩子 { // 让父节点左指针指向maxleft左孩子 maxleft_parent->_left = maxleft->_left; } else // 如果最大节点是父节点的右孩子 { // 让父节点右指针指向maxleft左孩子 maxleft_parent->_right = maxleft->_left; } // 3.4 删除 delete maxleft; } // 删除成功,返回true return true; } } // 没有找到元素key,删除失败,返回false return false; }
分而治之的思想:
每一级递归时,在我们眼中,当前树就是这样的,只有 root
、left
、right
三个节点。
递归算法思路:
// 定义二叉搜索树 template<class K> class BinarySearchTree { typedef BinarySearchTreeNode<K> Node; // 重命名 private: Node* _root = nullptr; // 根节点 public: // 删除元素key(递归版本) bool EraseR(const K& key) { return _EraseR(_root, key); // 保护根 } private: // 删除元素key子函数(递归版本) bool _EraseR(Node*& root, const K& key) { // 树为空,删除失败 if (root == nullptr) { return false; } // 树不为空,查找要删除的节点 if (key > root->_key) { return _EraseR(root->_right, key); } else if (key < root->_key) { return _EraseR(root->_left, key); } else // 找到了,删除该节点 { Node* del = root; // 保存当前节点的地址 // 1、当前节点没有左右孩子,或者当前节点只有一个左孩子 if (root->_right == nullptr) { root = root->_left; } // 2、当前节点只有一个右孩子 else if (root->_left == nullptr) { root = root->_right; } // 3、当前节点有左右两个孩子 else { // 找到当前节点的右子树中最小节点替代删除 Node* minRight = root->_right; while (minRight->_left) { minRight = minRight->_left; } // 替代节点值赋给当前节点 root->_key = minRight->_key; // 转换成,在当前节点的右子树中去删除替代节点 return _EraseR(root->_right, minRight->_key); } delete del; return true; } } }
【拓展】
在删除有两个孩子的节点时,需要注意的细节:
二叉搜索树的查找,根据「二叉搜索树性质」来找某节点
二叉搜索树的插入,
二叉搜索树的删除,
先根据「二叉搜索树性质」来查找要删除的节点 cur,
并根据要删除节点 cur 所在位置的不同情况,来具体操作,
必须要保存要删除节点 cur 的父节点,并判断要删除节点 cur 是左孩子还是右孩子,先让父亲接管要删除节点 cur 的孩子,然后再删除节点 cur。
删除节点 cur 的 3 种情况汇总:cur左为空,父亲指向右;右为空,父亲指向左;左右都不为空,找替代节点。
对于上述接口的递归写法,一般能用循环(非递归)就用非递归,有些递归好是好,也容易让人理解,但是对于深度高的树,建立栈帧也是一笔不小的开销,有可能会导致栈溢出。
K (Key) 模型:确定一个值在不在一个集合中,K 模型即只有 Key 作为关键码,二叉搜索树结构中只需要存储 Key 即可,关键码即为需要搜索到的值。
举个例子1:
举个例子2:给一个单词 word,判断该单词是否拼写正确,具体方式如下:
赞
踩
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。