C++AVL树

上一篇文章中介绍了二叉搜索树, 这是一种非常方便的数据结构, 但是二叉搜索树在处理一些特殊情况的时候会很不方便, 例如: 最差情况下,二叉搜索树退化为单支树,其平均比较次数为N / 2 。于是在此基础上, AVL诞生了, 这是一种特殊的二叉搜索树。 AVL树的概念 二叉搜索树虽可以缩短查找的效率,但…

C++二叉搜索树

概念 二叉搜索树又称二叉排序树,它或者是一棵空树,或者是具有以下性质的二叉树: 若它的左子树不为空,则左子树上所有节点的值都小于根节点的值 若它的右子树不为空,则右子树上所有节点的值都大于根节点的值 它的左右子树也分别为二叉搜索树 二叉搜索树的查找 过程如图: 主体框架代码: #include &l…

C++ 二叉树实现

二叉树想必大家非常熟悉, 本文介绍的是如何实现一个二叉树类, 其功能包括前序、中序、后序遍历等, 以及一些经典题型的解析 直接亮代码主体结构: #include <iostream> #include <stack> #include <queue> #inclu…

C++ 多态

多态 《C++ Primer》 C++有三种方式支持多态性: 通过一个隐式转换,从“派生类指针或引用”转换到“其共有基类类型的指针或引用“ Query *pquery = new NameQuery("Glass"); 虚拟函数机制:pquery->eval(); 通过dy…

C++继承

继承 1. 继承的概念及定义 1.1 概念 继承机制是面向对象程序设计使代码可以复用的最重要的手段,它允许程序员在保持原有类特性的基础上进行扩展,增加功能,这样产生新的类,称派生类。继承呈现了面向对象程序设计的层次结构, 体现了由简单到复杂的认知过程。以前我们接触的复用都是函数复用,继承是类设计层次…

C++_map&set

1. map map文档 map是关联容器,它按照特定的次序(利用key比较)存储键值key和值value组合而成的元素。 在map中,键值key通常用于排序和唯一的标识元素,而值value中存储与此键值key关联的内容。键值key和值value的类型可能不同,在map内部,key与value通过成…

C++_stack和queue

1. stack stack的介绍 stack文档 template <class T, class Container = deque<T> > class stack; stack是一种容器适配器,用于在具有后进先出操作的上下文环境中,其删除只能从容器的一段进行元素的插入…

C++_deque

deque的文档 deque即双端队列,双端队列是动态大小的序列式容器,其可以向两端进行伸缩。 特定的库可以以不同的方式实现deque,但通常都是一种动态数组。不论在核中情况下,它都允许通过随机访问迭代器直接访问单个元素,可以根据需要动态的伸缩。 deque提供了一些与vector相似的功能,但de…

C++_list

list 1.list介绍 list文档 list是可以在常数范围内在任意位置进行插入和删除的序列式容器,并且该容器可以前后双向迭代。 list的底层是双向链表结构,双向链表中每个元素存储在互不相关的独立节点中,在节点通过指针指向其前一个元素和后一个元素。 list与forward_list非常相似…