前言 🦕
二叉树顾名思义即为一个树中节点的度不大于2的有序树,是树中结构中较为简单的一种;
其特点为一个节点中分为两个子树;
通常可以以二叉树进行分治的思路对问题进行解决(递归或非递归);
但在实际中普通二叉树由于在数据存储方面中并没有明显的特性,所以在实际中普通二叉树的应用场景并不多;
BinarySearchTree二叉搜索树,顾名思义这种类型的二叉树对搜索有着比较大的优势;
二叉搜索树的概念 🦕
二叉搜索树又称搜索二叉树,也可以称为排序树,顾名思义这棵树有着对数据进行搜索的优势;
该二叉树的性质为:
- 如果这棵树的左子树不为空,则左子树上的节点值都小于根节点的值;
- 如果这棵树的右子树不为空,则右子树上的节点值都小于根节点的值;
二叉搜索树的左右子树也同时满足该条件;
该二叉树的节点若是使用中序遍历的方式进行打印则将会以顺序的方式进行打印,所以这棵树也被称为排序树;
同时搜索二叉树中的数据还具有唯一性,即同一种的数据只能进行一次插入;
搜索二叉树的初始化 🦕
在实现当中搜索二叉树也应该使用类模板确保可以进行泛型编程；
搜索二叉树的初始化与普通二叉树的初始化相当,都需要两个类:
struct BSTNode
该类用来对搜索二叉树的各个节点进行封装;
template<class K>//一般情况下二叉树内的模板参数习惯以K代替(key); struct BSTNode{ //构造函数 BSTNode(const K& key = K())// 给定缺省参数确保可以正常进行初始化 :_pleft(nullptr),//初始化列表初始化参数 _pright(nullptr), _key(key) {} BSTNode<K> *_pleft;//左子树 BSTNode<K> *_pright;//右子树 K _key;//数据 };
class BinarySearchTree
该类主要用于实现二叉树的整体(包括各个成员函数)
template<class K> class BinarySearchTree{ typedef BSTNode<K> Node;//对节点进行typedef重命名 public: BinarySearchTree(){}//构造函数 ~BinarySearchTree(){}//析构函数 BinarySearchTree(const BinarySearchtree<K> &node){}//拷贝构造函数 BinarySearchTree<K>& operator=(BinarySearchTree<K> node){}//赋值运算符重载 bool Insert(const K& key){}//数据插入 void InOrder(){}//中序遍历打印数据 bool Find(const K&key){}//查找数据 bool Erase(const K&key){}//删除数据 protected: private: Node* _proot = nullptr;//头节点 };
Insert( )插入函数 🦕
插入函数的实现在搜索二叉树中一般为顺照搜索二叉树的特性进行遍历;
当遍历节点至空时则表示在该处进行插入;
- 若是需要插入的数据大于当前节点的数据则向当前节点的右子树进行遍历;
- 若是需要插入的数据小于当前节点的数据则向当前节点的左子树进行遍历;
- 若是需要插入的数据等于当前节点的数据则返回
false(唯一性); - 遍历至
nullptr处则表示当前不存在节点,可进行插入,插入结束后返回true;
bool Insert(const K& key){ if(_proot == nullptr){//如果root节点为空说明为空树，空树进行第一次插入 _proot = new Node(key); return true;//插入成功进行返回 } Node* cur = _proot; Node* tmp; while(cur!=nullptr){ tmp = cur; if(key>cur->_key){ tmp = cur; cur = cur->_pright; } else if(key<cur->_key){ tmp = cur; cur = cur->_pleft; } else{ //相同 返回false return false; } } if(key>tmp->_key){//链接在右边 cur = new Node(key); tmp->_pright = cur; } else{//链接在左边 cur = new Node(key); tmp->_pleft = cur; } return true; }
该函数的插入还存在一个链接的问题;
链接的问题采用类似双指针的方式,一个指针进行遍历确认是否进行插入,另一个指针用来保存该节点的父节点位置方便两个节点进行链接;
👾 InsertR( ) 插入函数(递归)
一般来说在类中成员函数的递归比较麻烦的是对于数据的传参问题;
所以为了解决这个问题建议在自定义类型中定义递归函数时尽量写一个子函数用于递归,并使用成员函数来调用此子函数;
该函数的递归思路与非递归的思路相当,唯一不同的是在递归中除了要思考节点的插入问题同时还需要注意节点与节点之间的链接问题,在递归当中子函数的节点参数可以使用Node*& root来代替;
由于引用算是一个变量的别名,意义即为将一个指针的别名传入下一层的递归当中,将新节点插入该节点即完成插入的节点链接问题;
bool InsertR(const K&key){//主函数 return _InsertR(key,_proot);//调用函数进行递归 } //---------------------------------- bool _InsertR(const K&key,Node*& root){//子函数 if(root == nullptr) { root = new Node(key); return true; } if(root->_key < key){ return _InsertR(key,root->_pright); } else if(root->_key>key){ return _InsertR(key,root->_pleft); } else return false; }
InOrder( ) 中序遍历打印 🦕
该函数以递归的方式进行中序遍历,使用子函数递归,主函数调用的方式即可;
void InOrder(){//主函数 _InOrder(_proot); cout<<endl; } //---------------------------------- void _InOrder(Node *root){//子函数 if(root == nullptr){ return; } _InOrder(root->_pleft); cout<<root->_key<<" "; _InOrder(root->_pright); }
Find( ) 查找函数 🦕
该函数使用非递归以搜索二叉树的规则进行遍历即可;
找到数据则返回true否则返回false;
bool Find(const K& key){ Node*pcur = _proot; while(pcur){ if(key>pcur->_key) pcur = pcur->_pright; else if(key<pcur->_key) pcur = pcur->_pleft; else return true; } return false; }
👾 Find( ) 查找函数(递归)
该函数建立子函数进行递归即可;
bool FindR(const K& key){//主函数 return _FindR(key,_proot); } //---------------------------------- bool _FindR(const K&key,Node*root){//子函数 if(root == nullptr) return false; if(root->_key == key) return true; if(root->_key>key) return _FindR(key,root->_pleft); else return _FindR(key,root->_pright); }
『 C++ 』BinarySearchTree搜索二叉树（下）https://developer.aliyun.com/article/1424470
