平衡二叉树

二叉树的插入和删除 删除二叉树所有节点,用后序遍历的方式删除,也就是先删除叶子节点,再删除根节点,这样能减少父子关系的处理。 无序二叉树查询没有优势,不如用链表。 有序二叉树可以折半查找,此时有序树才有意义,所以,插入新节点时也要保持有序。 只有中序遍历才能看出是否为有序树。 补充: 二叉树删除节点分为三种情况: 1、

二叉树

二叉树 树的叶子、高度(深度),是最重要的两个概念。 有序树和无序树: 根(包括子树的根)左边的所有子节点根(或者左边=根),为有序树,反之为无序树。 二叉树第i(i >= 1)层最多有2^(i-1) 个节点; 深度为k的二叉树最多有2^k – 1 个节点,深度为k且有2^k – 1 个节点称为

栈_队列_迭代器

拾遗 pHdr(堆指针) 返回 _CrtMemBlockHeader,可以遍历堆结构 栈、队列 利用栈结构,可以很方便地处理后缀表达式。 中缀表达式转后缀表达式规则描述如下: 1. 从左向右扫遍历表达式; 2. If 当前遍历到的字符 ch 是操作数,则打印; 3. Else If 当前遍历的ch是 ‘(’, 入栈;

链表

拾遗 运行时获取变量类型: 链表 空间:空间可以不连续,逻辑连续即可。 优缺点与数组相反。 循环链表,遍历方便,从任何一个节点开始遍历都可以。 链表总结: 空间:链式存储结构,空间可以不连续,逻辑连续即可。 时间: 增加:O(1),常量阶,快; 删除:O(1),常量阶,快; 修改:O(1),常量阶,快; (以上都是通过

动态数组

封装数据结构,效率优先,靠调用保持健壮性,所以一般不会出现try-catch,但是可以加断言宏,方便找问题。 new ((void*) obj) A; //不申请obj的空间,只调用A的构造函数,非标准 动态数组基本数据成员和功能: 成员: Type 元素 元素的个数 总共申请的空间大小 功能: 插入数据到末尾 在指定

数据结构和算法

自己在练习中总结各种数据结构的优缺点。 算法的五个特性: 1、有穷性 2、确定性 3、可行性 4、输入量(可以没有) 5、输出量 算法设计要求: 1、正确性 2、可读性 3、健壮性 4、高效与低存储 时间复杂度由低到高: 时间复杂度是指算法可执行时间的增长率,不能得出具体时间。 时间复杂度算增长率,只算最高阶。 快速判

编码技巧汇总

1、利用数组下标简化实现过程 现在有一个英文字符串,需要统计每个英文字母出现的次数。原始做法用伪代码描述,如下: 冗长的switch-case虽然丑,但还能实现统计功能。假如,现在除了要统计字母,还要统计标点符号怎么办?恐怕没人会写switch-case了。 运用数组下标,可以极大简化这个问题。 还是这个字符串,现在要