做北美市场的外贸网站,软件开发中需要哪些可行性分析,深圳网站建设php,为什么做网站能赚钱#x1f44d;作者主页#xff1a;进击的1 #x1f929; 专栏链接#xff1a;【1的数据结构】 文章目录 一#xff0c;什么是二叉搜索树二#xff0c;二叉搜索树的操作及其实现2.1 插入操作及其实现2.2 查找操作及其实现2.3 删除操作及其实现 三#xff0c;构造及其析构四… 作者主页进击的1 专栏链接【1的数据结构】 文章目录 一什么是二叉搜索树二二叉搜索树的操作及其实现2.1 插入操作及其实现2.2 查找操作及其实现2.3 删除操作及其实现 三构造及其析构四二叉搜索树的应用 一什么是二叉搜索树
二叉搜索书又叫二叉排序树或二叉查找树其左子数上的节点小于根节点右子树上的节点大于根节点。 如图就是一颗二叉搜索树。
二二叉搜索树的操作及其实现
2.1 插入操作及其实现
二叉搜索树的插入其先根据插入值的大小确定插入的位置并且若是有相同的值则不会进行插入。确定位置的依据是我们上述的二叉搜索树的特性左子树上的节点小于根节点右子树上的节点大于根节点。 当确定好位置后我们申请节点将新节点链接到树中。 下面是插入的两种实现
非递归
typedef BSTreeNodeK Node;public:bool Insert(const K key){if (_root nullptr){_root new Node(key);return true;}Node* cur _root;Node* parent _root;//记录其父节点方便链接while (cur ! nullptr)//找位置{if (key cur-_key){parent cur;cur cur-left;}else if (key cur-_key){parent cur;cur cur-right;}else{return false;}}cur new Node(key);//链接过程if (parent-_key key){parent-left cur;}else{parent-right cur;}return true;}递归 bool InsertR(const K key){return _InsertR(_root, key);}bool _InsertR(Node* root,const K key){if (root nullptr)//为空则说明已经找好了位置可以进行插入{Node* cur new Node(key);root cur;return true;}if (key root-_key){_InsertR(root-left, key);}else if (key root-_key){_InsertR(root-right, key);}else{return false;//遇到相同的值}return true;}
由于在类外无法访问根节点_root所以无法给_InsertR()传参因此我们多写了一层函数在类里面调用插入的递归函数。这里有一个非常重要的细节就是在传root时我们使用的是引用。这时我们就可以直接进行链接不需要记录其父节点了。
2.2 查找操作及其实现
其查找利用其二叉搜索树的特性当树为完全二叉树或满二叉树时其效率可以达到lgN (N为数的高度。 下面为查找的两种实现方法
非递归
bool Find(const K key){Node* cur _root;while (cur){if (key cur-_key){cur cur-left;}else if (key cur-_key){cur cur-right;}else{return true;}}return false;}递归实现
bool _FindR(Node* root, const K key){if (root nullptr){return false;}if (key root-_key){_FindR(root-left, key);}else if (key root-_key){_FindR(root-right, key);}else{return true;}}2.3 删除操作及其实现
删除操作我们可以分为几种情况
删除节点没有孩子删除节点有右孩子删除节点有左孩子删除节点有左右孩子 对这四种情况我们又可以进行合并将1与23归为一类。 对于有两个节点的情况我们在找到要删除节点后在找到右子树的最小值或左子树的最大值将其值与删除节点值进行交换这时我们就只需要删除右子树最小值或左子树最大值了。 需要注意的是其右子树最小值或左子树最大值后可能还有节点因此要进行判断。
非递归
bool Erase(const K key){Node* cur _root;Node* parent _root;while (cur ! nullptr){if (key cur-_key){parent cur;cur cur-left;}else if (key cur-_key){parent cur;cur cur-right;}else{//左为空if (cur-left nullptr){if (cur _root){_root cur-right;}else if (key parent-_key){parent-left cur-right;}else{parent-right cur-right;}delete cur;}else if (cur-right nullptr)//右为空{if (cur _root){_root cur-left;}else if (key parent-_key){parent-left cur-left;}else{parent-right cur-left;}delete cur;}else//都不为空{//先找右子树的最小值Node* Minparent cur;Node* Mincur-right;while (Min-left ! nullptr){Minparent Min; Min Min-left;}std::swap(Min-_key, cur-_key);if (Minparent-left Min){Minparent-left Min-right;}else{Minparent-right Min-right;}delete Min;}return true;}}return false;}
递归 bool _EraseR(Node* root, const K key){if (root nullptr){return false;}if (key root-_key){_EraseR(root-left, key);}else if (key root-_key){_EraseR(root-right, key);}else{Node* del root;//找右子树最小if (root-left nullptr){root root-right;}else if (root-right nullptr){root root-left;}else{Node* min root-right;//找右子树最小值while (min-left){min min-left;}std::swap(root-_key, min-_key);return _EraseR(root-right, key);}delete del;return true;}}三构造及其析构
//拷贝构造BSTree(const BSTreeK t){_root Copy_root(t._root);}Node* Copy_root(Node* root){if (root nullptr){return nullptr;}Node* copy_root new Node(root-_key);copy_root-left Copy_root(root-left);copy_root-right Copy_root(root-right);return copy_root;}//赋值重载BSTree operator(BSTreeK T){std::swap(T._root,this-_root);return *this;}//析构~BSTree(){Destory(_root);}void Destory(Node* root){if (root nullptr){return;}Destory(root-left);Destory(root-right);delete root;root nullptr;}拷贝构造有一些像前序遍历我们遇到一个节点就构造一个节点最后在递归返回时将其链接起来。 析构函数则是像后续遍历。
四二叉搜索树的应用
K模型K模型即只有key作为关键码结构中只需要存储Key即可关键码即为需要搜索到的值。KV模型每一个关键码key都有与之对应的值Value即Key, Value的键值对。如中英文对照。
二叉搜索树的性能对于插入和删除来说都必须要先查找插入查找插入的位置删除查找删除的节点。因此其查找的性能代表了二叉树的性能。其查找的性能于树的深度有关但对于同一个集合其插入的顺序不同那么形成的树也是不同的。我们期望的最好的情况是它能够形成一个完全二叉树或接近完全二叉树的树。此时他的查找的效率能够达到lgN但其也有可能会形成一个单支树此时效率最差为N。
