小白学算法4.1

2022-07-18 14:25| 来源: 网络整理| 查看: 265

小白学算法4.1——二叉查找树

标签：小白学算法

1.什么是二叉查找树(Binary Search Tree)

二叉查找树是一种特殊的二叉树，相对于普通的二叉树，其有如下特点：

若任意结点的左子树不空，则左子树上所有结点的值均小于它的根结点的值任意结点的右子树不空，则右子树上所有结点的值均大于它的根结点的值任意结点的左、右子树也分别为二叉查找树没有键值相等的结点

二叉查找树相比于其他数据结构的优势在于查找、插入的时间复杂度较低，为 O(logN) 。二叉查找树常见的操作有插入、查找、取最值、删除、排名、范围查找等操作，本文主要讲解前四种操作。

本文中字符为key，数值为value，结点定义如下：

class Node { public: Node(char k, int v)//constructor { key = k; value = v; left = NULL; right = NULL; } char key; int value; Node* left; Node* right; //往往还会定义一个结点计数器 //int count;count = left->count + right->count + 1 };

二叉查找树定义如下：

class BST { public: int get(char key); void put(char key, int value); BST() {root = NULL;}//constructor int min(); int max(); void delete_min(); void delete_node(char key); Node* root; private: Node* put(Node* x, char key, int value); int get(Node* x, char key); Node* min(Node* x); Node* max(Node* x); Node* delete_min(Node* x); Node* delete_node(Node* x, char key); };

此处应当有一个析构函数的，防止内存泄露。

1.添加

添加元素的具体算法如下：

如果当前结点为空，新建结点添加元素当添加元素大于当前结点键时，向右走当添加元素小于当前结点键时，向左走当添加元素等于当前结点键时，更新当前结点的值

根结点是第一个当前结点，重复上面的步骤，直到元素添加完成。

void BST::put(char key, int value) { root = put(root, key, value); } Node* BST::put(Node* x, char key, int value) { //如果不存在键值为key的结点，新建一个结点 if (x == NULL) { Node* pNode = new Node(key, value); return pNode; } //key大于当前结点键值，向右走；小于当前结点键值，向左走；等于则更新 if (key > x->key) x->right = put(x->right, key, value); else if (key < x->key) x->left = put(x->left, key, value); else x->value = value; return x; } 2.查找

查找有两种结果，分别是命中(返回value)与未命中(返回NULL)。查找的算法具体如下：

如果当前结点为空，则未命中如果查找键大于当前结点键，向右走如果查找键小于当前结点键，向左走如果查找键等于当前结点键，返回当前结点value

根结点是第一个当前结点，递归上面的步骤，直到查找完成。

int BST::get(char key) { return get(root, key); } int BST::get(Node* x, char key) { //未命中返回NULL if (x == NULL) return NULL; //大于当前key，向右走；小于当前key，向左走；等于则返回 if (key > x->key) return get(x->right, key); else if (key < x->key) return get(x->left, key); else return x->value; } 3.取最值

取最值有两个操作，一个是取最大值，一个是取最小值。取最小值从根结点开始，不断地向左走，直到走到最左边的结点；取最大值从根结点开始，不断地向右走，直到走到最右边的结点。

int BST::min() { return min(root)->value; } Node* BST::min(Node* x) { if (x->left != NULL) return min(x->left); return x; } int BST::max() { return max(root)->value; } Node* BST::max(Node* x) { if (x->right != NULL) return max(x->right); return x; } 4.删除

删除操作较为麻烦，因为在删除结点后，还要保证二叉查找树的有序性，即左小右大。先考虑简单的情况：删除最小值结点。

最小值结点一定是最左边的结点，如果最小值结点没有右子结点，则直接删除最小值结点；如果有右子结点，则在删除最小值结点后，将其右子结点作为其父结点的左子结点。

void BST::delete_min() { root = delete_min(root); } Node* BST::delete_min(Node* x) { if (x->left == NULL) { //释放空间 Node* temp = x->right; delete x; x = NULL; return temp; } x->left = delete_min(x->left); return x; }

在delete_min之上，考虑删除任意结点的问题，算法如下：

如果没有要删除的结点，则不作任何操作根据当前结点的键值和待删除结点的大小关系，决定向左走还是向右走，直到找到待删除结点，记为node1如果node1没有子结点则直接删除如果node1只有一个子结点，直接用其子结点代替node1如果有两个子结点，需要先删除node1，用后选择一个子结点将其代替，记为node2，node2需要大于左子树中的任意一个结点，小于右子树中的任意一个结点，比较简单的一个方法就是从node1的右子树中选出最小结点作为node2 void BST::delete_node(char key) { root = delete_node(root, key); } Node* BST::delete_node(Node* x, char key) { if (x == NULL) return NULL;//无该元素则不进行任何操作 if (key < x->key) x->left = delete_node(x->left, key); else if (key > x->key) x->right = delete_node(x->right, key); else//删除结点 { if (x->right == NULL) return x->left; if (x->left == NULL) return x->right; Node* t = x; t = min(x->right); x->key = t->key; x->value = t->value; x->right = delete_min(x->right); } return x; } 6.实际操作

对二叉查找树进行中序遍历，会得到一个从小到大的序列，可以用这个方法检查一下代码的正确性。在main()函数中，执行以下操作：

建立二叉查找树中序遍历输出二叉查找树输出二叉查找树中最小键的值删除最小键结点中序遍历输出二叉查找树删除结点'E'中序遍历输出二叉查找树 //递归实现中序遍历 void mid_order(Node* x) { if (x) { mid_order(x->left); cout

【本文地址】

公司简介

联系我们