有关建筑的网站,重庆网站建设接重庆零臻科技,徐州网站设计,备案网站名称怎么改目录 1、二叉搜索树概念
2、 二叉搜索树的插入
3、二叉搜索树的查找
4、二叉搜索树的删除
5、二叉搜索树的中序遍历
实现 1、二叉搜索树概念 二叉搜索树又称二叉排序树#xff0c;它或者是一棵空树 #xff0c;或者是具有以下性质的二叉树 : 若它的左子树不为空#…目录 1、二叉搜索树概念
2、 二叉搜索树的插入
3、二叉搜索树的查找
4、二叉搜索树的删除
5、二叉搜索树的中序遍历
实现 1、二叉搜索树概念 二叉搜索树又称二叉排序树它或者是一棵空树 或者是具有以下性质的二叉树 : 若它的左子树不为空则左子树上所有节点的值都小于根节点的值 若它的右子树不为空则右子树上所有节点的值都大于根节点的值 它的左右子树也分别为二叉搜索树 定义一个二叉搜索树类
templateclass K
struct BSTreeNode
{BSTreeNodeK* _left;BSTreeNodeK* _right;K _key;BSTreeNode(const K key):_left(nullptr), _right(nullptr), _key(key){}
};templateclass K
class BSTree
{typedef BSTreeNodeK Node;
private:Node* _root nullptr;
public:bool Insert(const K key); //插入bool Find(const K key); //查找bool Erase(const K key); //删除void InOrder(); //中序遍历void _InOrder(Node* root);};
2、 二叉搜索树的插入 树为空则直接新增节点赋值给root指针 树不空按二叉搜索树性质查找插入位置插入新节点 templateclass K
bool BSTreeK::Insert(const K key)
{if (_root nullptr){_root new Node(key);return true;}Node* parent nullptr;Node* cur _root;while (cur ! nullptr){parent cur;if (cur-_key key){cur cur-_right;}else if (cur-_key key){cur cur-_left;}else{return false; //cur-_key key}}cur new Node(key);if (parent-_key key){parent-_right cur;}else{parent-_left cur;}return true;
}
3、二叉搜索树的查找
从根开始比较查找比根大则往右边走查找比根小则往左边走查找。 最多查找高度次走到到空还没找到这个值不存在。
templateclass K
bool BSTreeK::Find(const K key)
{Node* cur _root;while (cur ! nullptr){if (key cur-_key) //key小于cur-_key,cur向左走{cur cur-_left;}else if (key cur-_key) //key大于于cur-_key,cur向右走{cur cur-_right;}else //key等于于cur-_key返回true{return true;}}return false; //不存在返回false} 4、二叉搜索树的删除 首先查找元素是否在二叉搜索树中如果不存在则返回 , 否则要删除的结点可能分下面四种情 况 要删除的结点无孩子结点 要删除的结点只有左孩子结点 要删除的结点只有右孩子结点 要删除的结点有左、右孩子结点 看起来有待删除节点有 4 中情况实际情况 a 可以与情况 b 或者 c 合并起来因此真正的删除过程 如下 删除该结点且使被删除节点的双亲结点指向被删除节点的左孩子结点--直接删除 删除该结点且使被删除节点的双亲结点指向被删除结点的右孩子结点--直接删除 在它的右子树中寻找中序下的第一个结点(关键码最小)用它的值填补到被删除节点中再来处理该结点的删除问题--替换法删除 替换法删除我们可以使用被删的节点的左子树的最大节点或者右子树的最小节点来替代被删的节点的值
templateclass K
bool BSTreeK::Erase(const K key)
{Node* parent nullptr;Node* cur _root;while (cur ! nullptr){if (cur-_key key){parent cur;cur cur-_right;}else if (cur-_key key){parent cur;cur cur-_left;}else //找到要删除的数{// 准备删除//分为三种情况//1、左为空//2、右为空//3、左右都不为空 if (cur-_left nullptr) //左为空{if (cur _root) //1、要删除的点为根节点{_root cur-_right;}else{if (cur parent-_left){parent-_left cur-_right;}else{parent-_right cur-_right;}}}else if (cur-_right nullptr) //右为空{if (cur _root) //1、要删除的点为根节点{_root cur-_left;}else{if (cur parent-_left){parent-_left cur-_left;}else{parent-_right cur-_left;}}}else //左右都不为空{//我们可以使用被删的节点的左子树的最大节点或者右子树的最小节点//来替代被删的节点的值Node* parent cur;Node* subLeft cur-_right;while (subLeft-_left){parent subLeft;subLeft subLeft-_left; // 右子树的最小节点(最左节点)}swap(cur-_key, subLeft-_key); //右子树的最小节点与被删节点的值交换if (subLeft parent-_left){parent-_left subLeft-_right;}else{parent-_right subLeft-_right;}}return true;}}return false; //没有找到要删除的数
}5、二叉搜索树的中序遍历
根据二叉搜索树的特性我们可以推出二叉搜索树的中序遍历是一个有序的数据
我们可以采用递归的方法去遍历
templateclass K
void BSTreeK::InOrder()
{_InOrder(_root);cout endl;
}
templateclass K
void BSTreeK::_InOrder(Node* root)
{if (root nullptr)return;_InOrder(root-_left);cout root-_key ;_InOrder(root-_right);
}
实现
templateclass K
struct BSTreeNode
{BSTreeNodeK* _left;BSTreeNodeK* _right;K _key;BSTreeNode(const K key):_left(nullptr), _right(nullptr), _key(key){}
};templateclass K
class BSTree
{typedef BSTreeNodeK Node;
private:Node* _root nullptr;
public:bool Insert(const K key); //插入bool Find(const K key); //查找bool Erase(const K key); //删除void InOrder(); //中序遍历void _InOrder(Node* root);};templateclass K
bool BSTreeK::Insert(const K key)
{if (_root nullptr){_root new Node(key);return true;}Node* parent nullptr;Node* cur _root;while (cur ! nullptr){parent cur;if (cur-_key key){cur cur-_right;}else if (cur-_key key){cur cur-_left;}else{return false; //cur-_key key}}cur new Node(key);if (parent-_key key){parent-_right cur;}else{parent-_left cur;}return true;
}templateclass K
bool BSTreeK::Find(const K key)
{Node* cur _root;while (cur ! nullptr){if (key cur-_key) //key小于cur-_key,cur向左走{cur cur-_left;}else if (key cur-_key) //key大于于cur-_key,cur向右走{cur cur-_right;}else //key等于于cur-_key返回true{return true;}}return false; //不存在返回false}templateclass K
bool BSTreeK::Erase(const K key)
{Node* parent nullptr;Node* cur _root;while (cur ! nullptr){if (cur-_key key){parent cur;cur cur-_right;}else if (cur-_key key){parent cur;cur cur-_left;}else{// 准备删除 if (cur-_left nullptr) //左为空{if (cur _root){_root cur-_right;}else{if (cur parent-_left){parent-_left cur-_right;}else{parent-_right cur-_right;}}}else if (cur-_right nullptr) //右为空{if (cur _root){_root cur-_left;}else{if (cur parent-_left){parent-_left cur-_left;}else{parent-_right cur-_left;}}}else{//左右都不为空// 右树的最小节点(最左节点)Node* parent cur;Node* subLeft cur-_right;while (subLeft-_left){parent subLeft;subLeft subLeft-_left;}swap(cur-_key, subLeft-_key);if (subLeft parent-_left)parent-_left subLeft-_right;elseparent-_right subLeft-_right;}return true;}}return false;
}
templateclass K
void BSTreeK::InOrder()
{_InOrder(_root);cout endl;
}
templateclass K
void BSTreeK::_InOrder(Node* root)
{if (root nullptr)return;_InOrder(root-_left);cout root-_key ;_InOrder(root-_right);
}
