赣州网站设计有哪些,网站建设信息在哪儿发布,哈尔滨网络招聘,网站怎么制作视频一 什么是二叉搜索树 这个的结构特性非常重要#xff0c;是后面函数实现的结构基础#xff0c;二叉搜索树的特性是每个根节点都比自己的左树任一节点大#xff0c;比自己的右树任一节点小。
例如这个图#xff0c; 41是根节点#xff0c;要比左树大#xff0c;比右树小是后面函数实现的结构基础二叉搜索树的特性是每个根节点都比自己的左树任一节点大比自己的右树任一节点小。
例如这个图 41是根节点要比左树大比右树小满足但还不够还要去看看41的左子树的根和右子树的根是否满足更要判断这棵树上所有的根节点是不是都满足。而这棵树最厉害的地方之一我们用中序遍历(顺序左根右)便可以知道遍历结果为13,15,17,22,28,33,37,41,42,50,53,58,61,66,78排序不就排好了吗复杂度可媲美快排和归并。二叉搜索树另一个功能那当然就是搜索了例如我们要找66,66比根节点大就不用去左子树找了一下子少遍历一半然后就去右子树找和根节点58比较66比58大再去右子树找再比较就找到了最多查找高度次满二叉树下为log(n)。而二叉搜索树是不是完美无缺我也以为已经完美了不好意思我太年轻了直到我看到下面这颗树。 这个查找一次的效率就退化为O(N)了解决办法转化为平衡二叉树通俗点就是换个根节点重新构造二叉树例如把5或者7换成根节点大家可以试试练习一下构建二叉树构建完后的高度肯定比上图低查找效率不就高了吗。 在说二叉搜索树的实现前我们先说说什么是K结构什么是KV结构K结构就是只存一个数据这个数据称为关键码例如在英文词库里找一个英文单词就是用关键码查找需要的数据也是找到的关键码但是KV结构就不同了例如通过拼音找汉字这个时候拼音就是关键码但是我们需要的数据不是拼音这个关键码而是与之对应的汉字这就是KV结构。
二 二叉搜索树K结构实现
1 树的节点类
templateclass Tstruct TreeNode{TreeNode(const T val):_val(val)//_val可能为自定义类型在初始化列表初始化方便调用构造函数{;}TreeNode* left nullptr;TreeNode* right nullptr;T _val;};
2 BinaryTree树类
查找和排序都封装到了BinaryTree类中和list一样将节点类和树类分开封装。 (1) 默认构造函数
templateclass Tclass BinaryTree{public:typedef TreeNodeT Node;BinaryTree(Node*nodenullptr) 该构造函数是用节点指针初始化也可以再写个构造函数用个BinaryTree对象初始化:_root(node){;}private:Node* _root nullptr;树类只需根节点地址即可管理整棵树}; (2) 拷贝构造函数
因为两个copy函数都是用递归遍历二叉树所以只能再写一个子函数毕竟外部无法传_root指针。
void copy1(Node*tree)//前序遍历加复用insert拷贝二叉树{if (tree nullptr)return;insert(tree-_val); 先插入根节点的值,再去左子树和右子树获取节点的数值insert内部会开辟空间copy(tree-left);copy(tree-right);}方法二比较巧妙的是它的第一个参数,root是外部传参_root的引用所以rootnew node(),可以直接修改根节点而要拷贝左子树就传root-left的引用这样new出来的节点可以直接连接到根的_left指针上。右子树同理。void copy2(Node*root,Node*tree){if (tree nullptr)return;root new Node(tree-_val);copy2(root-left,tree-left);copy2(root-right,tree-right);}BinaryTree(const BinaryTreeTtree){//copy(tree._root);copy2(_root, tree._root);}
copy2函数传指针引用我是受下面一个成员函数实现的启发这个传引用一定要好好体会方便理解后面的函数非常巧妙。
(3) 赋值 用的是现代写法比如t1,t2是两个BinaryTree对象t1t2就会调用下面的赋值函数可是我的参数不是引用那按规定自定义类型传值传参要用拷贝构造(我在类的成员函数博客曾提及)t2传参给tree就要调用拷贝构造那tree就是一个新拷贝的对象我们就可以用swap直接交换tree和t1的根节点指针并且tree就是一个局部对象函数调用完后会自动调用析构函数省去了我们写析构t1树和创建新树的功夫都给编译器做了。(string模拟的赋值也用到了现代写法)
void swap(BinaryTreeT tree){std::swap(_root, tree._root);}void operator(BinaryTreeT tree){swap(tree);}
(4) find函数
搜索树怎么能缺少搜索功能呢 这个是find函数的子函数子函数原因和上面同理都是一开始传参外部无法获取_root因为递归遍历代码量少所以我实现的是递归版本bool _findR(Node*root,const T val){if (root nullptr)return false;if (val root-_val)//val比当前_val大去右树找{return _findR(root-right, val);}else if (val root-_val)//val比当前_val小去左树找{return _findR(root-left, val);}else {return true;//val和当前_val相等返回true}}//下面这个是外部调用的find函数只需要传要查找的值即可 bool find(const T val){return _findR(_root, val);}我之前在写find函数时我还想着返回false是不是应该当左树和右树都没找到才返回false,好一会才醒悟我们之所以去左树找就是因为要找的val比根节点的值小那右树更不会有了所以左树找到nullptr就应该返回false同理右树找到nullptr也返回false。
(5) insert函数
因为要递归去找合适的位置插入所以同样要写一个子函数 void _insertR(Node* root, const Tval){if (root nullptr)当找到空节点就可以插入了此时才是引用起作用的时候{root new Node(val); 直接就可以修改了因为root是上一个节点的left或者 right指针的引用。return;}Node* cur root;if (val cur-_val)//val大于当前根插入到右树去{_insertR(cur-right,val);}else if (val cur-_val)//val小于当前根插入到左树去{_insertR(cur-left, val);}else{return;}}void insert(const T val){_insertR(_root, val);}
(6) 中序遍历 void _Inorder(Node* root)//中序递归遍历{if (root nullptr)return;_Inorder(root-left); 一直往左子树递归直到左子树为空,算访问完可以访问根。cout root-_val ; _Inorder(root-right); 然后去右子树访问同样分为左子树根右子树}void Inorder(){_Inorder(_root);//调用子函数,外部无法获取私有成员_root}
(7) erase函数 bool _Rerase(Node*root,const Tval){if (root nullptr)return false;Node* cur root;if (val root-_val)//用_val找节点{return _Rerase(root-right, val);}else if (val root-_val){return _Rerase(root-left, val);}else//找到了{//该节点只有一个或者无子节点if (root-left nullptr) 由于root是上一节点左指针或者右指针的别名所以可以直接拿root-right来赋值给root否则还要 判断root-right是链接在上一节点的left指针还是 right指针。{root root-right;}else if (root-right nullptr){root root-left;}else{删除有两个子节点的节点-替换法找该节点左子树中最大的或者右子树中最小的来替换删除节点Node* leftMax root-left;while (leftMax-right){leftMax leftMax-right;}std::swap(leftMax-_val, root-_val);return _Rerase(root-left, val);调用_Rerase去删除leftMax节点这里必须要传root-left去左子树删除值为val的节点不能传root例如我们交换leftMax的7和root的8值如果传root,8的值比7大就会去右树删就找不到leftMax节点了但是root的左子树仍然满足二叉搜索的特性就可以找到leftMax节点并删除。 }delete cur; 该处统一释放删除节点并返回truereturn true;}}bool erase(const T val)//删除某个节点{return _Rerase(_root, val);}
三 kv结构实现 本来我以为kv结构是要将K结构的树大改当我实现后才发现赋值可以直接照搬find,inserterase中大量的if判断都是用关键码判断根本不需要改动中序遍历也就多打印一个数据还有insert和拷贝构造函数要在new一个节点的时候多传一个参数。
接下来就看看一些比较重要的改动在这里_key存关键码而我上面二叉树K结构中是_val存的关键码不要搞混了。
1 树的节点类 templateclass T,class Kstruct TreeNode{TreeNode(const T val,const Kkey):_val(val),_key(key){;} 类内可不加模板参数也就是说TreeNode等价于TreeNodeT,kTreeNode* left nullptr; TreeNode* right nullptr;T _val;//存与关键码对应的数据K _key;//_key存关键码};
2 BinaryTree类
有了先前K结构树的基础这里构造和析构函数我们就很好理解。
(1)构造和析构函数
templateclass T, class Kclass BinaryTree{public:typedef TreeNodeT,K Node;BinaryTree(Node* node nullptr) 默认构造无改变:_root(node){;}void _DestroyR(Node*root) 递归释放节点采用后序遍历的方式delete{if (root nullptr)return;_DestroyR(root-left);_DestroyR(root-right);delete root;root nullptr;}~BinaryTree(){_DestroyR(_root);}private:Node* _root nullptr; 成员变量是不变的毕竟kv结构的树用根节点同样可以管理};
}
(3)erase函数 bool _Rerase(Node* root, const T key){if (root nullptr)return false;Node* cur root; //记录节点方便后面deleteif (key root-_key){return _Rerase(root-right,key);}else if (key root-_key){return _Rerase(root-left, key);}else//找到了{//该节点只有一个或者无子节点if (root-left nullptr){root root-right;}else if (root-right nullptr){root root-left;}else{Node* leftMax root-left;while (leftMax-right){leftMax leftMax-right;}std::swap(leftMax-_val, root-_val); 在交换时要多交换一个值std::swap(leftMax-_key, root-_key);return _Rerase(root-left, key); 并且还是用key值去找leftMax删} 删除完leftMax后就直接return了就不会重复删除。delete cur;return true;}}bool erase(const T val)//删除某个节点{return _Rerase(_root, val);}
二叉搜索树中最复杂的就是erase函数大家在此处一定要画图理解。
