软件测试是软件工程学科的重要组成部分,在实际的软件开发过程中,软件测试所发挥的重要作用已得到软件开发人员的广泛认同。软件测试以发现软件中潜藏的缺陷和错误为目的,确保软件的可靠性和提高软件的质量。测试数据自动生成是软件测试中的一个重要环节,目前关于测试数据生成的研究主要集中于数值和字符串类型的数据,对于指针和动态数据结构类型的测试数据生成研究较少。而且,现有的解决动态数据结构类型输入数据的测试生成方法大多采用静态方法,这对于复杂动态数据结构的测试数据生成实现困难,并且测试生成效率较低。二叉树是一种广泛使用并且具有代表性的动态数据结构,为此,本课题针对二叉树结构,以路径覆盖为测试准则,提出了一种基于concolic的二叉树结构型测试数据自动生成方法,使用遗传搜索算法生成二叉树结构的形态,并利用约束求解确定其数据域的值。针对二叉树结构型测试数据的特点,设计了一种新的染色体编码方式,用以表示二叉树结构的形态,探讨了适用于二叉树结构的交叉操作和变异操作。同时,通过约束解决技术求解其数据域的值,实现面向路径的二叉树结构型测试数据自动生成方法。为验证本课题提出的二叉树结构型测试数据自动生成方法的可行性,选取二叉树操作程序进行大量实验。实验结果表明,基于遗传算法的二叉树形态测试生成方法是行之有效的,不仅能够实现以二叉树结构类型为输入的面向路径的测试数据自动生成,而且其测试生成效果明显优于随机生成方法。