二分搜索树及基本操作(c++代码实现)

您所在的位置：网站首页 › 二分查找判定树的构造 › 二分搜索树及基本操作(c++代码实现)

二分搜索树及基本操作(c++代码实现)

2024-07-09 17:09| 来源: 网络整理| 查看: 265

二分搜索树

二分搜索树通常用于实现查找表（字典数据结构key-value）

查找插入删除普通数组O(n)O(n)O(n)顺序数组O(logn)O(n)O(n)二分搜索树O(logn)O(logn)O(logn)

二分搜索树的优势：能够高效、动态维护数据，还可以很方便的回答很多数据关系的问题，比如min、max、floor、ceil、rank、select等。

[定义]

二分搜索树的特点如下： 1、二分搜索树是一棵二叉树 2、每个节点的键值大于左子树中所有节点 3、每个节点的键值小于右子树中所有节点 4、以左右孩子为根的子树仍为二分搜索树二分搜索树没有完全二叉树的要求，不一定是完全二叉树下面是两个二分搜索树的样例。在这里插入图片描述由于二分搜索树不一定是完全二叉树，所以用数组的形式难以表述，在c++中常采用指针表示。

[代码实现] template class BST{ private: struct Node{//二分搜索树中的节点 Key key; Value value; Node* left; Node* right; Node(Key key, Value value){//Node的构造函数 this->key = key; this->value = value; this->left = this->right = NULL; } Node(Node* node){ this->key = node->key; this->value = node->value; this->left = node->left; this->right = node->right; }; Node* root;//二分搜索树根节点 int count;//二分搜索树中的节点数 public: BST(){ root = NULL; count = 0; } ~BST(){ destroy(root); } int size(){ return count; } bool empty(){ return count == 0; } void destroy(Node* node){//本质就是后序遍历 if(node != NULL){ destroy(node->left); destroy(node->right); delete node; } } }; [二分搜索树常用操作] [insert-插入元素] [过程演示]

通过比较待插入元素和节点键值的大小关系，维护二叉搜索树的定义例如：插入28和60 在这里插入图片描述

[代码实现] //用户调用，公有函数 void insert(Key key, Value value){ //调用递归函数insert，私有函数 root = insert(root, key, value); } //递归函数，私有函数 //函数定义：向以node为根的二叉搜索树中，插入节点(key,value) //返回值：返回插入新节点后的二叉搜索树的根 Node* insert(Node* node, Key key, Value value){ if( node = NULL){//递归终止条件 count++; return new Node(key,value); } if(node->key == key) node->value = value; else if(key key) //key < node->key //向node的左子树插入(key,value) node->left = insert(node->left, key, value); else //key > node->key //向node的右子树插入(key,value) node->right = insert(node->right, key, value); return node; } [search/contain-查找/包含元素] [过程演示]

和insert操作类似，通过二叉搜索树的性质进行查找例如：查找28和42 在这里插入图片描述

[代码实现] contain操作 //用户调用，公有函数 void contain(Key key){ //调用递归函数contain，私有函数 root = contain(root, key); } //递归函数，私有函数 //查看以node为根的二叉搜索树中是否包含key的节点 //返回值：true-包含，false-不包含 bool contain(Node* node, Key key){ if( node == NULL){//递归终止条件 return false; } if(node->key == key) return true; else if(key key) //key < node->key //node的左子树是否包含 return contain(node->left, key); else //key > node->key //node的右子树是否包含 return contain(node->right, key); } search操作

查找key所对应的键值函数返回值分析： 1、Node*——这种情况由于struct Node为私有变量，外部无法通过Node访问到value 2、Value——这种情况若查找不到，无法返回空，可以返回前先判断是否contain 3、Value*——可以存空，也可获得具体值。采用此种返回值。

//用户调用，公有函数 Value* search(Key key){ //调用递归函数search，私有函数 Node* node = search(root, key); return &(node->value); } //递归函数，私有函数 //在以node为根的二叉搜索树中查找key所对应的value //返回值：Node*==NULL-未查找到 Node* search(Node* node, Key key){ if( node == NULL){//递归终止条件 return NULL; } if(node->key == key) return node; else if(key key) //key < node->key //查找node的左子树 return search(node->left, key); else //key > node->key //查找node的右子树 return search(node->right, key); } [二叉搜索树的遍历] 深度优先遍历(DFS) 前序遍历先访问当前节点，再访问左子树，再访问右子树中序遍历向访问左子树，再访问根节点，再访问右子树后序遍历先访问左子树，再访问右子树，再访问根节点

例如在这里插入图片描述前序遍历：28，16，13，22，30，29，42 中序遍历：13，16，22，28，29，30，42 （从小到大排序）后序遍历：13，22，16，29，42，30，28 释放二叉树

[代码实现] 前序遍历 //用户调用，公有函数 void preOrder(){ //调用递归函数preOrder，私有函数 preOrder(root); } //递归函数，私有函数 //在以root为根的二叉搜索树中进行前序遍历 void preOrder(Node* node){ if(node != NULL){ coutleft); coutright); coutkey; } //递归函数，私有函数 //查找以node为根节点的二叉搜索树中的key的最大值 //返回值：最大值的节点 Node* maximum(Node* node){ if(node->right == NULL) return node; return maximum(node->right); }

最小值

//用户调用，公有函数 Key minimum(){ assert(count > 0); Node* node = minimum(root); return node->key; } //递归函数，私有函数 //查找以node为根节点的二叉搜索树中的key的最小值 //返回值：最大值的节点 Node* minimum(Node* node){ if(node->left == NULL) return node; return minimum(node->left); } [删除二叉搜索树中的最大值或最小值]

若删除的最大值（最小值）为叶子节点，那么直接删除即可；若删除的节点不是叶子节点，那么删除该节点后，将该节点左（右）子树上移，代替删除的节点即可。

[过程演示]

删除最小值为叶子结点，直接删除即可在这里插入图片描述非叶子节点删除最大值同理

[代码实现]

删除最小值

//用户调用，公有函数 void removeMin(){ if(root) root = removeMin(root); } //递归调用，私有函数 //定义：删除以node为根节点的二叉搜索树的最小节点 //返回值：返回删除最小节点后的二叉树的根 Node* removeMin(Node* node){ if(node->left == NULL){ Node* rightNode = node->right; delete node; count--; return rightNode; } node->left = removeMin(node->left); return node; }

删除最大值

//用户调用，公有函数 void removeMax(){ if(root) root = removeMax(root); } //递归调用，私有函数 //定义：删除以node为根节点的二叉搜索树的最大节点 //返回值：返回删除最大节点后的二叉树的根 Node* removeMax(Node* node){ if(node->right == NULL){ Node* leftNode = node->left; delete node; count--; return leftNode; } node->right = removeMax(node->right); return node; } [删除二叉搜索树中的任意节点] 删除叶子节点——直接删除即可删除只有左孩子的节点——与删除最大、小节点类似删除只有右孩子的节点——与删除最大、小节点类似删除左右都有孩子的节点——Hubbard Deletion [Hubbard Deletion]

若想要删除节点58 在这里插入图片描述首先，我们需要重新找到一个节点代替58，如何找到代替58的节点？ [分析] 根据二叉搜索树的性质，我们可以得知，58左子树的所有节点一定小于58，右子树的所有节点一定大于58，为了维护二叉搜索树的定义，我们要保证代替58的节点s，应当大于58的左子树所有节点，为满足此条件，我们应当在58的右子树找，且小于58的右子树所有节点，为满足此条件，我们应当找到58右子树中的最小值。在这里插入图片描述找到代替58的节点后，先将58右子树的最小值s拷贝一份，然后将图中的s节点删除，随后，将拷贝的用拷贝的节点代替58 拷贝的节点连接58的左子树和右子树最后删除58节点即可，完成操作。

[代码实现] //用户调用，公有函数 void removeNode(Key key){ root = removeNode(root,key); } //递归调用，私有函数 //定义：删除以node为根节点的键值为key的节点 //返回值：返回删除节点的的根节点 Node* removeNode(Node* node, Key key){ if(node == NULL) return NULL; if(key key){//查找键值为key的节点 node->left = removeNode(node->left, key); return node; } else if(key > node->key){//查找键值为key的节点 node->right = removeNode(node->right, key); return node; } else{//查找到待删除的键值为key的节点 if(node->left == NULL){//node的左子树为空 Node* rightNode = node->right; delete node; count--; return rightNode; } else if(node->right == NULL){//node的右子树为空 Node* leftNode = node->left; delete node; count--; return leftNode; } else{//node的左右子树均不为空 Node* successor = new Node(minimum(node->right));//拷贝右子树最小值 count++;//维护count，因为删除最小值有count-- successor->right = removeMin(node->right);//连接待删除结点右子树 successor->left = node->left;//连接待删除节点左子树 delete node;//删除节点 count--; return successor; } } } 想说的话

本期主要是介绍了二叉搜索树的定义，以及涉及了二分搜索树的类，在类内完成了一些基本的操作，如，插入，查找，删除。下期更新利用二分搜索树的顺序性，完成一些进阶操作，即，floor，ceil，rank，select。大家加油~

【本文地址】

二分搜索树及基本操作(c++代码实现)

二分搜索树及基本操作(c++代码实现)

今日新闻

推荐新闻