【数据结构】二叉搜索树-创新互联
● 二叉搜索树满足以下条件的二叉树:
1、每个节点都有一个作为搜索依据的关键码(key),所有节点的关键码互不相同。
2、左子树上所有节点的关键码(key)都小于根节点的关键码(key)。
3、右子树上所有节点的关键码(key)都大于根节点的关键码(key)。
4、左右子树都是二叉搜索树。
● 二叉搜索树的插入过程如下:
1、若当前的二叉搜索树为空,则插入的元素为根节点。
2、若插入的元素值小于根节点值,则将元素插入到左子树中。
3、若插入的元素值大于根节点值,则将元素插入到右子树中。
4、找到插入的位置和插入的位置的父结点,进行链接。
templatevoid BSTree ::Insert(const T& key, const T& value)//非递归算法进行插入 { if (_root == NULL) { _root = new Node(key, value); return; } Node* prev = NULL; Node* cur = _root; while (cur)//在树中找到插入的位置 { if (key < cur->_key) { prev = cur; cur = cur->_left; } else if (key > cur->_key) { prev = cur; cur = cur->_right; } } cur = new Node(key, value);//建立新结点,并判断具体位置进行链接 if (prev->_key > cur->_key) { prev->_left = cur; } if (prev->_key < cur->_key) { prev->_right = cur; } } template void BSTree ::Insert_R(const T& key, const T& value)//递归算法进行插入 { _insert_r(_root, key, value); } template void BSTree ::_insert_r(Node*& root, const T& key, const T& value)//递归 { if (root == NULL)//root为空时,开辟新结点 { root = new Node(key, value); return; } Node* cur = root; if (key < cur->_key) _insert_r(cur->_left, key, value); if (key > cur->_key) _insert_r(cur->_right, key, value); }
● 二叉搜索树的查找过程如下:
1、若当前的二叉搜索树为空,则结束函数。
2、若查找的元素值小于根节点值,则在当前结点的左子树中查找。
3、若查找的元素值大于根节点值,则在当前结点的右子树中查找。
templateBSTNode * BSTree ::Find(const T& key)//非递归算法进行查找 { Node* cur = _root; while (cur) { if (key < cur->_key) { cur = cur->_left; } else if (key > cur->_key) { cur = cur->_right; } else { return cur; } } return NULL; } template BSTNode * BSTree ::Find_R(const T& key)//递归 { return _find_r(_root, key); } template BSTNode * BSTree ::_find_r(Node*& root, const T& key)//递归算法进行查找 { if (root == NULL)//root为空时为没找到 { return NULL; } if (key < root->_key) return _find_r(root->_left, key); else if (key > root->_key) return _find_r(root->_right, key); else return root; }
● 二叉搜索树的删除,分两种情况进行处理:
1、找到要删除的结点cur和cur的父亲结点prev。
2、情况一:cur只有一个子树或没有子树。首先考虑删除的结点为根结点时,直接_root指向它的子树;
再考虑cur的左为空、右为空还是左右都为空,进行删除,链接。
3、情况二:cur左右子树都不为空。首先找到cur右子树的最左下结点del,然后进行交换,通过替换法删除del,并使prev的指向置空。
templatevoid BSTree ::Remove(const T& key)//非递归算法进行删除 { if (_root == NULL) { return; } Node* prev = NULL; Node* cur = _root; while (cur)//找到要删除的结点cur { if (key < cur->_key) { prev = cur; cur = cur->_left; } else if (key > cur->_key) { prev = cur; cur = cur->_right; } else break; } //情况一:cur只有一个孩子或没有孩子,注意考虑cur为根结点时,prev=NULL if (cur->_left == NULL || cur->_right == NULL) { if (cur->_left == NULL)//cur只有右孩子 { if (prev == NULL)//cur为根结点时 _root = cur->_right; else if (prev->_left == cur) prev->_left = cur->_right; else prev->_right = cur->_right; } else if (cur->_right == NULL)//cur只有左孩子 { if (prev == NULL)//cur为根结点时 _root = cur->_left; else if (prev->_left == cur) prev->_left = cur->_left; else prev->_right = cur->_left; } //删除cur并置空,包含了cur的左右为空的情况 delete cur; cur = NULL; } //情况二:cur有左右子树,替换法删除 else { //先找到cur结点右子树的最左下结点del Node* del = cur; prev = del; del = del->_right; while (del->_left) { prev = del; del = del->_left; } //替换法,删除结点del,注意使prev的指向置空 swap(cur->_key, del->_key); swap(cur->_value, del->_value); if (prev->_left == del) prev->_left = NULL; else if (prev->_right == del) prev->_right = NULL; delete del; del = NULL; } } template void BSTree ::Remove_R(const T& key)//递归算法进行删除 { _remove_r(_root, key); } template void BSTree ::_remove_r(Node*& root, const T& key)//递归 { if (_root == NULL) { return; } if (key < root->_key) _remove_r(root->_left, key); else if (key > root->_key) _remove_r(root->_right, key); else { //情况一:只有一个子树或没有,直接使root重新赋值 if (root->_left == NULL || root->_right == NULL) { Node* del = root; if (root->_left == NULL) root = root->_right; else if (root->_right == NULL) root = root->_left; else root = NULL; delete del; del = NULL; } else//情况二:左右子树都不为空 { Node* cur = root->_right;//root右子树最左下结点,交换两个结点的值 while (cur->_left) { cur = cur->_left; } swap(root->_key, cur->_key); swap(root->_value, cur->_value); _remove_r(root->_right, key);//在root的右子树上删除key,转换成情况一中左子树一定为空 } } }
创新互联www.cdcxhl.cn,专业提供香港、美国云服务器,动态BGP最优骨干路由自动选择,持续稳定高效的网络助力业务部署。公司持有工信部办法的idc、isp许可证, 机房独有T级流量清洗系统配攻击溯源,准确进行流量调度,确保服务器高可用性。佳节活动现已开启,新人活动云服务器买多久送多久。
当前标题:【数据结构】二叉搜索树-创新互联
分享网址:http://pwwzsj.com/article/gsgep.html