二叉查找树(Binary Search Tree),也称有序二叉树(ordered binary tree),排序二叉树(sorted binary tree),是指一颗空树或者具有下列性质的二叉树:
创新互联专注于桑日网站建设服务及定制,我们拥有丰富的企业做网站经验。 热诚为您提供桑日营销型网站建设,桑日网站制作、桑日网页设计、桑日网站官网定制、微信小程序定制开发服务,打造桑日网络公司原创品牌,更为您提供桑日网站排名全网营销落地服务。
(1)每个节点都有一个作为搜索依据的关键码(key),所有的节点的关键码互不相同。
(2)左子树上所有的关键码(key)都小于根节点点的关键码(key)。
(3)右子树上所有的关键码(key)都大于根节点的关键码(key)。
(4)左右子树都是二叉搜索树。
代码实现如下:
#includeusing namespace std; template struct BSTreeNode{ BSTreeNode * _left; BSTreeNode * _right; K _key; V _value; BSTreeNode(const K& key,const V& value) :_key(key) , _value(value) , _left(NULL) , _right(NULL) {} }; template class BSTree{ typedef BSTreeNode Node; public: BSTree() :_root(NULL) {} //非递归 bool Insert(const K& key, const V& value) { if (_root == NULL) { _root = new Node(key,value); return true; } Node* parent = _root; 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; } } if (parent->_key>key) { parent->_left = new Node(key,value); } else { parent->_right = new Node(key, value); } return true; } void InOrder() { _InOrder(_root); cout << endl; } Node* Find(const K& key) { if (_root == NULL) { return NULL; } Node* cur = _root; while (cur) { if (cur->_key > key) { cur = cur->_left; } else if (cur->_key < key) { cur = cur->_right; } else { return cur; } } return NULL; } bool Remove(const K& key) { if (_root == NULL) { return false; } Node* parent = NULL; 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 break; } if (cur == NULL) return false; Node* del; //删除节点的左为空 if (cur->_left == NULL) { del = cur; if (parent == NULL) { _root = cur->_right; } else { if (parent->_left == cur) { parent->_left = cur->_right; } else { parent->_right = cur->_right; } } delete del; } //删除节点的右为空 else if (cur->_right == NULL) { del = cur; if (parent == NULL) { _root = cur->_left; } else { if (parent->_left == cur) { parent->_left = cur->_left; } else { parent->_right = cur->_left; } } delete del; } //删除节点的左右都不为空 else { //找右树的最左节点,也就是右边最小的数 parent = cur; Node* left = cur->_right; while (left->_left) { parent = left; left = left->_left; } del = left; cur->_key = left->_key; cur->_value = left->_value; if (parent->_left == left) { parent->_left = left->_right; } else { parent->_right = left->_right; } delete del; } return true; } //递归 Node* FindR(const K& key) { return _FindR(_root,key); } bool InsertR(const K& key, const V& value) { return _InsertR(_root,key,value); } bool RemoveR(const K& key) { return _RemoveR(_root,key); } protected: void _InOrder(Node* root) { if (root != NULL) { _InOrder(root->_left); cout << root->_key << " "; _InOrder(root->_right); } } Node* _FindR(Node* root,const K& key) { if (root == NULL) { return NULL; } if (root->_key == key) { return root; } if (root->_key > key) { return _FindR(root->_left,key); } else { return _FindR(root->_right,key); } return NULL; } bool _InsertR(Node*& root, const K& key, const V& value) { if (root == NULL) { root = new Node(key,value); return true; } if (root->_key > key) { return _InsertR(root->_left,key,value); } else { return _InsertR(root->_right,key,value); } return false; } bool _RemoveR(Node*& root, const K& key) { if (root == NULL) { return false; } if (root->_key > key) { return _RemoveR(root->_left,key); } else if (root->_key < key) { return _RemoveR(root->_right,key); } else { //删除的节点的左为空 if (root->_left == NULL) { root = root->_right; } //删除节点的右为空 else if (root->_right == NULL) { root = root->_left; } else { //找右边最左的节点(即右边最小的节点)替换删除的该节点(下面程序采用的)。 //或者找左边最右的节点(即左边最大的节点)替换删除的该节点 Node* parent = root; Node* left = root->_right; while (left->_left) { parent = left; left = left->_left; } root->_key = left->_key; root->_value = left->_value; if (parent->_left == left) { parent->_left = left->_right; } else { parent->_right = left->_right; } } return true; } return false; } protected: Node* _root; }; #include "BSTree.h" void Test1() { int arr[10] = { 0, 1, 3, 5, 4, 2, 7, 8, 6, 9}; BSTree bst; for (int i = 0; i < sizeof(arr) / sizeof(arr[0]); ++i) { bst.Insert(arr[i],i); } bst.InOrder(); BSTreeNode * ret1=bst.Find(8); if (ret1) { cout << ret1->_key << ":" << ret1->_value << endl; } else cout << "没有找到ret1" << endl; BSTreeNode * ret2=bst.Find(22); if (ret2) { cout << ret2->_key << ":" << ret2->_value << endl; } else cout << "没有找到ret2" << endl; bst.Remove(9); bst.Remove(7); bst.Remove(8); bst.InOrder(); bst.Remove(0); bst.Remove(1); bst.Remove(2); bst.Remove(3); bst.Remove(4); bst.Remove(5); bst.Remove(6); bst.Remove(7); bst.Remove(8); bst.Remove(9); bst.InOrder(); } void Test2() { int arr[10] = { 0, 1, 3, 5, 4, 2, 7, 8, 6, 9 }; BSTree bst; for (int i = 0; i < sizeof(arr) / sizeof(arr[0]); ++i) { bst.InsertR(arr[i], i); } bst.InOrder(); BSTreeNode * ret1 = bst.Find(7); if (ret1) { cout << ret1->_key << ":" << ret1->_value << endl; } else cout << "没有找到ret1" << endl; BSTreeNode * ret2 = bst.Find(12); if (ret2) { cout << ret2->_key << ":" << ret2->_value << endl; } else cout << "没有找到ret2" << endl; bst.RemoveR(8); bst.RemoveR(7); cout< 运行结果:
分享文章:搜索二叉树
地址分享:http://cdkjz.cn/article/gpocig.html