1树术语与递归分解
闭卷重建树术语与递归分解的ADT、表示不变量、操作与复杂度。
数据结构与抽象数据类型 · 小纸条
选一章打印。双面打印（按长边翻页）后沿虚线剪开，每张卡片正面题目、背面答案。
第 1 页 · 正面（题目）
2前中后序与迭代遍历
闭卷重建前中后序与迭代遍历的ADT、表示不变量、操作与复杂度。
3BST查找与有序不变量
闭卷重建BST查找与有序不变量的ADT、表示不变量、操作与复杂度。
4BST插入、删除与后继
闭卷重建BST插入、删除与后继的ADT、表示不变量、操作与复杂度。
5高度退化与平衡目标
闭卷重建高度退化与平衡目标的ADT、表示不变量、操作与复杂度。
6AVL旋转与高度维护
闭卷重建AVL旋转与高度维护的ADT、表示不变量、操作与复杂度。
7实验：BST/AVL不变量检查器
闭卷重建实验：BST/AVL不变量检查器的ADT、表示不变量、操作与复杂度。
第 1 页 · 背面（答案）
机制：遍历顺序取决于访问根与子树的相对时刻，显式栈可保存递归返回点；实验：对同一二叉树输出三种遍历并与迭代版本对比；边界：只把递归调用换while不保存阶段，会丢失中序/后序返回位置。
机制：根、父子、深度、高度和子树定义递归结构，节点数与边数在非空树满足E=V-1；实验：计算给定父数组的深度、高度与叶子数；边界：深度从根向下、高度从节点向叶，两者方向相反且空树定义需声明。
机制：删除叶、单子和双子节点分别处理；双子可用后继替换再删除后继原位置；实验：逐例删除根、叶和双子节点并检查父指针/大小；边界：复制后继键时值/计数也要同步，结构版移植节点又需维护所有链接。
机制：每节点左子树键小、右子树键大或按明确重复策略处理，查找每步排除一整棵子树；实验：插入序列后逐路径查找并用中序验证有序；边界：局部只比较父子不足以验证BST，左子树所有键都必须受祖先上界约束。
机制：AVL要求每节点左右高度差至多1，单/双旋在保持中序序列下恢复局部平衡；实验：对LL、RR、LR、RL四种失衡逐指针旋转并重算高度；边界：先后更新高度顺序错误会让祖先平衡因子继续错误，旋转还要接回原父节点。
机制：随机或有序插入会产生不同高度，搜索成本与根到节点路径长度相关；实验：比较有序、随机和中位优先插入后的树高；边界：BST平均快不能替代最坏保证；递归处理链状树也可能栈溢出。
机制：实现BST范围验证、高度计算、平衡因子检查和四类旋转；实验：覆盖空树、重复策略、深层祖先违规和四种失衡测试；边界：只比较中序是否排序会漏结构高度与父指针错误。