微信网站开发,顺德公司做网站,网站开发招聘年薪,安阳区号座机22开头哪的电话目录 1.二叉搜索树的概念
2.二叉搜索树的操作
二叉搜索树的插入
中序遍历(常用于排序)
二叉搜索树的查找
二叉搜索树的删除
完整二叉树代码#xff1a;
二叉搜索树的应用 key/value搜索模型整体代码 1.二叉搜索树的概念 二叉搜索树又称二叉排序树#xff0c;它或者是一…目录 1.二叉搜索树的概念
2.二叉搜索树的操作
二叉搜索树的插入
中序遍历(常用于排序)
二叉搜索树的查找
二叉搜索树的删除
完整二叉树代码
二叉搜索树的应用 key/value搜索模型整体代码 1.二叉搜索树的概念 二叉搜索树又称二叉排序树它或者是一棵空树 或者是具有以下性质的二叉树 : 若它的左子树不为空则左子树上所有节点的值都小于根节点的值 若它的右子树不为空则右子树上所有节点的值都大于根节点的值 它的左右子树也分别 为二叉搜索树 注搜索二叉树中没有重复值 二叉搜索树与其结点的代码实现 #includeiostream
using namespace std;templateclass K//搜索二叉树的结点
struct BSTreeNode
{K _key;BSTreeNodeK* _left;BSTreeNodeK* _right;BSTreeNode(const K s K()):_key(s), _left(nullptr), _right(nullptr){}
};templateclass K//搜索二叉树
class BSTree
{
public:BSTree():_root(nullptr){}//...各种操作二叉搜索树方法的实现//...
private:typedef BSTreeNodeK Node;Node* _root;
}; 2.二叉搜索树的操作 二叉搜索树的插入 这里根据二叉搜索树的概念分两种情况 a. 树为空则直接新增节点赋值给 root 指针 b. 树不空按二叉搜索树性质查找插入位置插入新节点 非递归 bool Insert(const K key){if (_root nullptr)//情况a{_root new Node(key);}else//情况b{Node* parent nullptr;//记录当前节点的父结点Node* cur _root;while (cur){if (cur-_key key)//小于当前节点的值向左走{parent cur;cur cur-_left;}else if (cur-_key key)//大于当前结点的值向右走{parent cur;cur cur-_right;}else //数字重复插入失败{return false;}}cur new Node(key);if (parent-_key key)//判断插入结点是在parent的左子树还是右子树{parent-_left cur;}else{parent-_right cur;}return true;}} 为什么要定义parent变量记录cur的父节点 这里我们要知道curnew Node(key)这行代码的真正意义是给cur赋值并没有把结点插入到树中。 注在向二叉搜索树插入时一定要判断是在父节点的左子树还是右子树。 递归 public:
bool InsertR(const K key)
{return _insertR(_root, key);
}private:
bool _insertR(Node* root, const K key)
{if (root nullptr){root new Node(key);return true;}else{if (root-_key key){return _insertR(root-_left, key);}else if (root-_key key){return _insertR(root-_right, key);}else{return false;}}
} 注由于使用递归时需要用到成员变量_root作为实参但是在类外面无法直接调用因此将递归调用的函数封装到了InsertR()里面。 为什么这里不用记录父节点就可以插入到树中。 这里我们要注意函数的第一个变量我们使用了引用 这里的root就是父节点的左孩子或有孩子。 那么在非递归里面可以使用引用来达到不设置parent变量来记录父节点吗 不能因为在C里引用只能指向一个。之后就不能改变指向。在递归中我们是在传参是使用的每次引用都重新开辟了一个新的变量而非递归中我们一直用的是一个变量。 中序遍历(常用于排序) public:
void Inorder()
{_Inorder(_root);
}private:
void _Inorder(Node* root)
{if (root nullptr)return;_Inorder(root-_left);cout root-_key ;_Inorder(root-_right);
} 这里根据二叉搜索树的概念我们清楚其中序遍历相当于将树里面的数据按从小到大排序输出。
二叉搜索树的查找
查找方法 a 、从根开始比较查找比根大则往右边走查找比根小则往左边走查找。 b 、最多查找高度次走到到空还没找到这个值不存在。 注意 为完全二叉树时间复杂度最好为O(log n) 树的结点全部为左孩子或右孩子时时间复杂度最坏为O(n) 非递归 bool Find(const K key)
{if (_root nullptr)//树为空return false;Node* cur _root;while (cur){if (cur-_key key){cur cur-left;// _keykey.左走}else if (cur-_key key){cur cur-_right;//_keykey.右走}else{return true;//相等找到}}return false;//没有一个相等
} 递归 public:
Node* FindR(const K key)
{return _FindR(_root, key);
}private:
Node* _FindR(Node* root, const K key)
{if (root nullptr)return nullptr;if (root-_key key){_FindR(root-_left, key);}else if (root-_key key){_FindR(root-_right, key);}else{return root;}
} 二叉搜索树的删除 首先查找元素是否在二叉搜索树中如果不存在则返回 , 否则要删除的结点可能分下面四种情 况 a. 要删除的结点无孩子结点 b. 要删除的结点只有左孩子结点 c. 要删除的结点只有右孩子结点 d. 要删除的结点有左、右孩子结点 看起来有待删除节点有 4 中情况实际情况 a 可以与情况 b 或者 c 合并起来因此真正的删除过程 如下 情况 b 删除该结点且使被删除节点的双亲结点指向被删除节点的左孩子结点 -- 直接删除 情况 c 删除该结点且使被删除节点的双亲结点指向被删除结点的右孩子结点 -- 直接删除 情况 d 在它的右子树中寻找中序下的第一个结点 ( 关键码最小 ) 用它的值填补到被删除节点 中再来处理该结点的删除问题 -- 替换法删除 bool Erase(const K key)
{if (_root nullptr)return false;Node* cur _root;Node* parent nullptr;while (cur){if (cur-_key key){parent cur;cur cur-_left;}else if (cur-_key key){parent nullptr;cur cur-_right;}else{if (cur-_left nullptr)//情况a{if (cur _root)//特殊条件等于根节点{_root cur-_right;}else{if (parent-_left cur){parent-_left cur-_right;}else{parent-_right cur-_right;}}delete cur;}else if (cur-right nullptr)//情况b{if (cur _root) //特殊条件等于根节点{_root cur-_left;}else{if (parent-_left cur){parent-_left cur-_left;}else{parent-_right cur-_left;}}delete cur;}else //情况c{Node* parent cur;Node* subnode cur-_right;while (subnode-_left){parent subnode;subnode subnode-_left;}swap(cur-_key, subnode-_key);if (parent-_right subnode) //当cur-_right-leftnullptr{parent-_right subnode-_right;}else{parent-_left subnode-_right;}delete subnode;}return true;}}return false;
} 递归 public:bool EraseR(const K key)
{_EraseR(_root,key);
}private: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{if (root-_left nullptr){Node* temp root;root root-_right;delete temp;}else if (root-right){Node* temp root;root root-_left;delete temp;}else{Node* subnode root-_right;while (subnode-left){subnode subnode-_left;}swap(root-_key, subnode-_key);return _EraseR(root - right, key);}}
} 完整二叉树代码 #includeiostream
using namespace std;templateclass K//搜索二叉树的结点
struct BSTreeNode
{K _key;BSTreeNodeK* _left;BSTreeNodeK* _right;BSTreeNode(const K s K()):_key(s), _left(nullptr), _right(nullptr){}
};templateclass K//搜索二叉树
class BSTree
{
public:BSTree():_root(nullptr){}bool Insert(const K key){if (_root nullptr)//情况a{_root new Node(key);}else//情况b{Node* parent nullptr;//记录当前节点的父结点Node* cur _root;while (cur){if (cur-_key key)//小于当前节点的值向左走{parent cur;cur cur-_left;}else if (cur-_key key)//大于当前结点的值向右走{parent cur;cur cur-_right;}else //数字重复插入失败{return false;}}cur new Node(key);if (parent-_key key)//判断插入结点是在parent的左子树还是右子树{parent-_left cur;}else{parent-_right cur;}return true;}}bool Find(const K key){if (_root nullptr)//树为空return false;Node* cur _root;while (cur){if (cur-_key key){cur cur-left;// _keykey.左走}else if (cur-_key key){cur cur-_right;//_keykey.右走}else{return true;//相等找到}}return false;//没有一个相等}Node* FindR(const K key){return _FindR(_root, key);}void Inorder(){_Inorder(_root);}bool InsertR(const K key){return _insertR(_root, key);cout endl;}bool Erase(const K key){if (_root nullptr)return false;Node* cur _root;Node* parent nullptr;while (cur){if (cur-_key key){parent cur;cur cur-_left;}else if(cur-_keykey){parent nullptr;cur cur-_right;}else{if (cur-_left nullptr){if (cur _root){_root cur-_right;}else{if (parent-_left cur){parent-_left cur-_right;}else{parent-_right cur-_right;}}delete cur;}else if(cur-rightnullptr){if (cur _root){_root cur-_left;}else{if (parent-_left cur){parent-_left cur-_left;}else{parent-_right cur-_left;}}delete cur;}else{Node* parent cur;Node* subnode cur-_right;while (subnode-_left){parent subnode;subnode subnode-_left;}swap(cur-_key, subnode-_key);if (parent-_right subnode){parent-_right subnode-_right;}else{parent-_left subnode-_right;}delete subnode;}return true;}}return false;}bool EraseR(const K key){return _EraseR(_root, key);}private:typedef BSTreeNodeK Node;Node* _root;bool _insertR(Node* root, const K key){if (root nullptr){root new Node(key);return true;}else{if (root-_key key){return _insertR(root-_left, key);}else if (root-_key key){return _insertR(root-_right, key);}else{return false;}}}void _Inorder(Node* root){if (root nullptr)return;_Inorder(root-_left);cout root-_key ;_Inorder(root-_right);}Node*_FindR(Node* root, const K key){if (root nullptr)return nullptr;if (root-_key key){_FindR(root-_left, key);}else if (root-_key key){_FindR(root-_right, key);}else{return root;}}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{if (root-_left nullptr){Node* temp root;root root-_right;delete temp;}else if (root-right){Node* temp root;root root-_left;delete temp;}else{Node* subnode root-_right;while (subnode-left){subnode subnode-_left;}swap(root-_key, subnode-_key);return _EraseR(root - right, key);}}}
}; 二叉搜索树的应用 1. K 模型 K 模型即只有 key 作为关键码结构中只需要存储 Key 即可关键码即为需要搜索到 的值 。 比如 给一个单词 word 判断该单词是否拼写正确 具体方式如下 以词库中所有单词集合中的每个单词作为 key 构建一棵二叉搜索树 在二叉搜索树中检索该单词是否存在存在则拼写正确不存在则拼写错误。 2. KV 模型每一个关键码 key 都有与之对应的值 Value 即 Key, Value 的键值对 。该方式在现实生活中非常常见 比如 英汉词典就是英文与中文的对应关系 通过英文可以快速找到与其对应的中文英 文单词与其对应的中文 word, chinese 就构成一种键值对 再比如 统计单词次数 统计成功后给定单词就可快速找到其出现的次数 单词与其出 现次数就是 word, count 就构成一种键值对 。 key/value搜索模型整体代码 #pragma once
// 改造二叉搜索树为KV结构
templateclass K, class V
struct BSTNode
{BSTNode(const K key K(), const V value V()): _pLeft(nullptr), _pRight(nullptr), _key(key), _Value(value){}BSTNodeT* _pLeft;BSTNodeT* _pRight;K _key;V _value
};templateclass K, class V
class BSTree
{typedef BSTNodeK, V Node;
public:bool Insert(const K key,const V value){if (_root nullptr)//情况a{_root new Node(key,value);}else//情况b{Node* parent nullptr;//记录当前节点的父结点Node* cur _root;while (cur){if (cur-_key key)//小于当前节点的值向左走{parent cur;cur cur-_left;}else if (cur-_key key)//大于当前结点的值向右走{parent cur;cur cur-_right;}else //数字重复插入失败{return false;}}cur new Node(key,value);if (parent-_key key)//判断插入结点是在parent的左子树还是右子树{parent-_left cur;}else{parent-_right cur;}return true;}}bool Find(const K key){if (_root nullptr)//树为空return false;Node* cur _root;while (cur){if (cur-_key key){cur cur-left;// _keykey.左走}else if (cur-_key key){cur cur-_right;//_keykey.右走}else{return true;//相等找到}}return false;//没有一个相等}bool Erase(const K key){if (_root nullptr)return false;Node* cur _root;Node* parent nullptr;while (cur){if (cur-_key key){parent cur;cur cur-_left;}else if (cur-_key key){parent nullptr;cur cur-_right;}else{if (cur-_left nullptr){if (cur _root){_root cur-_right;}else{if (parent-_left cur){parent-_left cur-_right;}else{parent-_right cur-_right;}}delete cur;}else if (cur-right nullptr){if (cur _root){_root cur-_left;}else{if (parent-_left cur){parent-_left cur-_left;}else{parent-_right cur-_left;}}delete cur;}else{Node* parent cur;Node* subnode cur-_right;while (subnode-_left){parent subnode;subnode subnode-_left;}swap(cur-_key, subnode-_key);if (parent-_right subnode){parent-_right subnode-_right;}else{parent-_left subnode-_right;}delete subnode;}return true;}}return false;}void Inorder(){_Inorder(_root);}private:Node* _root;void _Inorder(Node* root){if (root nullptr)return;_Inorder(root-_left);cout root-_key :root-_valueendl;_Inorder(root-_right);}
};
