二叉树队列关系问题非递归算法的推导及形式化证明

该文对二叉树类问题进行分划,寻找其递推关系,并针对具有队列递推关系的一类问题,给出了其推导过程和形式化证明策略.再结合每个算法后置断言的不同,提出3种开发循环不变式的策略,并构造出该类问题的通用循环不变式模板.同时,发现该类问题是基于2个母算法的功能加以实现的,由此派生出3类问题.首先,对这3类派生问题进行推导,得到递推关系表达式和循环不变式,由此导出非递归Apla算法;然后,使用Dijkstra-Gries标准程序证明方法证明这些算法的正确性;最后,通过Apla到C++程序自动生成系统自动生成C++代码,实现了从抽象规约到具体的可执行程序的完整求精过程.