怎么搭建购物网站,seo网络推广优化教程,3d建模培训班有用吗,南宁伯才网络目录
1.二叉搜索树的概念
2.二叉搜索树的操作
3. 二叉树的实现
4.二叉搜索树的应用
5. 二叉树的性能分析
6. 二叉树进阶练习题 1.二叉搜索树的概念
二叉搜索树又称二叉排序树#xff0c;它或者是一棵空树#xff0c;或者是具有以下性质的二叉树#xff1a;
若它的左…目录
1.二叉搜索树的概念
2.二叉搜索树的操作
3. 二叉树的实现
4.二叉搜索树的应用
5. 二叉树的性能分析
6. 二叉树进阶练习题 1.二叉搜索树的概念
二叉搜索树又称二叉排序树它或者是一棵空树或者是具有以下性质的二叉树
若它的左子树不为空则左子树上所有节点的值都小于根节点的值若它的右子树不为空则右子树上所有节点的值都大于根节点的值它的左右子树也分别为二叉搜索树
二叉搜索树BSTBinary Search Tree也称二叉排序树或二叉查找树。
2.二叉搜索树的操作 int a[] {8, 3, 1, 10, 6, 4, 7, 14, 13};
1. 二叉搜索树的查找
a、从根开始比较查找比根大则往右边走查找比根小则往左边走查找。b、最多查找高度次走到到空还没找到这个值不存在。
2. 二叉搜索树的插入 插入的具体过程如下
a. 树为空则直接新增节点赋值给root指针b. 树不空按二叉搜索树性质查找插入位置插入新节点
3. 二叉搜索树的删除 首先查找元素是否在二叉搜索树中如果不存在则返回否则要删除的结点可能分下面四种情况
a. 要删除的结点无孩子结点b. 要删除的结点只有左孩子结点c. 要删除的结点只有右孩子结点d. 要删除的结点有左、右孩子结点 看起来有待删除节点有4中情况实际情况a可以与情况b或者c合并起来把一个孩子看作空节点因此真正的删除过程如下
情况b删除该结点且使被删除节点的双亲结点指向被删除节点的左孩子结点然后直接删除该节点 -- 即直接删除。情况c删除该结点且使被删除节点的双亲结点指向被删除结点的右孩子结点然后直接删除该节点 -- 即直接删除。情况d在它的右子树中寻找中序下的第一个结点(关键码最小)用它的值填补到被删除节点中再来处理该结点的删除问题 -- 替换法删除。即用左子树的最大节点或右子树的最小节点来替换。
3. 二叉树的实现
代码中有每个操作都有两种写法一种是非递归写法一种是递归写法。
namespace key
{templateclass Kstruct BSTreeNode{BSTreeNodeK* left;BSTreeNodeK* right;K _key;BSTreeNode(const K key K()):left(nullptr), right(nullptr), _key(key){}};templateclass Kclass BSTree{typedef BSTreeNodeK Node;public:BSTree():_root(nullptr){}//C11 强制生成默认构造//BSTree() default; BSTree(const BSTreeK root){_root Copy(root._root);}BSTreeK operator(BSTreeK tree){swap(tree._root, _root);return *this;}bool Insert(const K key)//插入{if (_root nullptr){_root new Node(key);return true;}else{Node* cur _root;Node* parent nullptr;while (cur){parent cur;if (cur-_key key){cur cur-left;}else if (cur-_key key){cur cur-right;}else{return false;}}cur new Node(key);if (cur-_key parent-_key){parent-left cur;}else{parent-right cur;}return true;}}bool Find(const K key){Node* cur _root;while (cur){if (cur-_key key){return true;}else if (cur-_key key){cur cur-right;}else{cur cur-left;}}return false;}bool Erase(const K key)//删除{Node* cur _root;Node* parent nullptr;while (cur){if (cur-_key key){parent cur;cur cur-left;}else if (cur-_key key){parent cur;cur cur-right;}else//找到删除{if (cur-left nullptr){//左为空if (parent nullptr)//根节点{_root cur-right;}else{if (cur parent-left){parent-left cur-right;}else if (cur parent-right){parent-right cur-right;}delete cur;}}else if (cur-right nullptr){//右为空if (parent nullptr)//根节点{_root cur-left;}else{if (cur parent-left){parent-right cur-left;}else if (cur parent-right){parent-right cur-left;}delete cur;}}else{//左右都不为空//右树的最小节点最左节点Node* subLeft cur-right;Node* parent cur;while (subLeft-left){parent subLeft;subLeft subLeft-left;}if (subLeft cur-right)//右树的最左节点是根最左节点不是父节点的左孩子{swap(subLeft-_key, cur-_key);parent-right subLeft-right;}else{swap(subLeft-_key, cur-_key);parent-left subLeft-right;}delete subLeft;}return true;}}return false;}//递归遍历void InOrder(){_InOrder(_root);cout endl;}//递归查找bool FindR(const K key){return _FindR(_root, key);}//递归插入bool InsertR(const K key){return _InsertR(_root, key);}//递归删除bool EraseR(const K key){return _EraseR(_root, key);}~BSTree(){Destroy(_root);}private:Node* Copy(Node* root){if (root nullptr){return nullptr;}Node* newRoot new Node(root-_key);newRoot-left Copy(root-left);newRoot-right Copy(root-right);return newRoot;}void Destroy(Node* root)//auto不能做函数参数{if (root nullptr){return;}Destroy(root-left);Destroy(root-right);delete root;root nullptr;}bool _EraseR(Node* root, const K key){if (root nullptr){return false;}if (root-_key key){return _EraseR(root-left, key);}if (root-_key key){return _EraseR(root-right, key);}else{//删除,用引用十分巧妙if (root-right nullptr){//引用的是父节点的一个指针Node* del root;root root-left;delete del;return true;}else if (root-left nullptr){Node* del root;root root-right;delete del;return true;}else{Node* subLeft root-right;while (subLeft-left){subLeft subLeft-left;}swap(subLeft-_key, root-_key);//让子树递归删除 return _EraseR(root-right, key);}}}bool _InsertR(Node* root, const K key){//这里root用引用if (root nullptr){root new Node(key);return true;}if (root-_key key){//引用的是父节点的右孩子_InsertR(root-right, key);}if (root-_key key){_InsertR(root-left, key);}else{return false;}}//bool _InsertR(Node* root, const K key)//{// if (root nullptr)// {// _root new Node(key);// return true;// }// if (key root-_key)// {// return false;// }// if (key root-_key)// {// if (root-left nullptr)// {// root-left new Node(key);// return true;// }// else// {// return _InsertR(root-left, key);// }// }// if (key root-_key)// {// if (root-right nullptr)// {// root-right new Node(key);// return true;// }// else// {// return _InsertR(root-right, key);// }// }//}bool _FindR(Node* root, const K key){if (root nullptr){return false;}else if (root-_key key){return true;}else if (root-_key key){return _FindR(root-right, key);}else{return _FindR(root-left, key);}}void _InOrder(Node* root){if (root nullptr){return;}_InOrder(root-left);cout root-_key ;_InOrder(root-right);}private:Node* _root nullptr;};
}
4.二叉搜索树的应用
1. K模型K模型即只有key作为关键码结构中只需要存储Key即可关键码即为需要搜索到的值。
比如给一个单词word判断该单词是否拼写正确具体方式如下
以词库中所有单词集合中的每个单词作为key构建一棵二叉搜索树在二叉搜索树中检索该单词是否存在存在则拼写正确不存在则拼写错误。
2. KV模型每一个关键码key都有与之对应的值Value即Key, Value的键值对。该种方式在现实生活中非常常见
比如英汉词典就是英文与中文的对应关系通过英文可以快速找到与其对应的中文英文单词与其对应的中文word, chinese就构成一种键值对再比如统计单词次数统计成功后给定单词就可快速找到其出现的次数单词与其出现次数就是word, count就构成一种键值对
//改造后的 key_value 结构
namespace key_value
{templateclass K, class Vstruct BSTreeNode{BSTreeNodeK,V* left;BSTreeNodeK,V* right;K _key;V _value;BSTreeNode(const K key K(),const V value V()):left(nullptr), right(nullptr), _key(key), _value(value){} };templateclass K, class Vclass 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{Node* cur _root;Node* parent nullptr;while (cur){parent cur;if (cur-_key key){cur cur-left;}else if (cur-_key key){cur cur-right;}else{return false;}}cur new Node(key,value);if (cur-_key parent-_key){parent-left cur;}else{parent-right cur;}return true;}}Node* Find(const K key){Node* cur _root;while (cur){if (cur-_key key){return cur;}else if (cur-_key key){cur cur-right;}else{cur cur-left;}}return nullptr;}bool Erase(const K key){Node* cur _root;Node* parent nullptr;while (cur){if (cur-_key key){parent cur;cur cur-left;}else if (cur-_key key){parent cur;cur cur-right;}else//找到删除{if (cur-left nullptr){//左为空if (parent nullptr)//根节点{_root cur-right;}else{if (cur parent-left){parent-left cur-right;}else if (cur parent-right){parent-right cur-right;}delete cur;}}else if (cur-right nullptr){//右为空if (parent nullptr)//根节点{_root cur-left;}else{if (cur parent-left){parent-right cur-left;}else if (cur parent-right){parent-right cur-left;}delete cur;}}else{//左右都不为空//右树的最小节点最左节点Node* subLeft cur-right;Node* parent cur;while (subLeft-left){parent subLeft;subLeft subLeft-left;}if (subLeft cur-right)//右树的最左节点是根最左节点不是父节点的左孩子{swap(subLeft-_key, cur-_key);parent-right subLeft-right;}else{swap(subLeft-_key, cur-_key);parent-left subLeft-right;}delete subLeft;}return true;}}return false;}//递归遍历void InOrder(){_InOrder(_root);cout endl;}private:void _InOrder(Node* root){if (root nullptr){return;}_InOrder(root-left);cout root-_key : root-_value endl;_InOrder(root-right);}private:Node* _root nullptr;};
}
5. 二叉树的性能分析
插入和删除操作都必须先查找查找效率代表了二叉搜索树中各个操作的性能。
对有n个结点的二叉搜索树若每个元素查找的概率相等则二叉搜索树平均查找长度是结点在二叉搜索树的深度的函数即结点越深则比较次数越多。
但对于同一个关键码集合如果各关键码插入的次序不同可能得到不同结构的二叉搜索树 最优情况下二叉搜索树为完全二叉树(或者接近完全二叉树)其时间复杂度为O(logN)。
最差情况下二叉搜索树退化为单支树(或者类似单支)其时间复杂度为O(N)。
问题如果退化成单支树二叉搜索树的性能就失去了。那能否进行改进不论按照什么次序插入关键码二叉搜索树的性能都能达到最优那么我们后续文章学习的AVL树和红黑树就可以上场了。
6. 二叉树进阶练习题
这些题目更适合使用C完成难度也更大一些
二叉树创建字符串。OJ链接二叉树的分层遍历1。OJ链接二叉树的分层遍历2。OJ链接给定一个二叉树, 找到该树中两个指定节点的最近公共祖先 。OJ链接二叉树搜索树转换成排序双向链表。OJ链接根据一棵树的前序遍历与中序遍历构造二叉树。OJ链接根据一棵树的中序遍历与后序遍历构造二叉树。OJ链接二叉树的前序遍历非递归迭代实现 。OJ链接二叉树中序遍历 非递归迭代实现。OJ链接二叉树的后序遍历 非递归迭代实现。OJ链接
本篇详细代码可查看我的Gitee
本篇结束
