美工需要的网站,电子商务网站建设第一章课后,自己装修设计app,建设彩票网站需要多少投资前言 二叉搜索树#xff08;搜索二叉树#xff0c;Binary search tree#xff09;是一种特殊的二叉树。其规则为#xff1a;左子树的值一定小于等于根#xff0c;右子树的值一定大于等于根#xff0c;并且左右子树也为搜索二叉树。
二叉搜索树的插入 1.若树为空#xf…前言 二叉搜索树搜索二叉树Binary search tree是一种特殊的二叉树。其规则为左子树的值一定小于等于根右子树的值一定大于等于根并且左右子树也为搜索二叉树。
二叉搜索树的插入 1.若树为空插入的数据为根节点的数据 2.若树不为空按照二叉搜索树的性质判断节点的值与插入值的大小关系。若大于节点的值则往右边走。若小于节点的值则往左边走
二叉搜索树的搜索 1.从根节点开始查找小于节点值则往左边大于节点值则往右边。找到就返回 2.若遍历完都没有找到即返回找不到
二叉搜索树的删除重点 1.删除叶子节点既没有左右孩子直接删除然后将其父亲节点的指针赋值为nullptr 2.删除只有一个孩子的节点直接删除然后将孩子连接至父亲节点 3.删除有两个孩子的节点不能直接删除。从这个节点出发寻找左子树的最大值既最右节点或者右子树的最小值既最左节点。将找到的值的赋值给要删除的节点然后删除我们找到的节点这样就能保证不会破坏二叉搜索树的性质。 补充若删除根节点的话要单独处理一下
代码实现
templateclass K
struct BSNode
{K _val;BSNodeK* _left;BSNodeK* _right;BSNode(const K key):_val(key), _left(nullptr), _right(nullptr){ }
};templateclass K
class BSTree
{//typedef BSNodeK Node;using Node BSNodeK;//新的重命名方式
public:void Insert(const K key)//搜索二叉树的插入(不允许冗余){Node* cur _root;if (!cur){_root new Node(key);}else{Node* parent cur;while (cur){if (cur-_val key){parent cur;cur cur-_right;}else{parent cur;cur cur-_left;}}if (parent-_val key){parent-_right new Node(key);}else if (parent-_val key){parent-_left new Node(key);}elsereturn;}}bool Search(const K key)//查找{Node* cur _root;while (cur){if (cur-_val key){cur cur-_right;}else if (cur-_val key){cur cur-_left;}elsereturn true;}return false;}//搜索二叉树的删除void Erase(const K key){Node* cur _root;Node* parent cur;//先找到相应位置while (cur){if (cur-_val key){parent cur;cur cur-_right;}else if (cur-_val key){parent cur;cur cur-_left;}elsebreak;}if (!cur)return;//进行删除if (!cur-_left !cur-_right)//没有孩子{if (cur _root)//若删除根节点{delete _root;_root nullptr;}else{if (parent-_left cur)parent-_left nullptr;elseparent-_right nullptr;delete cur;cur nullptr; // 显式置空}}else if (!cur-_left || !cur-_right)//有一个孩子{if (cur _root)//若删除根节点{if (cur-_left){_root cur-_left;delete cur;cur nullptr; // 显式置空}else{_root cur-_right;delete cur;cur nullptr; // 显式置空}}else{if (!cur-_left){if (parent-_left cur){parent-_left cur-_right;delete cur;cur nullptr; // 显式置空}else{parent-_right cur-_right;delete cur;cur nullptr; // 显式置空}}else{if (parent-_left cur){parent-_left cur-_left;delete cur;cur nullptr; // 显式置空}else{parent-_right cur-_left;delete cur;cur nullptr; // 显式置空}}}}else//有两个孩子{//寻找左子树最大值或右子树最小值来替换curNode* Replace cur-_left;Node* Replacep cur;while (Replace-_right){Replacep Replace;Replace Replace-_right;}swap(Replace-_val, cur-_val);if(Replacep-_right Replace)Replacep-_right Replace-_left;elseReplacep-_left Replace-_left;delete Replace;}}void Inorder()//中序遍历{_Inorder(_root);cout endl;}private:void _Inorder(Node* root)//中序遍历{if (!root)return;_Inorder(root-_left);cout root-_val ;_Inorder(root-_right);}Node* _root nullptr;
};
