---
pubDatetime: 2024-07-23 11:31:25
title: 408-数据结构
slug: 408-数据结构
tags:
- "考研"
---

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


# 二.
栈的应用：
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 左右孩子

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

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