目录 算法与生活联系 研究算法和数据结构的意义 算法与生活联系 驾驶汽车 驾驶员不清楚汽车内部的物理机制,只知道实现驾驶(功能)的逻辑,这称为接口 Interface 汽车修理工清楚汽车内部的物理机制,这称为实现Implementation 总结(两对相对概念) 逻辑与接口(抽象) 机制与实现(具体) 研究算法和数据结构的意义 解决问题的整体感 控制问题复杂度,利用抽象保持“整体感” 不陷入过多的细节 与算法相联系的数据保持一致性 数据抽象:ADT(Abstract Data Type) 对数据处理的逻辑描述,不涉…

2021年3月25日 0条评论 22点热度 阅读全文

一、什么是平衡二叉树? 平衡二叉树: 又称为AVL树 ,它或者是一棵空树,或者是具备以下性质的二叉排序树: 每棵子树中的左子树和右子树的深度差(平衡因子)的绝对值不能超过1; 二叉树中每棵子树都要求是平衡二叉树; 一棵AVL树必须满足以下条件: 条件一:必须是二叉排序树 条件二:每个节点的左子树和右子树的高度差的绝对值至多为1。 也就是说,平衡二叉树的前提是它是一棵二叉排序树 平衡二叉树的查找、插入、删除操作在平均和最坏的情况下都是O(logn),这得益于它时刻维护着二叉树的平衡。 二、平衡二叉树的相关概念 平衡因…

2020年6月19日 0条评论 9点热度 阅读全文

一、什么是平衡二叉树? 平衡二叉树: 又称为AVL树 ,它或者是一棵空树,或者是具备以下性质的二叉排序树: 每棵子树中的左子树和右子树的深度差(平衡因子)的绝对值不能超过1; 二叉树中每棵子树都要求是平衡二叉树; 一棵AVL树必须满足以下条件: 条件一:必须是二叉排序树 条件二:每个节点的左子树和右子树的高度差的绝对值至多为1。 也就是说,平衡二叉树的前提是它是一棵二叉排序树 平衡二叉树的查找、插入、删除操作在平均和最坏的情况下都是O(logn),这得益于它时刻维护着二叉树的平衡。 二、平衡二叉树的相关概念 平衡因…

2020年6月19日 0条评论 19点热度 阅读全文

设一颗完全二叉树共有1699个结点,则该二叉树中叶子结点数(度为0)为? 解析: 在二叉树中有关系:度为0的结点个数 = 度为2的结点个数 + 1,表示为:n0 = n2 +1; 因为度为1的结点只可能出现在最后一个结点,或者根本就不存在度为1的结点。 假设:存在度为1的结点; n0 + n2 + 1 = 1699,解其可得,n0 与 n2 都不为整数,这与事实不符,所以可以得出,不存在度数为1的点(虽然计算得出是的确不存在,但并不是一定不存在) 所以可得度为1的结点是不存在的; 即:n0 + n2 = 1699,…

2017年2月12日 0条评论 9点热度 阅读全文

题目:一颗完全二叉树第六层有8个叶结点(根为第一层),则结点个数最多有()个。 二叉树第k层最多有 2^(k-1) 个节点 第六层最多有32个节点 第五层最多有16个节点 第四层最多有8个节点 第三层最多有4个节点 第二层最多有2个节点  第一层最多有1个节点 完全二叉树的叶节点只可能出现在后两层 如果完全二叉树有6层,则前5层是满二叉树,总节点数目为16+8+4+2+1+8=39 如果完全二叉树有7层,则前6层是满二叉树, 前六层总节点数目为32+16+8+4+2+1=63 第六层有8个叶子节点,则有3…

2017年2月12日 0条评论 8点热度 阅读全文