重庆分公司,新征程启航
为企业提供网站建设、域名注册、服务器等服务
这篇文章将为大家详细讲解有关C++中怎么实现搜索二叉树,文章内容质量较高,因此小编分享给大家做个参考,希望大家阅读完这篇文章后对相关知识有一定的了解。
成都创新互联公司从2013年创立,是专业互联网技术服务公司,拥有项目网站制作、成都网站建设网站策划,项目实施与项目整合能力。我们以让每一个梦想脱颖而出为使命,1280元内丘做网站,已为上家服务,为内丘各地企业和个人服务,联系电话:18982081108二叉查找树(英语:Binary Search Tree),也称二叉搜索树、有序二叉树(英语:ordered binary tree),排序二叉树(英语:sorted binary tree),是指一棵空树或者具有下列性质的二叉树:
任意节点的左子树不空,则左子树上所有结点的值均小于它的根结点的值;
任意节点的右子树不空,则右子树上所有结点的值均大于它的根结点的值;
任意节点的左、右子树也分别为二叉查找树;
没有键值相等的节点。
#pragma once templatestruct BSTreeNode { K _key; V _value; BSTreeNode * _left; BSTreeNode * _right; 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 (NULL == _root)//若为空树 { _root = new Node(key, value); return true; } Node* parent = NULL; Node* cur = _root; //确定插入节点的位置 while (cur) { if (key < cur->_key) { parent = cur; cur = cur->_left; } else if (key > cur->_key) { parent = cur; cur = cur->_right; } else//已经存在key { return false; } } //插入节点 if (key > parent->_key) parent->_right = new Node(key, value); else parent->_left = new Node(key, value); } //Insert递归写法 bool InsertR(const K& key, const V& value) { return _InsertR(_root, key, value); } bool _InsertR(Node*& root, const K& key, const V& value) { if (NULL == root) { root = new Node(key, value); return true; } if (key > root->_key) return _InsertR(root->_right, key, value); else if (key < root->_key) return _InsertR(root->_left, key, value); else return false; } Node* Find(const K& key) { Node* cur = _root; while (cur) { if (key > cur->_key) cur = cur->_right; else if (key < cur->_key) cur = cur->_left; else return cur; } return NULL; } //Find递归写法 Node* FindR(const K& key) { return _FindR(_root, key); } Node* _FindR(Node* root, const K& key) { if (NULL == root) return NULL; if (key > root->_key) return _FindR(root->_right, key); else if (key < root->_key) return _FindR(root->_left, key); else return root; } bool Remove(const K& key) { Node* parent = NULL; Node* cur = _root; //确定删除节点的位置 while (cur) { if (key > cur->_key) { parent = cur; cur = cur->_right; } else if (key < cur->_key) { parent = cur; cur = cur->_left; } else { break; } } if (NULL == cur)//没有该节点 { return false; } Node* del; if (NULL == cur->_left)//删除节点的左孩子为空 { del = cur; //删除的节点为根节点 if (NULL == parent) { _root = _root->_right; } else { if (cur == parent->_left) parent->_left = cur->_right; else parent->_right = cur->_right; } } else if (NULL == cur->_right)//删除节点的右孩子为空 { del = cur; if (NULL == parent) { _root = _root->_left; } else { if (cur == parent->_left) parent->_left = cur->_right; else parent->_right = cur->_left; } } else//删除节点的左右孩子都不为空,找右子树最左节点代替该节点删除 { parent = cur; Node* leftmost = cur->_right; while (leftmost->_left) { parent = leftmost; leftmost = leftmost->_left; } del = leftmost; cur->_key = leftmost->_key; cur->_value = leftmost->_value; if (leftmost == parent->_left) parent->_left = leftmost->_right; else parent->_right = leftmost->_right; } return true; } //Remove递归写法 bool RemoveR(const K& key) { return _RemoveR(_root, key); } bool _RemoveR(Node*& root, const K& key) { if (NULL == root) return false; if (key > root->_key) { return _RemoveR(root->_right, key); } else if (key < root->_key) { return _RemoveR(root->_left, key); } else { Node* del = root; if (NULL == root->_left) { root = root->_right; } else if (NULL == root->_right) { root = root->_left; } else { Node* leftmost = root->_right; while (leftmost->_left) { leftmost = leftmost->_left; } swap(root->_key, leftmost->_key); swap(root->_value, leftmost->_value); return _RemoveR(root->_right, key); } delete del; } return true; } //中序遍历递归写法 void InOrder() { _InOrder(_root); } void _InOrder(Node* root) { if (NULL == root) return; _InOrder(root->_left); cout< _key<<" "; _InOrder(root->_right); } protected: Node* _root; }; void Test() { BSTree t; int a[] = {5, 3, 4, 1, 7, 8, 2, 6, 0, 9}; for (size_t i = 0; i < sizeof(a)/sizeof(a[0]);++i) { t.InsertR(a[i], i); } cout< _key< _key< _key< 关于C++中怎么实现搜索二叉树就分享到这里了,希望以上内容可以对大家有一定的帮助,可以学到更多知识。如果觉得文章不错,可以把它分享出去让更多的人看到。
另外有需要云服务器可以了解下创新互联scvps.cn,海内外云服务器15元起步,三天无理由+7*72小时售后在线,公司持有idc许可证,提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案,具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势,专为企业上云打造定制,能够满足用户丰富、多元化的应用场景需求。
网站标题:C++中怎么实现搜索二叉树-创新互联
URL网址:http://cqcxhl.com/article/hesoi.html