C++中如何实现搜索二叉树
本篇内容介绍了“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++中如何实现搜索二叉树”的内容就介绍到这里了,感谢大家的阅读。如果想了解更多行业相关的知识可以关注创新互联网站,小编将为大家输出更多高质量的实用文章!
网站题目:C++中如何实现搜索二叉树
当前链接:http://scyanting.com/article/gsghpc.html