有一个外国聊天网站 动画做的,网络推广网站,第1模板网,118论坛网址之家目录 一、二叉搜索树简介
二、二叉搜索树的结构与实现
2.1二叉树的查找与插入
2.2二叉树的删除
2.3二叉搜索树的实现
2.3.1非递归实现 2.3.2递归实现
三、二叉搜索树的k模型和kv模型 一、二叉搜索树简介 二叉搜索树又称二叉排序树#xff0c;它或者是一棵空树#xff0…目录 一、二叉搜索树简介
二、二叉搜索树的结构与实现
2.1二叉树的查找与插入
2.2二叉树的删除
2.3二叉搜索树的实现
2.3.1非递归实现 2.3.2递归实现
三、二叉搜索树的k模型和kv模型 一、二叉搜索树简介 二叉搜索树又称二叉排序树它或者是一棵空树或者是具有以下性质的二叉树:。 若它的左子树不为空则左子树上所有节点的值都小于根节点的值。 若它的右子树不为空则右子树上所有节点的值都大于根节点的值。 它的左右子树也分别为二叉搜索树。 二、二叉搜索树的结构与实现
2.1二叉树的查找与插入 int a [] { 8 , 3 , 1 , 10 , 6 , 4 , 7 , 14 , 13 }; 1. 二叉搜索树的查找 a、从根开始比较查找比根大则往右边走查找比根小则往左边走查找。 b、最多查找高度次走到到空还没找到这个值不存在。 2. 二叉搜索树的插入 插入的具体过程如下 a. 树为空则直接新增节点赋值给root指针 b. 树不空按二叉搜索树性质查找插入位置插入新节点 2.2二叉树的删除 首先查找元素是否在二叉搜索树中如果不存在则返回, 否则要删除的结点可能分下面四种情 况 a. 要删除的结点无孩子结点 b. 要删除的结点只有左孩子结点 c. 要删除的结点只有右孩子结点 d. 要删除的结点有左、右孩子结点 看起来有待删除节点有4中情况实际情况a可以与情况b或者c合并起来因此真正的删除过程 如下 情况b删除该结点且使被删除节点的双亲结点指向被删除节点的左孩子结点--直接删除 情况c删除该结点且使被删除节点的双亲结点指向被删除结点的右孩子结点--直接删除 情况d在它的右子树中寻找中序下的第一个结点(关键码最小)用它的值填补到被删除节点 中再来处理该结点的删除问题--替换法删除。 2.3二叉搜索树的实现
2.3.1非递归实现
//二叉树节点的构建
templateclass Kstruct BSTreeNode{typedef BSTreeNodeK Node;Node* _left;Node* _right;K _key;BSTreeNode(const K key):_left(nullptr), _right(nullptr), _key(key){}};//class BinarySearchTreetemplateclass Kclass BSTree{typedef BSTreeNodeK Node;public:// 强制生成默认构造BSTree() default;//拷贝构造BSTree(const BSTreeK t){_root Copy(t._root);}//赋值拷贝BSTreeK operator(BSTreeK t){swap(_root, t._root);return *this;}//析构函数~BSTree(){Destroy(_root);}/////增删查改//插入数据bool Insert(const K key){if (_root nullptr){_root new Node(key);return true;}Node* parent nullptr;Node* cur _root;while (cur){if (cur-_key key){parent cur;cur cur-_right;}else if (cur-_key key){parent cur;cur cur-_left;}else{return false;}}cur new Node(key);if (parent-_key key){parent-_right cur;}else{parent-_left cur;}return true;}//查找数据bool Find(const K key){Node* cur _root;while (cur){if (cur-_key key){cur cur-_right;}else if (cur-_key key){cur cur-_left;}else{return true;}}return false;}//删除数据bool Erase(const K key){Node* parent nullptr;Node* cur _root;while (cur){if (cur-_key key){parent cur;cur cur-_right;}else if (cur-_key key){parent cur;cur cur-_left;}else{if (cur-_left nullptr){if (cur _root){_root cur-_right;}else{if (cur parent-_right){parent-_right cur-_right;}else{parent-_left cur-_right;}}delete cur;return true;}else if (cur-_right nullptr){if (cur _root){_root cur-_left;}else{if (cur parent-_right){parent-_right cur-_left;}else{parent-_left cur-_left;}}delete cur;return true;}else{// 替换法Node* rightMinParent cur;Node* rightMin cur-_right;while (rightMin-_left){rightMinParent rightMin;rightMin rightMin-_left;}cur-_key rightMin-_key;if (rightMin rightMinParent-_left)rightMinParent-_left rightMin-_right;elserightMinParent-_right rightMin-_right;delete rightMin;return true;}}}return false;}privateNode* _root;}; 2.3.2递归实现
//二叉树节点的构建
templateclass Kstruct BSTreeNode{typedef BSTreeNodeK Node;Node* _left;Node* _right;K _key;BSTreeNode(const K key):_left(nullptr), _right(nullptr), _key(key){}};//class BinarySearchTreetemplateclass Kclass BSTree{typedef BSTreeNodeK Node;public:// 强制生成默认构造BSTree() default;//拷贝构造BSTree(const BSTreeK t){_root Copy(t._root);}//赋值拷贝BSTreeK operator(BSTreeK t){swap(_root, t._root);return *this;}//析构函数~BSTree(){Destroy(_root);}/////增删查改bool FindR(const K key){return _FindR(_root, key);}bool InsertR(const K key){return _InsertR(_root, key);}bool EraseR(const K key){return _EraseR(_root, key);}void InOrder(){_InOrder(_root);cout endl;}privatevoid Destroy(Node* root){if (root nullptr)return;Destroy(root-_left);Destroy(root-_right);delete root;}Node* Copy(Node* root){if (root nullptr)return nullptr;Node* newRoot new Node(root-_key);newRoot-_left Copy(root-_left);newRoot-_right Copy(root-_right);return newRoot;}//借助引用可以更好的删除和更改数据节点不需要再额外创建父节点来更改bool _EraseR(Node* root, const K key){if (root nullptr)return false;if (root-_key key){return _EraseR(root-_right, key);}else if (root-_key key){return _EraseR(root-_left, key);}else{Node* del root;if (root-_right nullptr){root root-_left;}else if (root-_left nullptr){root root-_right;}else{Node* rightMin root-_right;while (rightMin-_left){rightMin rightMin-_left;}swap(root-_key, rightMin-_key);return _EraseR(root-_right, key);}delete del;return true;}}bool _InsertR(Node* root, const K key){if (root nullptr){root new Node(key);return true;}if (root-_key key){return _InsertR(root-_right, key);}else if (root-_key key){return _InsertR(root-_left, key);}else{return false;}}bool _FindR(Node* root, const K key){if (root nullptr)return false;if (root-_key key){return _FindR(root-_right, key);}else if (root-_key key){return _FindR(root-_left, key);}else{return true;}}void _InOrder(Node* root){if (root nullptr)return;_InOrder(root-_left);cout root-_key ;_InOrder(root-_right);}Node* _root;};
三、二叉搜索树的k模型和kv模型 1. K模型K模型即只有key作为关键码结构中只需要存储Key即可关键码即为需要搜索到 的值。 比如给一个单词word判断该单词是否拼写正确具体方式如下 以词库中所有单词集合中的每个单词作为key构建一棵二叉搜索树 在二叉搜索树中检索该单词是否存在存在则拼写正确不存在则拼写错误。 例如小区停车场只要可以搜索到车牌号就可以自由进出。 2. KV模型每一个关键码key都有与之对应的值Value即Key, Value的键值对。该种方 式在现实生活中非常常见 比如英汉词典就是英文与中文的对应关系通过英文可以快速找到与其对应的中文英 文单词与其对应的中文word, chinese就构成一种键值对 再比如统计单词次数统计成功后给定单词就可快速找到其出现的次数单词与其出 现次数就是word, count就构成一种键值对。 例如商场停车场进去时记录车牌号出来时查询是否缴费如果缴费才可以出去。 改造搜素二叉树为kv结构 // 改造二叉搜索树为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;typedef Node* PNode;
public:BSTree(): _pRoot(nullptr){}PNode Find(const K key);bool Insert(const K key, const V value)bool Erase(const K key)
private:PNode _pRoot;};void TestBSTree()
{// 输入单词查找单词对应的中文翻译BSTreestring, string dict;dict.Insert(string, 字符串);dict.Insert(tree, 树);dict.Insert(left, 左边、剩余);dict.Insert(right, 右边);dict.Insert(sort, 排序);// 插入词库中所有单词string str;while (cinstr){BSTreeNodestring, string* ret dict.Find(str);if (ret nullptr){cout 单词拼写错误词库中没有这个单词: str endl;}else{cout str 中文翻译: ret-_value endl;}}
}
