网站建设简运维 简历,网站商城建设6,简答电子商务网站建设流程,婚纱设计网站首页文章目录1.二叉搜索树基本操作二叉搜索树的效率分析2. C实现1.二叉搜索树基本操作
二叉排序树是具有下列特性的二叉树#xff1a;
若左子树非空#xff0c;则左子树上所有结点的值均小于根结点的值。若右子树非空#xff0c;则右子树上所有结点的值均大于根结点的值。左、…
文章目录1.二叉搜索树基本操作二叉搜索树的效率分析2. C实现1.二叉搜索树基本操作
二叉排序树是具有下列特性的二叉树
若左子树非空则左子树上所有结点的值均小于根结点的值。若右子树非空则右子树上所有结点的值均大于根结点的值。左、右子树也分别是一棵二叉排序树
根据二叉排序树的定义左子树结点值 根结点值 右子树结点值。 所以对二叉排序树进行中序遍历可以得到一个递增的有序序列。
二叉排序树的搜索
从根结点开始沿某个分支逐层向下比较的过程。若二叉排序树非空先将给定值与根结点的关键字比较若相等则查找成功若不等,如果小于根结点的关键字则在根结点的左子树上查找否则在根结点的右子树上查找。
这个过程可以通过递归或者非递归实现实现
二叉排序树的插入
若原二叉排序树为空则直接插入结点若关键字k小于根结点值则插入到左子树若关键字k大于根结点值则插入到右子树。
插入的结点一定是一个新添加的叶结点且是查找失败时的查找路径上访问的最后一个结点的左孩子或右孩子.
二叉排序树的删除
在二叉排序树中删除一个结点时不能把以该结点为根的子树上的结点都删除必须先把被删除结点从存储二叉排序树的链表上摘下将因删除结点而断开的二叉链表重新链接起来同时确保二叉排序树的性质不会丢失。删除操作的实现过程按3种情况来处理 若被删除结点z是叶结点则直接删除不会破坏二叉排序树的性质 若结点z只有一棵左子树或右子树则让z的子树成为z父结点的子树替代z的位置 若结点z有左、右两棵子树则令z的直接后继或直接前驱替代z然后从二叉排序树中删去这个直接后继或直接前驱这样就转换成了第一或第二种情况。可以使用递归解决这个问题。 直接后继节点右子树中最左节点右子树最小节点 删除流程图具体看代码流程
二叉搜索树的效率分析
二叉排序树的查找效率主要取决于树的高度。 若二叉排序树的左、右子树的高度之差的绝对值不超过1这样的二叉排序树称为平衡二叉树它的平均查找长度为O(logN) 若二叉排序树是一个只有右(左)孩子的单支树(类似于有序的单链表)则其平均查找长度为O(N) a图的平均搜索成功长度ASL类似折半查找1x1 2x2……h×2h-1) 每层的节点不一定放满需要针对题目灵活处理 (1×12×23×44×3)÷102.9
b图的平均搜索成功长度ASL(110)/25.5 因为此时搜索二叉树由树型退化为线型平均搜索长度为n1/2
二叉排序树与二分查找相似。就平均时间性能而言二叉排序树上的查找和二分查找差不多。
但二分查找的判定树唯一而二叉排序树的查找不唯一相同的关键字其插入顺序不同可能生成不同的二叉排序树。
二叉排序树与二分搜索
二叉排序树无须移动结点只需修改指针即可完成插入和删除操作 平均执行时间为O(logN)二分查找的对象是有序顺序表若有插入和删除结点的操作所花的代价是O(n)。当有序表是静态查找表时宜用顺序表作为其存储结构采用二分查找实现其查找操作若有序表是动态查找表则应选择二叉排序树作为其逻辑结构.
2. C实现
// 二叉搜索树头文件实现
#include iostream
#include vector
#include algorithmstruct TreeNode
{int _val;TreeNode *_left;TreeNode *_right;TreeNode(int val) : _val(val), _left(nullptr), _right(nullptr) {}
};class SearchTree
{
private:TreeNode *root nullptr;/*** brief 在二叉搜索树中查找节点值为val的节点** param val 查找节点的值* param node 如果找到了这个节点node就是这个节点的地址否则为null* param part part这个节点的父亲如果这个节点为null,这个参数输出null*/void _find(int val, TreeNode *node, TreeNode *part){TreeNode *ptr root;TreeNode *prev nullptr;while (ptr ! nullptr){if (ptr-_val val){node ptr;break;}else if (ptr-_val val){prev ptr;ptr ptr-_left;}else{prev ptr;ptr ptr-_right;}}node ptr;part prev;}bool _erase(int val, TreeNode *node){if (node nullptr){return false;}else{if (node-_val val){_erase(val, node-_left);}else if (node-_val val){_erase(val, node-_right);}else{if (node-_left nullptr){TreeNode *del node;node node-_right;delete del;}else if (node-_right nullptr){TreeNode *del node;node node-_left;delete del;}else{// 找要删除节点的后继TreeNode *right_min_node node-_right;while (right_min_node-_left ! nullptr){right_min_node right_min_node-_left;}// 记录right_min_node这个节点的值吧这个节点的值和node节点交换在删除right_min_node这个节点即可// right_min_node这个节点的左子树一定为空在上面顶点流程会处理int tmp right_min_node-_val;_erase(tmp, node-_right);node-_val tmp;}}return true;}}// 判断一棵树是否是二叉搜索树,检查每个节点是否满足节点值的取值范围bool _isSearchTree(TreeNode *node, int min, int max){if (node nullptr)return true;if (node-_val min || node-_val max){return false;}return _isSearchTree(node-_left, min, node-_val - 1) _isSearchTree(node-_right, node-_val 1, max);}void _display_inorder(TreeNode *node){if (node nullptr)return;_display_inorder(node-_left);std::cout node-_val ;_display_inorder(node-_right);}int _max(){TreeNode *node root;while (node-_right ! nullptr){node node-_right;}return node-_val;}int _min(){TreeNode *node root;while (node-_left ! nullptr){node node-_left;}return node-_val;}public:SearchTree() default;SearchTree(const std::vectorint buff){for (int i 0; i buff.size(); i){insert(buff[i]);}}// 不允许重复插入相同的值bool insert(int val){if (root nullptr){root new TreeNode(val);return true;}else{TreeNode *pos nullptr;TreeNode *prev nullptr;_find(val, pos, prev);if (pos ! nullptr){// 之前插入过值重复return false;}else{// posnullptr;if (prev-_val val){prev-_left new TreeNode(val);}else{prev-_right new TreeNode(val);}return true;}}}// 查找节点值为val的节点bool find(int val){TreeNode *node;TreeNode *part;_find(val, node, part);return node ! nullptr;}// 删除搜索二叉树节点bool erase(int val){return _erase(val, root);}// 判断这颗树是否为二叉搜索树bool isSearchTree(){return _isSearchTree(root, _min(), _max());}// 中序遍历二叉搜索树void inorder(){_display_inorder(root);std::cout \n;}
};测试代码
#include SearchTree.h
#include time.husing namespace std;#define TIMES 10int main(int argc, char const *argv[])
{srand((unsigned int)time(0));// vectorint ret {1, 2, 3};vectorint ret;for (int i 0; i TIMES; i){ret.push_back(rand() % 100);}SearchTree tree(ret);tree.inorder();tree.insert(40);tree.inorder();cout tree.isSearchTree() endl;tree.insert(1);tree.erase(40);tree.inorder();cout tree.isSearchTree() endl;return 0;
}
