二叉树、算法
- 一、树
- 结点（Node）
- 树由一系列的结点组成，每个结点可以包含数据和指向其他结点的链接。
- 结点通常包含一个数据元素和若干指向其他结点的指针
- 根结点（Root）
- 树的顶部结点称为根结点，它是树中没有父结点的唯一结点
- 子结点（Child）
- 一个结点的子结点是指由该节点直接指向的结点
- 叶结点（Leaf）
- 没有子结点的结点称为叶结点或终端结点
- 深度（Depth）
- 结点的深度是从根结点到该结点的路径上的边数。
- （广）度
- 最大的结点的度
- 树的存储：顺序结构、链式结构
- 结点（Node）
- 二、二叉树，binary tree
- n个结点的有限集合，集合要么为空树，要么由一个根结点和两棵互不相交，分别称谓根结点的左子树和右子树的二叉树组成
- 特点
- 每个结点最多两个子树。
- 左子树和右子树是有顺序的，次序不能颠倒
- 如果某个结点只有一个子树，也要区分左，右子树
- 特殊的二叉树
- 斜树，所有的结点都只有左子树，左斜树，所有结点都只有右子树，右斜树
- 满二叉树，所有的分支结点都存在左右子树，并且叶结点都在同一层上
- 完全二叉树，对于一颗有n个结点的二叉树按层序编号，如果编号i（1<=i<=n）的结点于同样深度的满二叉树中编号为i的结点在二叉树中位置完全相同，则这可树为完全二叉树
- 斜树，所有的结点都只有左子树，左斜树，所有结点都只有右子树，右斜树
- 特性
- 在二叉树的第i层上最多有2^(i-1)个结点i>=1
- 深度为k的二叉树至多有2^k -1 个结点 k>=1
- 任意一个二叉树T，如果其叶子结点的个数是n0,度数为2的结点数为n2，n0 = n2 +1;
- 有n个结点的完全二叉树深度为(log n/log 2) +1（向下取整）;
- 层序
- 前序，根左右，先访问根，然访问左，访问右
- 中序，左根右，先从根开始（不是先访问根），从左开始访问，再访问根，再访问右结点
- 后序，左右根，先从根开始（不是先访问根），先访问左，再访问右，再访问根
- 三、算法
- 算法即解决特定问题求解步骤
- 算法的设计
- 正确性
- 语法正确
- 合法的输入得到合理的结果
- 对非法的输入，给出满足要求的规格说明
- 对精心选择，甚至刁难的测试都能正常运行，结果正确
- 可读性
- 便于交流，阅读，理解 高内聚，低耦合
- 健壮性
- 输入非法内容，能进行相应的处理，而不是产生异常
- 高效率（时间复杂度）
- 算法时间复杂度：
- 执行这个算法所花时间的度量
- 将数据量增长和时间增长用函数表示出来，这个函数就叫做时间复杂度
- 一般用大0表示法：0(n)------>时间复杂度是关于数据n的一个函数
- 随着n的增加，时间复杂度增长较慢的算法时间复杂度低
- 时间复杂度的计算规则
- 用常数1 取代运行时间中的所有加法常数
- 在修改后的运行函数中，只保留最高阶项
- 如果最高阶存在且系数不是1，则去除这个项相乘的常数
- 常用的时间复杂度所耗的时间
- 算法时间复杂度：
- 低存储（空间复杂度）
- 空间复杂度越低：低存储 越高：高存储
- 时间复杂度越低：高效率 越高：低效率
- 正确性
