C++搜索二叉树
卖寂寞的小男孩 人气:0零.前言
了解搜索二叉树是为了STL中的map和set做铺垫,我们所熟知的AVL树和平衡搜索二叉树也需要搜索二叉树的基础,本文就来建立一棵搜索二叉树。
1.概念
搜索二叉树又称为二叉排序树,它或者是一棵空树,或者具有如下性质:
1.若其左子树不为空,则左子树上所有节点的值都小于根节点的值。
2.若其右子树不为空,则右子树上所有节点的值都大于根节点的值。
3.它的左右子树也分别为二叉搜索树。
2.作用
1.搜索:通过搜索二叉树的性质来进行搜索。
2.排序:二叉搜索树的中序遍历就是将所有数据进行排序。
3.迭代实现
(1)查找
对二叉搜索树的节点进行查找:
1.定义查找节点指针cur
2.比较cur->_k与要查找的节点k的值的大小关系,当_k<k的时候,cur指向该节点的右子树,否则指向左子树。
3.查找成功返回true,失败返回false
bool Find(const K& k) { Node* cur = _root;//1. while (cur)//2. { if (cur->_k < k) { cur = cur->_right; } else if (cur->_k > k) { cur = cur->_left; } else { return true;//3 } } return false;//3 }
(2)插入
1.判断根节点指针是否为空。如果为空则直接将该节点插入根节点位置。
2.定义遍历节点cur与其父节点parent。
3.依次判断插入节点的k与当前节点cur的大小决定cur指向当前节点的左或者右节点。并在改变cur指向之前将parent赋值为cur。
如果二叉搜索树中已经有该值,则返回false。
4.当cur为空的时候,建立根据k在cur处建立节点。比较parent的_k与k的大小,判断cur建立在parent的左子树还是右子树。并返回true。
bool InsertNode(const K& k) { if (_root == nullptr) { _root = new Node(k); return true; }//1 Node* cur = _root; Node* parent = nullptr;//2 while (cur) { if (cur->_k < k) { parent = cur; cur = cur->_right; } else if (cur->_k > k) { parent = cur; cur = cur->_left; } else { return false; } }//3 cur = new Node(k); if (parent->_k < k) { parent->_right = cur; } else { parent->_left = cur; } return true;//4 }
(3)删除
1.首先通过cur和parent查找该节点。
2.如果cur左为空,判断cur相对于parent的位置,并将cur的右子树赋值到cur相对于parent的位置处。并删除cur。
3.如果cur右为空,判断cur相对于parent的位置,并将cur的左子树赋值到cur相对于parent的位置处。并删除cur。
4.如果cur的左右都不为空:
(1)建立一个新的节点指针min赋值为cur->right作为遍历指针,和其父节点指针minparent赋值为cur。
(2)一直向左遍历直到min->left为空。并交换min与cur的_key。
(3)判断min与minparent的位置关系,并将min的右子树放在该处。
(4)删除min,返回true。若没找到返回false。
bool Erase(const K& k) { Node* cur = _root; Node* parent = nullptr; while (cur) { if (cur->_k < k) { parent = cur; cur = cur->_right; } else if (cur->_k > k) { parent = cur; cur = cur->_left; }//1 else { if (cur->_left == nullptr) { if (parent == nullptr) { _root = cur->_right; } else if (parent->_right == cur) { parent->_right = cur->_right; } else { parent->_left = cur->_right; } delete cur; return true; } else if (cur->_right == nullptr) { if (parent == nullptr) { _root = cur->_left; } else if (parent->_left == cur) { parent->_left = cur->_left; } else { parent->_right = cur->_left; } delete cur; return true; }//2 else { Node* min = cur->_right; Node* minparent = cur;//4.(1) while(min->_left) { minparent = min; min = min->_left; }//4.(2) cur->_k = min->_k; if (minparent->_left == min) { minparent->_left = min->_right; } else { minparent->_right = min->_right; }//4.(3) delete min; return true; } } } return false;//4.(4) }
4.递归实现
(1)查找
1.判空
2.判断root->_k与k的大小,判断递归的方向。
3.如果找到了返回root节点。
Node* _FindR(const K& k) { return FindR(_root, k); }//1 Node* FindR(Node* root, const K& k) { if (root == nullptr) { return nullptr; } if (root->_k > k) { return FindR(root->_left, k); } else if (root->_k < k) { return FindR(root->_right, k); }//2 else { return root; }//3 }
(2)插入
1.判断节点是否为空,如果为空将该节点插入节点的位置。并返回true
2.判断_k和k的大小,判断递归的方向。
3.如果节点值等于k返回false。
bool InsertR(const K& k) { return _InsertR(_root, k); } bool _InsertR(Node*& root, const K& k) { if (root == nullptr) { root = new Node(k); return true; }//1 if (root->_k < k) { return _InsertR(root->_right, k); } else if (root->_k > k) { return _InsertR(root->_left, k); }//2 else { return false; }//3 }
(3)删除
1.如果节点为空则返回false
2.通过_k和k的大小来判断递归方向。
3.找到该节点:
(1)定义del指针赋值为root。
(2)如果root左子树为空,则将root指向该节点的右子树。
(3)如果root右子树为空,则将root指向该节点的左子树。
(4)如果root左右子树都不为空,将min赋值为root->right,并依次向左找,直到min->left为空。并交换min的k与root的k。 然后递归到右子树来进行删除。
(5)删除原root节点(del),并返回true。
bool EraseR(const K& k) { return _EraseR(_root, k); } bool _EraseR(Node*& root, const K& k) { if (root == nullptr) return false;//1 if (root->_k < k) { return _EraseR(root->_right, k); } else if (root->_k > k) { return _EraseR(root->_left, k); }//2 else { Node* del = root;//3.(1) if (root->_left == nullptr) { root = root->_right; }//3.(2) else if (root->_right == nullptr) { root = root->_left; }//3.(3) else { Node* min = root->_right; while (min->_left) { min = min->_left; } swap(min->_k, root->_k); // 递归到右子树去删除 return _EraseR(root->_right, k);//3.(4) } delete del; return true;//3.(5) } }
5.key/value模型的应用
key/value模型,即在原来k的基础上,每个节点再带有一个value值。有两种主要的应用:
(1)对应查找
利用到了二叉搜索树搜素的性质。
BSTree<string, string> word; word.InsertNode("man", "男人"); word.InsertNode("woman", "女人"); word.InsertNode("sort", "排序"); word.InsertNode("Earth", "地球"); word.InsertNode("birth", "出生"); word.InsertNode("die", "死亡"); string str; while (cin >> str) { BSTreeNode<string, string>* ret = word.Find(str); if (ret) { cout << "对应的中文解释:" << ret->_v << endl; } else { cout << "无此单词" << endl; } }
我们向二叉搜索树中存入英文单词和中文释义,将英文单词作为k来构建二叉搜索树,如果搜索到了则打印中文释义,这样就简单构成了一个字典。
(2)判断出现次数
当我们判断一个数组中各个元素出现的次数的时候,也可以使用到二叉搜索树。
string arr[] = { "a","b","e","e","b","a","n","a","n","a","c","p","d","d","x","s","w","l" }; BSTree<string, int> counttree; for (auto& str : arr) { auto ret = counttree.Find(str); if (ret != nullptr) { (ret->_v)++; } else { counttree.InsertNode(str, 1); } } counttree._InOrderv();
每一次出现一个元素我们就将它插入二叉搜索树中,并把它的value赋值为1,当第二次遇到这个元素的时候,在二叉搜索树中搜索该元素,人如果可以找到该元素则将该元素的value的值++。最终统计出各个元素出现的次数。
6.总结
对于二叉搜索树的理解对以后学习AVL树和红黑树具有很大的帮助
加载全部内容