408-数据结构

一.

数据 > 数据对象（某张表） > 数据元素 （某条记录）> 数据项（名字，性别）
逻辑结构 集合 线性 树 图
物理结构 顺序 链表 索引 散列
算法： 有穷 稳定 可行 输入 输出
时间复杂度：常对幂指阶

二.

栈的应用：

1. 表达式求值：

kmp 算法 算next 值 往右移动 nextvalue next 值和当前一样调用nextvalue 的next值

树

结点数 = 总度数 + 1 树的度（度的最大值） 度为m的树，第i层的结点数至多 = m^(i-1) 高度为h的m叉树至多有m^h - 1 / m -1 个结点

高度为h的m叉树至少有h个结点。 高度为h、度为m的树至少有h+m-1个结点

二叉树 n0 = n2 + 1

顺序存储 只适合存储 完全二叉树 2i 2i+1 左右孩子

层序遍历 通过辅助队列实现

前中 + 后中 + 层中 可确定 二叉树 其他不能确定