三角剖分(二叉树)的对角线翻转(旋转)能够实现两三角剖分(二叉树)间的转化,三角剖分(二叉树)间的对角线翻转(旋转)距离是指从一三角剖分(二叉树)通过对角线翻转(旋转)转化为另一三角剖分(二叉树)所需的最少对角线翻转(旋转)数目.凸多边形三角剖分与二叉树之间存在着一一对应的关系,凸多边形三角剖分间的对角线翻转距离和与其对应的二叉树间的旋转距离是等价的,从而可以从三角剖分的角度来研究二叉树间的旋转距离.二叉树是算法设计与分析中经常用到的一种数据结构,在二叉树的算法分析中,常常需要讨论具有某些特点的二叉树的平均性能,因此需要实现二叉树的枚举,对于二叉树枚举的研究,无论在算法理论上还是在实际应用中都具有重要的意义.本文首先通过对凸多边形三类特殊形态的三角剖分的研究,求得了三类三角剖分间对角线翻转距离的精确值,给出了三类三角剖分问的对角线翻转距离算法,并且根据二叉树与三角剖分间的对应关系得出了与三类三角剖分相对应的二叉树间的旋转距离.其次,本文给出了二叉树枚举的两种算法.其一是根据二叉树与三角剖分间的对应关系,通过实现凸多边形三角剖分的枚举来实现二叉树的枚举生成;其二是通过二叉树的一种特殊旋转(左臂右旋转)来实现二叉树的枚举生成.最后,就本文所做的主要工作进行了总结并进行了展望.