口碑好的网站建设价格,书签制作步骤,传奇手游排行榜前一,wordpress 乱版【提醒】本章内容需掌握二叉树结构的基本概念和特性#xff0c;不然可能阅读起来比较费劲。
一、 概念 什么是搜索二叉树#xff1f;搜索二叉树和普通二叉树的却别是什么#xff1f; 答#xff1a; 二叉搜索树又称二叉排序树#xff0c;它或者是一棵空树 或者是具有以下性…【提醒】本章内容需掌握二叉树结构的基本概念和特性不然可能阅读起来比较费劲。
一、 概念 什么是搜索二叉树搜索二叉树和普通二叉树的却别是什么 答 二叉搜索树又称二叉排序树它或者是一棵空树 或者是具有以下性质的二叉树: 非空的左子树树上所有节点的值都小于根节点的值非空的右子树树上所有节点的值都大于根节点的值它的左右子树也分别为二叉搜索树 搜索二叉树 最重要的特性之一搜索二叉树 中序遍历可以得到一个有序的序列。
把文字转换成图形下面是一颗搜索二叉树 下面再来看两个例子更深刻地理解什么是搜索二叉树 二、搜索二叉树的增删查改
1. 搜索二叉树插入节点增 搜索二叉树的插入分为三个步骤 从根节点开始。 如果插入的值小于当前节点移动到左子节点如果大于移动到右子节点。 重复步骤2直到找到一个空位置插入新值。 以下用一个插入建树的详细图解说明
以数值{8 3 1 10 1}为例 【注意】二叉搜索树中如果插入的值已经存在处理方式可以有几种现阶段采用第一种 忽略重复值简单地不插入重复值保留原有节点。 计数重复值在每个节点中增加一个计数器如果插入相同值则增加计数器而不是新建节点。 允许重复值按某种规则插入如将相同值插入到右子树。 2. 搜索二叉树节点的删除 搜索二叉树阶段的删除相较于插入是要复杂一点的需要分情况讨论。 节点的删除: 首先查找元素是否在二叉搜索树中如果不存在则返回 false。 元素存在的情况则分以下四种情况分别处理假设要删除的结点为 N 要删除的结点 N 左右孩子均为空。 要删除的结点 N 左孩子为空右孩子结点不为空。 要删除的结点 N 右孩子为空左孩子结点不为空。 要删除的结点 N 左右孩子结点均不为空。 结合图形举例说明删除节点时会遇到的4种情况 为了解决以上4种情况分别对应4种解决方案
1.左右孩子均为空
把 N 结点的父节点对应孩子指针指向空直接删除 N 结点情况 1 可以当成 2 或者 3 处理效果是一样的。
2.左孩子为空右孩子不为空 把 N 结点的父节点对应孩子指针指向 N 的右孩子直接删除 N 结点。
3.右孩子为空左孩子不为空 把 N 结点的父节点对应孩子指针指向 N 的左孩子直接删除 N 结点。
4.左右孩子结点均不为空 无法直接删除 N 结点因为 N 的两个孩子无处安放只能用替换法删除。 找 N 左子树的值最大结点 R最右结点或者 N 右子树的值最小结点 R最左结点替代 N。 因为这两个结点中任意一个放到 N 的位置都满足二叉搜索树的规则。 替代 N 的意思就是 N 和 R 两个结点的值交换转而变成删除 R 结点R 结点符合情况 2 或情况 3可以直接删除。 同样结合图形可以更好的理解4总处理方式 3. 搜索二叉树节点的查找 搜索二叉树的查找逻辑很简单其实在上面插入节点已经使用过 查找步骤 从根节点开始。 比较值如果查找的值小于当前节点移动到左子节点如果大于移动到右子节点。 找到值重复步骤2直到找到值或访问到空节点。 4. 搜索二叉树节点的更改 搜索二叉树节点的修改如果直接修改可能会破坏BST的结构使树不再满足搜索树的性质。 所以在BST节点的修改应该遵循以下步骤 修改 删除原节点首先删除需要修改的节点。 插入新值然后插入修改后的新值。 三、搜索二叉树的模拟实现
下面是搜索二叉树的模拟实现出自鄙人如有错误愿联系指正【仅参考非源码】
// BST.h#include iostream
#include string
using namespace std;namespace key
{templateclass Kclass BSTreeNode {public:BSTreeNodeK* _leftNode;BSTreeNodeK* _rightNode;K _key;BSTreeNode(const K key):_key(key), _leftNode(nullptr), _rightNode(nullptr) {}};templateclass Kclass BinarySearchTree{typedef BSTreeNodeK Node;public:BinarySearchTree() :_root(nullptr){}~BinarySearchTree(){Destroy(_root);}BinarySearchTree(const BinarySearchTreeK tree) {_root Copy(tree._root);}BinarySearchTreeK operator(BinarySearchTreeK tree) {swap(_root, tree._root);return *this;}//节点插入bool Insert(const K key){if (_root nullptr) {_root new Node(key);return true;}Node* parent nullptr;Node* current _root;while (current){if (current-_key key) {parent current;current current-_rightNode;}else if (current-_key key) {parent current;current current-_leftNode;}else { //搜索二叉树不允许值相等return false;}}if (parent-_key key) {parent-_leftNode new Node(key);return true;}else if (parent-_key key) {parent-_rightNode new Node(key);return true;}return false;}//查找循环版Node* Find(const K key){Node* curr _root;while (curr) {if (curr-_key key) {curr curr-_rightNode;}else if (curr-_key key) {curr-_leftNode;}else {return curr;}}return nullptr;}bool Erase(const K key) {Node* parent nullptr;Node* curr _root;while (curr) {if (curr-_key key){parent curr;curr curr-_rightNode;}else if (curr-_key key){parent curr;curr curr-_leftNode;}else {//等于情况下就删除 找到了if (curr-_leftNode nullptr) {if (curr _root) {//如果根就是要删除的节点_root curr-_rightNode;}else {//判断现在找到的节点 是父的左还是右if (parent-_leftNode curr) {parent-_leftNode curr-_rightNode;}else {parent-_rightNode curr-_rightNode;}}}else if (curr-_rightNode nullptr) {if (curr _root) {//如果根就是要删除的节点_root curr-_leftNode;}else {//判断现在找到的节点 是父的左还是右if (parent-_leftNode curr) {parent-_leftNode curr-_leftNode;}else {parent-_rightNode curr-_leftNode;}}}else { //两边都有Node* leftNodeParent curr;Node* leftMaxNode curr-_leftNode;//找左边树最大的节点代替while (leftMaxNode-_rightNode) {leftNodeParent leftMaxNode;leftMaxNode leftMaxNode-_rightNode;}// 交换要删除节点和左子树最大节点的键值curr-_key leftMaxNode-_key;// 更新父节点指针删除左子树的最大节点if (leftNodeParent-_leftNode leftMaxNode) {leftNodeParent-_leftNode leftMaxNode-_leftNode;}else {leftNodeParent-_rightNode leftMaxNode-_leftNode;}curr leftMaxNode;}delete curr;return true;}}return false;}//查找递归版bool FindR(const K key){_FindR(_root, key);}//插入节点递归版bool InsertR(const K key) {return _InsertR(_root, key); }//删除节点递归版bool EraseR(const K key) {return _EraseR(_root, key);}//中序遍历打印void InOrder() {_InOrder(_root);}private://递归寻找子函数bool _FindR(Node* root, const K key) {if (root nullptr)return false;if (root-_key key) {return _FindR(root-_leftNode, key);}else if (root-_key key) {return _FindR(root-_rightNode, key);}else {return true;}}//递归删除子函数bool _EraseR(Node* root, const K key){if (root nullptr)return false;if (root-_key key) {return _EraseR(root-_leftNode, key);}else if (root-_key key) {return _EraseR(root-_rightNode, key);}else {//找到了删除Node* deleteNode root;if (root-_leftNode nullptr) {root root-_rightNode;}else if (root-_rightNode nullptr) {root root-_leftNode;}else {//左右都有Node* leftMax root-_leftNode;while (leftMax-_rightNode) {leftMax leftMax-_rightNode;}swap(root-_key, leftMax-_key);return _EraseR(root-_leftNode, key);}delete deleteNode;return true;}}//递归插入子函数bool _InsertR(Node* root, const K key){if (root nullptr) {root new Node(key);return true;}if (root-_key key) {return _InsertR(root-_leftNode, key);}else if (root-_key key) {return _InsertR(root-_rightNode, key);}else {return false; //相同的返回false}}//中序遍历打印子函数void _InOrder(Node* root){if (root nullptr)return;_InOrder(root-_leftNode);cout root-_key ;_InOrder(root-_rightNode);}void Destroy(Node* root){if (root nullptr)return;Destroy(root-_leftNode);Destroy(root-_rightNode);delete root;root nullptr;}Node* Copy(const Node* root){if (root nullptr)return nullptr;Node* copyRoot new Node(root-_key);copyRoot-_leftNode Copy(root-_leftNode);copyRoot-_rightNode Copy(root-_rightNode);return copyRoot;}Node* _root nullptr;};void TestBSTree1();
}
//main.h
#include binarysearchtree.h
#include iostreamnamespace key {void TestBSTree1(){int a[] { 8, 3, 1, 10, 6, 4, 7, 14, 13 };BinarySearchTreeint t;for (auto e : a){t.InsertR(e);}t.InOrder();cout endl;t.Erase(4);t.InOrder();cout endl;t.EraseR(6);t.InOrder();cout endl;t.EraseR(7);t.InOrder();cout endl;t.EraseR(3);t.InOrder();cout endl;for (auto e : a){t.EraseR(e);}t.InOrder();}
}int main()
{key::TestBSTree1();return 0;
}
程序运行结果
1 3 4 6 7 8 10 13 14
1 3 6 7 8 10 13 14
1 3 7 8 10 13 14
1 3 8 10 13 14
1 8 10 13 14
