一、二叉树搜索树1.1 二叉搜索树的概念二叉搜索树(BST、Binary Search Tree)又称二叉排序树或二叉查找树可以是一棵空树也可以是具有以下性质的特殊二叉树1.如果左子树不为空那么左子树上所有的节点的值(key)都小于根节点的值(key)。 2.如果右子树不为空那么右子树上所有的节点的值(key)都大于根节点的值(key)。 3.左右子树也是一棵搜索二叉树。 4.搜索二叉树不允许有重复的值(key)。默认的二叉搜索树走中序遍历结果是升序。1.2 二叉搜索树的操作对于下面这棵二叉搜索树int a[] { 8,3,1,10,6,4,7,14,13 };1.2.1二叉搜索树的查找1.如果要查找的值(key)比根节点的值(key)要大那么往右子树继续查找如果比根节点的值(key) 小那么往左子树查找。 2.最多查找高度次如果走到空还没有找到说明这个值不在该二叉搜索树里。1.2.2二叉搜索树的插入两种情况 1.树为空则直接新增一个节点并将该节点赋值给根节点。 2.树不为空先查找插入位置然后插入新节点。依次插入16、0。插入成功返回true插入失败返回false。1.2.3二叉搜索树的删除首先查找要删除的值是否在树中如果不在则返回false。如果在树中又可能分为以下四种情况 1.被删除的节点没有左右孩子。 1.被删除的节点只有左孩子。 2.被删除的节点只有右孩子。 3.被删除的节点既有左孩子又有右孩子。情况1可以和情况2或3合并。合并以后的新情况1.被删除的节点只有左孩子左孩子可能为空树。 2.被删除的节点只有右孩子。 3.被删除的节点既有左孩子又有右孩子。情况1.被删除的节点只有左孩子左孩子可能为空树。情况1的删除方法情况1存在的特殊情况以及处理方法根节点只有左子树情况2.被删除的节点只有右孩子。情况2的处理方式以及情况2的特殊情况的处理方式情况3被删除的节点既有左孩子又有有孩子。情况3的处理方法替换法 1.找到左子树的最大节点(最右节点)或右子树的最小节点(最左节点)。 2.左子树的最右节点必定是没有右子树的右子树的最左节点必定是没有左子树的。 3.将被删除的节点替换最右节点或最左节点。 4.删除替换后的最右节点或最左节点。以节点8和找右子树的最左节点为例二、二叉搜索树的实现2.1 二叉搜索树的框架结构1.二叉树的每个节点的结构包含模板参数K、一个显示构造函数、节点的值_key、指向左孩子的节点指针_left、指向右孩子的 节点指针_right。//1.二叉树的每个节点的结构 templateclass K struct BSTreeNode { //构造函数 BSTreeNode(const K keyK()) :_key(key) ,_left(nullptr) ,_right(nullptr) {} //成员变量 K _key; //key值 BSTreeNodeK* _left; //指向左孩子 BSTreeNodeK* _right; //指向右孩子 };2.二叉树的结构包含模板参数K、对节点名称的重命名根节点_root默认成员函数、功能成员函数//模板参数K templateclass K class BSTree { //对节点重命名 typedef BSTreeNodeK Node; public: //成员函数 //1.默认成员函数 //构造函数 BSTree(); //拷贝构造函数 BSTree(const BSTreeK tree); //赋值重载函数 BSTreeK operator(BSTreeK tree); //析构函数 ~BSTree(); //... //2.功能成员函数 //查找 bool Find(const K key); //插入 bool Insert(const K key); //删除 bool Erase(const K key); //中序遍历 void InOrder(); //... private: //成员变量 Node* root nullptr; };其中功能成员函数又有递归版本和非递归版本。2.2 实现2.2.1 Find查找非递归版本//查找 bool Find(const K key) { Node* cur _root; while (cur ! nullptr) { if (key cur-_key) { //继续去右子树查找 cur cur-_right; } else if (key cur-_key) { //继续去左子树查找 cur cur-_left; } else { //找到了 return true; } } //没找到 return false; }递归版本//递归版本的查找 bool FindR(const K key) { return _FindR(_root, key); } bool _FindR(Node* root, const K key) { if (root nullptr) { return false; } if (root-_key key) { return true; } else if (root-_key key) { return _FindR(root-_right, key); } else { return _FindR(root-_left, key); } }2.2.2 插入Insert非递归版本//插入 bool Insert(const K key) { //如果根为空直接插入新节点 if (_root nullptr) { _root new Node(key); return true; } Node* cur _root; //记录cur的父节点 Node* prev _root; while (cur ! nullptr) { prev cur; if (key cur-_key) { //继续去右子树 cur cur-_right; } else if (key cur-_key) { //继续去左子树 cur cur-_left; } else { //搜索二叉树不允许有重复值 return false; } } //插入 if (key prev-_key) { prev-_right new Node(key); } else { prev-_left new Node(key); } return true; }递归版本递归版本的插入使用了引用传参可以在找到插入位置时修改root可以直接插入//递归版本 bool InsertR(const K key) { return _InsertR(_root, key); } //引用传参方便插入 bool _InsertR(Node* root, const K key) { if (root nullptr) { //已经找到插入位置直接插入 root new Node(key); return true; } if (root-_key key) { //搜索二叉树不允许有重复值 return false; } else if (root-_key key) { _InsertR(root-_left, key); } else { _InsertR(root-_right, key); } return true; }2.2.3 删除非递归版本//删除 bool Erase(const K key) { Node* cur _root; //指向cur的父节点 Node* prev _root; while (curcur-_key!key) { prev cur; if (cur-_key key) { //去左子树 cur cur-_left; } else if (cur-_key key) { //去右子树 cur cur-_right; } } if (cur nullptr) { //没找到要删除的节点 return false; } //找到了要删除的节点 //开始删除 if (cur-_left cur-_right) { //左右孩子均存在 //1.找右子树的最左节点 Node* tmp cur-_right; Node* parent cur; while (tmp-_left ! nullptr) { parent tmp; tmp tmp-_left; } //交换最左节点和cur节点的值_key swap(cur-_key, tmp-_key); //如果parent没有动说明cur的第一个右孩子就是最左节点 if (parent cur) { cur-_right tmp-_right; } else { //如果parent动了那么tmp就必定是parent的左孩子 parent-_left tmp-_right; } delete tmp; } else if (cur-_right) { //只有右孩子 //1.特殊情况如果cur等于_root if (cur _root) { _root cur-_right; } else { //判断cur是父节点的左孩子还是右孩子 if (prev-_key cur-_key) { //是左孩子 prev-_left cur-_right; } else { //是右孩子 prev-_right cur-_right; } } delete cur; } else { //只有左孩子或没有孩子 if (cur _root) { _root cur-_left; } else { //判断cur是父节点的左孩子还是右孩子 if (prev-_key cur-_key) { //是左孩子 prev-_left cur-_left; } else { //是右孩子 prev-_right cur-_left; } } delete cur; } return true; }递归版本递归版本的删除也使用的引用传参可以更方便直接删除节点。//删除的递归版本 bool EraseR(const K key) { return _EraseR(_root, key); } bool _EraseR(Node* root, const K key) { if (root nullptr) { //没找到要删除的节点 return false; } if (root-_key key) { return _EraseR(root-_left, key); } else if (root-_key key) { return _EraseR(root-_right, key); } else { Node* cur root; //找到了要删除的节点 if (root-_left root-_right) { //有左右孩子 //1.找右子树的最左节点 Node* tmp root-_right; while (tmp-_left ! nullptr) { tmp tmp-_left; } //交换最左节点和cur节点的值_key swap(root-_key, tmp-_key); //cur的右子树仍然能确保是一棵二叉搜索树在cur的右子树里递归删除key _EraseR(root-_right, key); } else if (root-_right) { //只有右孩子 root root-_right; delete cur; } else { //只有左孩子或没有孩子 root root-_left; delete cur; } return true; } }2.2.4 中序遍历递归版本void InOrder() { _InOrderR(_root); } void _InOrderR(Node* root) { if (root nullptr) { return; } _InOrderR(root-_left); cout root-_key ; _InOrderR(root-_right); }2.2.5 构造函数//构造函数 BSTree() :_root(nullptr) {}2.2.6 拷贝构造函数二叉搜索树的拷贝构造需要深拷贝。//拷贝构造函数 BSTree(const BSTreeK tree) { //需要进行深拷贝 copy(_root, tree._root); } //root2拷贝至root1 void copy(Node* root1, Node* root2) { if (root2 nullptr) { root1 nullptr; return; } root1 new Node(root2-_key); copy(root1-_left, root2-_left); copy(root1-_right, root2-_right); }2.2.7 赋值重载函数//赋值重载函数 BSTreeK operator(BSTreeK tree) { swap(_root, tree._root); return *this; }2.2.8 析构函数//析构函数 ~BSTree() { destroy(_root); } void destroy(Node* root) { if (root nullptr) { return; } destroy(root-_left); destroy(root-_right); delete root; root nullptr; }2.2.9 整体代码//1.二叉树的每个节点的结构 templateclass K struct BSTreeNode { //构造函数 BSTreeNode(const K keyK()) :_key(key) ,_left(nullptr) ,_right(nullptr) {} //成员变量 K _key; //key值 BSTreeNodeK* _left; //指向左孩子 BSTreeNodeK* _right; //指向右孩子 }; //模板参数K templateclass K class BSTree { //对节点重命名 typedef BSTreeNodeK Node; public: //构造函数 BSTree() :_root(nullptr) {} //拷贝构造函数 BSTree(const BSTreeK tree) { //需要进行深拷贝 copy(_root, tree._root); } //root2拷贝至root1 void copy(Node* root1, Node* root2) { if (root2 nullptr) { root1 nullptr; return; } root1 new Node(root2-_key); copy(root1-_left, root2-_left); copy(root1-_right, root2-_right); } //赋值重载函数 BSTreeK operator(BSTreeK tree) { swap(_root, tree._root); return *this; } //析构函数 ~BSTree() { destroy(_root); } void destroy(Node* root) { if (root nullptr) { return; } destroy(root-_left); destroy(root-_right); delete root; root nullptr; } //2.功能成员函数 //查找 bool Find(const K key) { Node* cur _root; while (cur ! nullptr) { if (key cur-_key) { //继续去右子树查找 cur cur-_right; } else if (key cur-_key) { //继续去左子树查找 cur cur-_left; } else { //找到了 return true; } } //没找到 return false; } //递归版本的查找 bool FindR(const K key) { return _FindR(_root, key); } bool _FindR(Node* root, const K key) { if (root nullptr) { return false; } if (root-_key key) { return true; } else if (root-_key key) { return _FindR(root-_right, key); } else { return _FindR(root-_left, key); } } //插入 bool Insert(const K key) { //如果根为空直接插入新节点 if (_root nullptr) { _root new Node(key); return true; } Node* cur _root; //记录cur的父节点 Node* prev _root; while (cur ! nullptr) { prev cur; if (key cur-_key) { //继续去右子树 cur cur-_right; } else if (key cur-_key) { //继续去左子树 cur cur-_left; } else { //搜索二叉树不允许有重复值 return false; } } //插入 if (key prev-_key) { prev-_right new Node(key); } else { prev-_left new Node(key); } return true; } //递归版本的插入使用了引用传参可以在找到插入位置时修改root可以直接插入 //递归版本 bool InsertR(const K key) { return _InsertR(_root, key); } //引用传参方便插入 bool _InsertR(Node* root, const K key) { if (root nullptr) { //已经找到插入位置直接插入 root new Node(key); return true; } if (root-_key key) { //搜索二叉树不允许有重复值 return false; } else if (root-_key key) { _InsertR(root-_left, key); } else { _InsertR(root-_right, key); } return true; } //删除 bool Erase(const K key) { Node* cur _root; //指向cur的父节点 Node* prev _root; while (curcur-_key!key) { prev cur; if (cur-_key key) { //去左子树 cur cur-_left; } else if (cur-_key key) { //去右子树 cur cur-_right; } } if (cur nullptr) { //没找到要删除的节点 return false; } //找到了要删除的节点 //开始删除 if (cur-_left cur-_right) { //左右孩子均存在 //1.找右子树的最左节点 Node* tmp cur-_right; Node* parent cur; while (tmp-_left ! nullptr) { parent tmp; tmp tmp-_left; } //交换最左节点和cur节点的值_key swap(cur-_key, tmp-_key); //如果parent没有动说明cur的第一个右孩子就是最左节点 if (parent cur) { cur-_right tmp-_right; } else { //如果parent动了那么tmp就必定是parent的左孩子 parent-_left tmp-_right; } delete tmp; } else if (cur-_right) { //只有右孩子 //1.特殊情况如果cur等于_root if (cur _root) { _root cur-_right; } else { //判断cur是父节点的左孩子还是右孩子 if (prev-_key cur-_key) { //是左孩子 prev-_left cur-_right; } else { //是右孩子 prev-_right cur-_right; } } delete cur; } else { //只有左孩子或没有孩子 if (cur _root) { _root cur-_left; } else { //判断cur是父节点的左孩子还是右孩子 if (prev-_key cur-_key) { //是左孩子 prev-_left cur-_left; } else { //是右孩子 prev-_right cur-_left; } } delete cur; } return true; } //删除的递归版本 bool EraseR(const K key) { return _EraseR(_root, key); } bool _EraseR(Node* root, const K key) { if (root nullptr) { //没找到要删除的节点 return false; } if (root-_key key) { return _EraseR(root-_left, key); } else if (root-_key key) { return _EraseR(root-_right, key); } else { Node* cur root; //找到了要删除的节点 if (root-_left root-_right) { //有左右孩子 //1.找右子树的最左节点 Node* tmp root-_right; while (tmp-_left ! nullptr) { tmp tmp-_left; } //交换最左节点和cur节点的值_key swap(root-_key, tmp-_key); //cur的右子树仍然能确保是一棵二叉搜索树在cur的右子树里递归删除key _EraseR(root-_right, key); } else if (root-_right) { //只有右孩子 root root-_right; delete cur; } else { //只有左孩子或没有孩子 root root-_left; delete cur; } return true; } } //中序遍历 void InOrder() { _InOrderR(_root); } void _InOrderR(Node* root) { if (root nullptr) { return; } _InOrderR(root-_left); cout root-_key ; _InOrderR(root-_right); } //... private: //成员变量 Node* _root nullptr; };三、二叉搜索树的应用3.1 K模型K模型K模型即只有key作为关键码结构中只要存储key即可关键码即为需要搜到的值。比如给一个单词word判断该单词是否拼写正确具体方式如下:1.以词库里所有单词作为key构建一棵搜索二叉树。 2.在二叉树里检索该单词word是否存在存在则拼写正确如果不存在则是该单词拼写错误。3.2 K-V模型KV模型每一个关键码key都有一个与之对应的value即key,value的键值对。比如英汉词典中的英文和汉语就是对应关系通过英文可以快速找到对应的中文wordchinese。再比如统计单词单词和单词出现的次数也是一对key-value模型wordcount。3.3 改造K模型为K-V模型删除不需要改变每个节点的结构需要改变插入也只需要新增一个参数value和new节点时的参 数find返回值改为找到的节点的地址遍历只需要多打印一个value。//1.K-V模型的二叉树的每个节点的结构 templateclass K,class V struct BSTreeNode { //构造函数 BSTreeNode(const K key K(),const V valueV()) :_key(key) ,_value(value) , _left(nullptr) , _right(nullptr) {} //成员变量 K _key; //key值 V _value; BSTreeNodeK,V* _left; //指向左孩子 BSTreeNodeK,V* _right; //指向右孩子 }; //模板参数K,V templateclass K,class V class BSTree { //对节点重命名 typedef BSTreeNodeK,V Node; public: //查找 Node* Find(const K key) { Node* cur _root; while (cur ! nullptr) { if (key cur-_key) { //继续去右子树查找 cur cur-_right; } else if (key cur-_key) { //继续去左子树查找 cur cur-_left; } else { //找到了返回当前节点 return cur; } } //没找到 return nullptr; } //插入 bool Insert(const K key,const V value) { //如果根为空直接插入新节点 if (_root nullptr) { _root new Node(key,value); return true; } Node* cur _root; //记录cur的父节点 Node* prev _root; while (cur ! nullptr) { prev cur; if (key cur-_key) { //继续去右子树 cur cur-_right; } else if (key cur-_key) { //继续去左子树 cur cur-_left; } else { //搜索二叉树不允许有重复值 return false; } } //插入 if (key prev-_key) { prev-_right new Node(key, value); } else { prev-_left new Node(key, value); } return true; } //删除 bool Erase(const K key) { Node* cur _root; //指向cur的父节点 Node* prev _root; while (cur cur-_key ! key) { prev cur; if (cur-_key key) { //去左子树 cur cur-_left; } else if (cur-_key key) { //去右子树 cur cur-_right; } } if (cur nullptr) { //没找到要删除的节点 return false; } //找到了要删除的节点 //开始删除 if (cur-_left cur-_right) { //左右孩子均存在 //1.找右子树的最左节点 Node* tmp cur-_right; Node* parent cur; while (tmp-_left ! nullptr) { parent tmp; tmp tmp-_left; } //交换最左节点和cur节点的值_key swap(cur-_key, tmp-_key); //如果parent没有动说明cur的第一个右孩子就是最左节点 if (parent cur) { cur-_right tmp-_right; } else { //如果parent动了那么tmp就必定是parent的左孩子 parent-_left tmp-_right; } delete tmp; } else if (cur-_right) { //只有右孩子 //1.特殊情况如果cur等于_root if (cur _root) { _root cur-_right; } else { //判断cur是父节点的左孩子还是右孩子 if (prev-_key cur-_key) { //是左孩子 prev-_left cur-_right; } else { //是右孩子 prev-_right cur-_right; } } delete cur; } else { //只有左孩子或没有孩子 if (cur _root) { _root cur-_left; } else { //判断cur是父节点的左孩子还是右孩子 if (prev-_key cur-_key) { //是左孩子 prev-_left cur-_left; } else { //是右孩子 prev-_right cur-_left; } } delete cur; } return true; } //中序遍历 void InOrder() { _InOrderR(_root); } void _InOrderR(Node* root) { if (root nullptr) { return; } _InOrderR(root-_left); cout root-_key root-_value ; _InOrderR(root-_right); } //... private: //成员变量 Node* _root nullptr; };四、二叉搜索树的性能分析插入和删除都需要先进行查找因此查找效率变成了代表二叉搜索树的各个操作的性能。二叉搜索树查找的时间复杂度O(N)1.当二叉搜索树接近一棵完全二叉树或满二叉树时查找效率为O(log(N))。 2.当二叉搜索树是以有序的顺序插入时查找效率为O(N)。在最坏情况下二叉搜索树退化为了一只单支树搜索性能就失去了时间复杂度是按照最坏的情况进行计算的因此二叉搜索树的时间复杂度为O(N)。
C++-二叉搜索树
发布时间：2026/5/27 21:41:13
一、二叉树搜索树1.1 二叉搜索树的概念二叉搜索树(BST、Binary Search Tree)又称二叉排序树或二叉查找树可以是一棵空树也可以是具有以下性质的特殊二叉树1.如果左子树不为空那么左子树上所有的节点的值(key)都小于根节点的值(key)。 2.如果右子树不为空那么右子树上所有的节点的值(key)都大于根节点的值(key)。 3.左右子树也是一棵搜索二叉树。 4.搜索二叉树不允许有重复的值(key)。默认的二叉搜索树走中序遍历结果是升序。1.2 二叉搜索树的操作对于下面这棵二叉搜索树int a[] { 8,3,1,10,6,4,7,14,13 };1.2.1二叉搜索树的查找1.如果要查找的值(key)比根节点的值(key)要大那么往右子树继续查找如果比根节点的值(key) 小那么往左子树查找。 2.最多查找高度次如果走到空还没有找到说明这个值不在该二叉搜索树里。1.2.2二叉搜索树的插入两种情况 1.树为空则直接新增一个节点并将该节点赋值给根节点。 2.树不为空先查找插入位置然后插入新节点。依次插入16、0。插入成功返回true插入失败返回false。1.2.3二叉搜索树的删除首先查找要删除的值是否在树中如果不在则返回false。如果在树中又可能分为以下四种情况 1.被删除的节点没有左右孩子。 1.被删除的节点只有左孩子。 2.被删除的节点只有右孩子。 3.被删除的节点既有左孩子又有右孩子。情况1可以和情况2或3合并。合并以后的新情况1.被删除的节点只有左孩子左孩子可能为空树。 2.被删除的节点只有右孩子。 3.被删除的节点既有左孩子又有右孩子。情况1.被删除的节点只有左孩子左孩子可能为空树。情况1的删除方法情况1存在的特殊情况以及处理方法根节点只有左子树情况2.被删除的节点只有右孩子。情况2的处理方式以及情况2的特殊情况的处理方式情况3被删除的节点既有左孩子又有有孩子。情况3的处理方法替换法 1.找到左子树的最大节点(最右节点)或右子树的最小节点(最左节点)。 2.左子树的最右节点必定是没有右子树的右子树的最左节点必定是没有左子树的。 3.将被删除的节点替换最右节点或最左节点。 4.删除替换后的最右节点或最左节点。以节点8和找右子树的最左节点为例二、二叉搜索树的实现2.1 二叉搜索树的框架结构1.二叉树的每个节点的结构包含模板参数K、一个显示构造函数、节点的值_key、指向左孩子的节点指针_left、指向右孩子的 节点指针_right。//1.二叉树的每个节点的结构 templateclass K struct BSTreeNode { //构造函数 BSTreeNode(const K keyK()) :_key(key) ,_left(nullptr) ,_right(nullptr) {} //成员变量 K _key; //key值 BSTreeNodeK* _left; //指向左孩子 BSTreeNodeK* _right; //指向右孩子 };2.二叉树的结构包含模板参数K、对节点名称的重命名根节点_root默认成员函数、功能成员函数//模板参数K templateclass K class BSTree { //对节点重命名 typedef BSTreeNodeK Node; public: //成员函数 //1.默认成员函数 //构造函数 BSTree(); //拷贝构造函数 BSTree(const BSTreeK tree); //赋值重载函数 BSTreeK operator(BSTreeK tree); //析构函数 ~BSTree(); //... //2.功能成员函数 //查找 bool Find(const K key); //插入 bool Insert(const K key); //删除 bool Erase(const K key); //中序遍历 void InOrder(); //... private: //成员变量 Node* root nullptr; };其中功能成员函数又有递归版本和非递归版本。2.2 实现2.2.1 Find查找非递归版本//查找 bool Find(const K key) { Node* cur _root; while (cur ! nullptr) { if (key cur-_key) { //继续去右子树查找 cur cur-_right; } else if (key cur-_key) { //继续去左子树查找 cur cur-_left; } else { //找到了 return true; } } //没找到 return false; }递归版本//递归版本的查找 bool FindR(const K key) { return _FindR(_root, key); } bool _FindR(Node* root, const K key) { if (root nullptr) { return false; } if (root-_key key) { return true; } else if (root-_key key) { return _FindR(root-_right, key); } else { return _FindR(root-_left, key); } }2.2.2 插入Insert非递归版本//插入 bool Insert(const K key) { //如果根为空直接插入新节点 if (_root nullptr) { _root new Node(key); return true; } Node* cur _root; //记录cur的父节点 Node* prev _root; while (cur ! nullptr) { prev cur; if (key cur-_key) { //继续去右子树 cur cur-_right; } else if (key cur-_key) { //继续去左子树 cur cur-_left; } else { //搜索二叉树不允许有重复值 return false; } } //插入 if (key prev-_key) { prev-_right new Node(key); } else { prev-_left new Node(key); } return true; }递归版本递归版本的插入使用了引用传参可以在找到插入位置时修改root可以直接插入//递归版本 bool InsertR(const K key) { return _InsertR(_root, key); } //引用传参方便插入 bool _InsertR(Node* root, const K key) { if (root nullptr) { //已经找到插入位置直接插入 root new Node(key); return true; } if (root-_key key) { //搜索二叉树不允许有重复值 return false; } else if (root-_key key) { _InsertR(root-_left, key); } else { _InsertR(root-_right, key); } return true; }2.2.3 删除非递归版本//删除 bool Erase(const K key) { Node* cur _root; //指向cur的父节点 Node* prev _root; while (curcur-_key!key) { prev cur; if (cur-_key key) { //去左子树 cur cur-_left; } else if (cur-_key key) { //去右子树 cur cur-_right; } } if (cur nullptr) { //没找到要删除的节点 return false; } //找到了要删除的节点 //开始删除 if (cur-_left cur-_right) { //左右孩子均存在 //1.找右子树的最左节点 Node* tmp cur-_right; Node* parent cur; while (tmp-_left ! nullptr) { parent tmp; tmp tmp-_left; } //交换最左节点和cur节点的值_key swap(cur-_key, tmp-_key); //如果parent没有动说明cur的第一个右孩子就是最左节点 if (parent cur) { cur-_right tmp-_right; } else { //如果parent动了那么tmp就必定是parent的左孩子 parent-_left tmp-_right; } delete tmp; } else if (cur-_right) { //只有右孩子 //1.特殊情况如果cur等于_root if (cur _root) { _root cur-_right; } else { //判断cur是父节点的左孩子还是右孩子 if (prev-_key cur-_key) { //是左孩子 prev-_left cur-_right; } else { //是右孩子 prev-_right cur-_right; } } delete cur; } else { //只有左孩子或没有孩子 if (cur _root) { _root cur-_left; } else { //判断cur是父节点的左孩子还是右孩子 if (prev-_key cur-_key) { //是左孩子 prev-_left cur-_left; } else { //是右孩子 prev-_right cur-_left; } } delete cur; } return true; }递归版本递归版本的删除也使用的引用传参可以更方便直接删除节点。//删除的递归版本 bool EraseR(const K key) { return _EraseR(_root, key); } bool _EraseR(Node* root, const K key) { if (root nullptr) { //没找到要删除的节点 return false; } if (root-_key key) { return _EraseR(root-_left, key); } else if (root-_key key) { return _EraseR(root-_right, key); } else { Node* cur root; //找到了要删除的节点 if (root-_left root-_right) { //有左右孩子 //1.找右子树的最左节点 Node* tmp root-_right; while (tmp-_left ! nullptr) { tmp tmp-_left; } //交换最左节点和cur节点的值_key swap(root-_key, tmp-_key); //cur的右子树仍然能确保是一棵二叉搜索树在cur的右子树里递归删除key _EraseR(root-_right, key); } else if (root-_right) { //只有右孩子 root root-_right; delete cur; } else { //只有左孩子或没有孩子 root root-_left; delete cur; } return true; } }2.2.4 中序遍历递归版本void InOrder() { _InOrderR(_root); } void _InOrderR(Node* root) { if (root nullptr) { return; } _InOrderR(root-_left); cout root-_key ; _InOrderR(root-_right); }2.2.5 构造函数//构造函数 BSTree() :_root(nullptr) {}2.2.6 拷贝构造函数二叉搜索树的拷贝构造需要深拷贝。//拷贝构造函数 BSTree(const BSTreeK tree) { //需要进行深拷贝 copy(_root, tree._root); } //root2拷贝至root1 void copy(Node* root1, Node* root2) { if (root2 nullptr) { root1 nullptr; return; } root1 new Node(root2-_key); copy(root1-_left, root2-_left); copy(root1-_right, root2-_right); }2.2.7 赋值重载函数//赋值重载函数 BSTreeK operator(BSTreeK tree) { swap(_root, tree._root); return *this; }2.2.8 析构函数//析构函数 ~BSTree() { destroy(_root); } void destroy(Node* root) { if (root nullptr) { return; } destroy(root-_left); destroy(root-_right); delete root; root nullptr; }2.2.9 整体代码//1.二叉树的每个节点的结构 templateclass K struct BSTreeNode { //构造函数 BSTreeNode(const K keyK()) :_key(key) ,_left(nullptr) ,_right(nullptr) {} //成员变量 K _key; //key值 BSTreeNodeK* _left; //指向左孩子 BSTreeNodeK* _right; //指向右孩子 }; //模板参数K templateclass K class BSTree { //对节点重命名 typedef BSTreeNodeK Node; public: //构造函数 BSTree() :_root(nullptr) {} //拷贝构造函数 BSTree(const BSTreeK tree) { //需要进行深拷贝 copy(_root, tree._root); } //root2拷贝至root1 void copy(Node* root1, Node* root2) { if (root2 nullptr) { root1 nullptr; return; } root1 new Node(root2-_key); copy(root1-_left, root2-_left); copy(root1-_right, root2-_right); } //赋值重载函数 BSTreeK operator(BSTreeK tree) { swap(_root, tree._root); return *this; } //析构函数 ~BSTree() { destroy(_root); } void destroy(Node* root) { if (root nullptr) { return; } destroy(root-_left); destroy(root-_right); delete root; root nullptr; } //2.功能成员函数 //查找 bool Find(const K key) { Node* cur _root; while (cur ! nullptr) { if (key cur-_key) { //继续去右子树查找 cur cur-_right; } else if (key cur-_key) { //继续去左子树查找 cur cur-_left; } else { //找到了 return true; } } //没找到 return false; } //递归版本的查找 bool FindR(const K key) { return _FindR(_root, key); } bool _FindR(Node* root, const K key) { if (root nullptr) { return false; } if (root-_key key) { return true; } else if (root-_key key) { return _FindR(root-_right, key); } else { return _FindR(root-_left, key); } } //插入 bool Insert(const K key) { //如果根为空直接插入新节点 if (_root nullptr) { _root new Node(key); return true; } Node* cur _root; //记录cur的父节点 Node* prev _root; while (cur ! nullptr) { prev cur; if (key cur-_key) { //继续去右子树 cur cur-_right; } else if (key cur-_key) { //继续去左子树 cur cur-_left; } else { //搜索二叉树不允许有重复值 return false; } } //插入 if (key prev-_key) { prev-_right new Node(key); } else { prev-_left new Node(key); } return true; } //递归版本的插入使用了引用传参可以在找到插入位置时修改root可以直接插入 //递归版本 bool InsertR(const K key) { return _InsertR(_root, key); } //引用传参方便插入 bool _InsertR(Node* root, const K key) { if (root nullptr) { //已经找到插入位置直接插入 root new Node(key); return true; } if (root-_key key) { //搜索二叉树不允许有重复值 return false; } else if (root-_key key) { _InsertR(root-_left, key); } else { _InsertR(root-_right, key); } return true; } //删除 bool Erase(const K key) { Node* cur _root; //指向cur的父节点 Node* prev _root; while (curcur-_key!key) { prev cur; if (cur-_key key) { //去左子树 cur cur-_left; } else if (cur-_key key) { //去右子树 cur cur-_right; } } if (cur nullptr) { //没找到要删除的节点 return false; } //找到了要删除的节点 //开始删除 if (cur-_left cur-_right) { //左右孩子均存在 //1.找右子树的最左节点 Node* tmp cur-_right; Node* parent cur; while (tmp-_left ! nullptr) { parent tmp; tmp tmp-_left; } //交换最左节点和cur节点的值_key swap(cur-_key, tmp-_key); //如果parent没有动说明cur的第一个右孩子就是最左节点 if (parent cur) { cur-_right tmp-_right; } else { //如果parent动了那么tmp就必定是parent的左孩子 parent-_left tmp-_right; } delete tmp; } else if (cur-_right) { //只有右孩子 //1.特殊情况如果cur等于_root if (cur _root) { _root cur-_right; } else { //判断cur是父节点的左孩子还是右孩子 if (prev-_key cur-_key) { //是左孩子 prev-_left cur-_right; } else { //是右孩子 prev-_right cur-_right; } } delete cur; } else { //只有左孩子或没有孩子 if (cur _root) { _root cur-_left; } else { //判断cur是父节点的左孩子还是右孩子 if (prev-_key cur-_key) { //是左孩子 prev-_left cur-_left; } else { //是右孩子 prev-_right cur-_left; } } delete cur; } return true; } //删除的递归版本 bool EraseR(const K key) { return _EraseR(_root, key); } bool _EraseR(Node* root, const K key) { if (root nullptr) { //没找到要删除的节点 return false; } if (root-_key key) { return _EraseR(root-_left, key); } else if (root-_key key) { return _EraseR(root-_right, key); } else { Node* cur root; //找到了要删除的节点 if (root-_left root-_right) { //有左右孩子 //1.找右子树的最左节点 Node* tmp root-_right; while (tmp-_left ! nullptr) { tmp tmp-_left; } //交换最左节点和cur节点的值_key swap(root-_key, tmp-_key); //cur的右子树仍然能确保是一棵二叉搜索树在cur的右子树里递归删除key _EraseR(root-_right, key); } else if (root-_right) { //只有右孩子 root root-_right; delete cur; } else { //只有左孩子或没有孩子 root root-_left; delete cur; } return true; } } //中序遍历 void InOrder() { _InOrderR(_root); } void _InOrderR(Node* root) { if (root nullptr) { return; } _InOrderR(root-_left); cout root-_key ; _InOrderR(root-_right); } //... private: //成员变量 Node* _root nullptr; };三、二叉搜索树的应用3.1 K模型K模型K模型即只有key作为关键码结构中只要存储key即可关键码即为需要搜到的值。比如给一个单词word判断该单词是否拼写正确具体方式如下:1.以词库里所有单词作为key构建一棵搜索二叉树。 2.在二叉树里检索该单词word是否存在存在则拼写正确如果不存在则是该单词拼写错误。3.2 K-V模型KV模型每一个关键码key都有一个与之对应的value即key,value的键值对。比如英汉词典中的英文和汉语就是对应关系通过英文可以快速找到对应的中文wordchinese。再比如统计单词单词和单词出现的次数也是一对key-value模型wordcount。3.3 改造K模型为K-V模型删除不需要改变每个节点的结构需要改变插入也只需要新增一个参数value和new节点时的参 数find返回值改为找到的节点的地址遍历只需要多打印一个value。//1.K-V模型的二叉树的每个节点的结构 templateclass K,class V struct BSTreeNode { //构造函数 BSTreeNode(const K key K(),const V valueV()) :_key(key) ,_value(value) , _left(nullptr) , _right(nullptr) {} //成员变量 K _key; //key值 V _value; BSTreeNodeK,V* _left; //指向左孩子 BSTreeNodeK,V* _right; //指向右孩子 }; //模板参数K,V templateclass K,class V class BSTree { //对节点重命名 typedef BSTreeNodeK,V Node; public: //查找 Node* Find(const K key) { Node* cur _root; while (cur ! nullptr) { if (key cur-_key) { //继续去右子树查找 cur cur-_right; } else if (key cur-_key) { //继续去左子树查找 cur cur-_left; } else { //找到了返回当前节点 return cur; } } //没找到 return nullptr; } //插入 bool Insert(const K key,const V value) { //如果根为空直接插入新节点 if (_root nullptr) { _root new Node(key,value); return true; } Node* cur _root; //记录cur的父节点 Node* prev _root; while (cur ! nullptr) { prev cur; if (key cur-_key) { //继续去右子树 cur cur-_right; } else if (key cur-_key) { //继续去左子树 cur cur-_left; } else { //搜索二叉树不允许有重复值 return false; } } //插入 if (key prev-_key) { prev-_right new Node(key, value); } else { prev-_left new Node(key, value); } return true; } //删除 bool Erase(const K key) { Node* cur _root; //指向cur的父节点 Node* prev _root; while (cur cur-_key ! key) { prev cur; if (cur-_key key) { //去左子树 cur cur-_left; } else if (cur-_key key) { //去右子树 cur cur-_right; } } if (cur nullptr) { //没找到要删除的节点 return false; } //找到了要删除的节点 //开始删除 if (cur-_left cur-_right) { //左右孩子均存在 //1.找右子树的最左节点 Node* tmp cur-_right; Node* parent cur; while (tmp-_left ! nullptr) { parent tmp; tmp tmp-_left; } //交换最左节点和cur节点的值_key swap(cur-_key, tmp-_key); //如果parent没有动说明cur的第一个右孩子就是最左节点 if (parent cur) { cur-_right tmp-_right; } else { //如果parent动了那么tmp就必定是parent的左孩子 parent-_left tmp-_right; } delete tmp; } else if (cur-_right) { //只有右孩子 //1.特殊情况如果cur等于_root if (cur _root) { _root cur-_right; } else { //判断cur是父节点的左孩子还是右孩子 if (prev-_key cur-_key) { //是左孩子 prev-_left cur-_right; } else { //是右孩子 prev-_right cur-_right; } } delete cur; } else { //只有左孩子或没有孩子 if (cur _root) { _root cur-_left; } else { //判断cur是父节点的左孩子还是右孩子 if (prev-_key cur-_key) { //是左孩子 prev-_left cur-_left; } else { //是右孩子 prev-_right cur-_left; } } delete cur; } return true; } //中序遍历 void InOrder() { _InOrderR(_root); } void _InOrderR(Node* root) { if (root nullptr) { return; } _InOrderR(root-_left); cout root-_key root-_value ; _InOrderR(root-_right); } //... private: //成员变量 Node* _root nullptr; };四、二叉搜索树的性能分析插入和删除都需要先进行查找因此查找效率变成了代表二叉搜索树的各个操作的性能。二叉搜索树查找的时间复杂度O(N)1.当二叉搜索树接近一棵完全二叉树或满二叉树时查找效率为O(log(N))。 2.当二叉搜索树是以有序的顺序插入时查找效率为O(N)。在最坏情况下二叉搜索树退化为了一只单支树搜索性能就失去了时间复杂度是按照最坏的情况进行计算的因此二叉搜索树的时间复杂度为O(N)。
