Non-recursive Algorithm Derivation and Formal Proof of Binary Tree Traversal Class Problems
Zhengkang Zuo, Yue Fang, Qing Yun Huang, Yunyan Liao, Yuan Wang, Changjing Wang · 2020
The development of loop invariants for recursive problems of nonlinear data structures is always difficult problem in formal development. The paper studies the derivation and formal proof of binary tree traversal class non-recursive algorithm. The non-recursive Apla (Abstract Programming Language) algorithms of binary tree traversal class problems and their exact and simple loop invariants are derived. Then, the correctness of the algorithm is proved by Dijkstra-Gries standard proving technique. Finally, the PAR platform is used to automatically generate C++ code, which realizes the complete refinement process from abstract specification to concrete executable program. The results of this study point out the direction for the exploration of the loop invariant of the nonrecursive algorithm for recursive problems and have guiding significance for the derivation and formal proof of the algorithm program of the nonlinear data structure.