制造企业网站的建设目标,黑马程序员培训在哪里,珠海企业网站建设公,广东省网站备案系统目录 概念 性能分析 二叉搜索树的插入
二叉树的查找
二叉树的前序遍历
二叉搜索树的删除#xff08;重点#xff09; 完整代码 key与value的使用 概念 对于一个二叉搜索树 若它的左子树不为空#xff0c;则左子树上所有的节点的值都小于等于根节点的值若它的右子树不为空…目录 概念 性能分析 二叉搜索树的插入
二叉树的查找
二叉树的前序遍历
二叉搜索树的删除重点 完整代码 key与value的使用 概念 对于一个二叉搜索树 若它的左子树不为空则左子树上所有的节点的值都小于等于根节点的值若它的右子树不为空则右字数上所有的节点的值都大于等于根节点的值它的左右子树也分别为二叉搜索树二叉搜索树中可以支持插入相等的值也可以不支持插入相等的值具体看使用场景 templateclass K,class V
struct BSTreeNode
{typedef BSTreeNodeK, V Node;BSTreeNode(const K key,const V val):_key(key),_value(val){}K _key;V _value;Node* _left nullptr;Node* _right nullptr;
}; 性能分析 指出二叉搜索树 最优情况下二叉搜索树近似为完全二叉树高度为最差情况下二叉搜索树退化为类似于单支树高度为最优情况下增删查改为最差情况下增删查改为综合来讲时间复杂度为 指出二分查找 二分查找需要在允许下标随机访问的结构中二分查找需要在有序的结构中二分查找的时间复杂度为二分查找对应的结构一般为数组它挪动数据的时间复杂 二叉搜索树的插入 树为空直接增新节点赋值给root指针树不为空按照性质插入值比当前节点大走右边反之走左边插入空位置如果支持插入相等的值可以插左边或者右边但是插左边就都插左边反之相同 int num[] { 8, 3, 1, 10, 6, 4, 7, 14, 13 }; bool Insert(const K key, const V value)
{if (_root nullptr){_root new Node(key, value);return true;}else{bool right true;Node* p _root;Node* c _root;while (c ! nullptr){p c;if (key c-_key){right true;c p-_right;}else if(key c-_key){right false;c p-_left;}else{return false;}}c new Node(key, value);if (right){p-_right c;}else{p-_left c;}return true;}
}
二叉树的查找 从根开始查找key比节点大就走右比节点小就走左边最多查找高度次数走到空还没找到就不存在不支持插入相等的值找到x就返回反之继续查找直到高度次 Node* Find(const K key,Node** p nullptr){ Node* ptr _root;while (ptr){if (key ptr-_key){if (p)*p ptr;ptr ptr-_right;}else if (key ptr-_key){if (p)*p ptr;ptr ptr-_left;}elsereturn ptr;}return ptr;}
二叉树的前序遍历 采用递归打印左边节点打印中间节点打印右边节点 void _InOrder(Node* root) {if (root nullptr) return;_InOrder(root-_left);cout root-_key { root-_value } ;_InOrder(root-_right);}
二叉搜索树的删除重点 先查找是否存在不存在返回false若存在有以下四种情况 删除节点的左右孩子均为空 直接删除然后给空 删除节点的左右孩子为空另一边不为空 把节点的父亲对应的孩子节点的指针指向孩子不为空的一边然后删除节点 删除节点左右均不为空 找左子树的最大节点右子树的最小节点替代删除节点然后删除最值节点 bool Erase(const K key)
{Node* par _root;Node* ptr Find(key,par);if (!ptr)return false;if (ptr par){delete ptr;_root nullptr;return true;}if(!ptr-_left!ptr-_right){if(par-_left ptr)par-_left nullptr;if(par-_right ptr)par-_right nullptr;delete ptr;return true;}else if (!ptr-_left ptr-_right)//左空右不空{if (par-_left ptr){par-_left ptr-_right;}if (par-_right ptr){par-_right ptr-_right;}delete ptr;return true;}else if(ptr-_left !ptr-_right){if (par-_left ptr){par-_left ptr-_left;}if (par-_right ptr){par-_right ptr-_left;}delete ptr;return true;}else//两边均不为空直接替换操作{//找左侧最大节点Node* Max ptr-_left;Node* Maxp ptr;while (Max-_right ! nullptr){Maxp Max;Max Max-_right;}//交换ptr-_key Max-_key;ptr-_value Max-_value;//删除MAX的位置if (Maxp ptr){ptr-_left Max-_left;}else if (Max-_left){Maxp-_right Max-_left;}else{Maxp-_right Max-_right;}//删除Maxdelete Max;return true;}return false;
} 完整代码
#pragma once
#includeiostream
#includestring
using namespace std;templateclass K,class V
struct BSTreeNode
{
public:typedef BSTreeNodeK, V Node;BSTreeNode(const K key,const V val):_key(key),_value(val){}K _key;V _value;Node* _left nullptr;Node* _right nullptr;
};templateclass K, class V
class BSTree
{typedef BSTreeNodeK, V Node;
public:bool Insert(const K key, const V value) {if (_root nullptr) {_root new Node(key, value);return true;}else {bool right true;Node* p _root;Node* c _root;while (c ! nullptr) {p c;if (key c-_key) {right true;c p-_right;}else if (key c-_key){right false;c p-_left;}else{return false;}}c new Node(key, value);if (right){p-_right c;}else{p-_left c;}return true;}}Node* Find(const K key,Node** p nullptr){ Node* ptr _root;while (ptr){if (key ptr-_key){if (p)*p ptr;ptr ptr-_right;}else if (key ptr-_key){if (p)*p ptr;ptr ptr-_left;}elsereturn ptr;}return ptr;}bool Erase(const K key){Node* par _root;Node* ptr Find(key,par);if (!ptr)return false;if (ptr par){delete ptr;_root nullptr;return true;}if(!ptr-_left!ptr-_right){if(par-_left ptr)par-_left nullptr;if(par-_right ptr)par-_right nullptr;delete ptr;return true;}else if (!ptr-_left ptr-_right)//左空右不空{if (par-_left ptr){par-_left ptr-_right;}if (par-_right ptr){par-_right ptr-_right;}delete ptr;return true;}else if(ptr-_left !ptr-_right){if (par-_left ptr){par-_left ptr-_left;}if (par-_right ptr){par-_right ptr-_left;}delete ptr;return true;}else//两边均不为空直接替换操作{//找左侧最大节点Node* Max ptr-_left;Node* Maxp ptr;while (Max-_right ! nullptr){Maxp Max;Max Max-_right;}//交换ptr-_key Max-_key;ptr-_value Max-_value;//删除MAX的位置if (Maxp ptr){ptr-_left Max-_left;}else if (Max-_left){Maxp-_right Max-_left;}else{Maxp-_right Max-_right;}//删除Maxdelete Max;return true;}return false;}void InOrder(){_InOrder(_root);}
private:void _InOrder(Node* root) {if (root nullptr) return;_InOrder(root-_left);cout root-_key { root-_value } ;_InOrder(root-_right);}Node* _root nullptr;
}; key与value的使用
void TestBSTree()
{BSTreestring, string dict;dict.Insert(insert, 插入);dict.Insert(erase, 删除);dict.Insert(left, 左边);dict.Insert(string, 字符串);string str;while (cin str){auto ret dict.Find(str);if (ret){cout str : ret-_value endl;}else{cout 单词拼写错误 endl;}}//string strs[] { 苹果, 西瓜, 苹果, 樱桃, 苹果, 樱桃, 苹果, 樱桃, 苹果 };统计水果出现的次//BSTreestring, int countTree;//for (auto str : strs)//{// auto ret countTree.Find(str);// if (ret NULL)// {// countTree.Insert(str, 1);// }// else// {// ret-_value;// }//}//countTree.InOrder();
}
