凸多邊形三角剖分的對角線翻轉(zhuǎn)與二叉樹的旋轉(zhuǎn).pdf

1、三角剖分(二叉樹)的對角線翻轉(zhuǎn)(旋轉(zhuǎn))能夠?qū)崿F(xiàn)兩三角剖分(二叉樹)間的轉(zhuǎn)化，三角剖分(二叉樹)間的對角線翻轉(zhuǎn)(旋轉(zhuǎn))距離是指從一三角剖分(二叉樹)通過對角線翻轉(zhuǎn)(旋轉(zhuǎn))轉(zhuǎn)化為另一三角剖分(二叉樹)所需的最少對角線翻轉(zhuǎn)(旋轉(zhuǎn))數(shù)目.凸多邊形三角剖分與二叉樹之間存在著一一對應的關(guān)系，凸多邊形三角剖分間的對角線翻轉(zhuǎn)距離和與其對應的二叉樹間的旋轉(zhuǎn)距離是等價的，從而可以從三角剖分的角度來研究二叉樹間的旋轉(zhuǎn)距離. 二叉樹是算法設計與分析中經(jīng)

2、常用到的一種數(shù)據(jù)結(jié)構(gòu)，在二叉樹的算法分析中，常常需要討論具有某些特點的二叉樹的平均性能，因此需要實現(xiàn)二叉樹的枚舉，對于二叉樹枚舉的研究，無論在算法理論上還是在實際應用中都具有重要的意義. 本文首先通過對凸多邊形三類特殊形態(tài)的三角剖分的研究，求得了三類三角剖分間對角線翻轉(zhuǎn)距離的精確值，給出了三類三角剖分間的對角線翻轉(zhuǎn)距離算法，并且根據(jù)二叉樹與三角剖分間的對應關(guān)系得出了與三類三角剖分相對應的二叉樹間的旋轉(zhuǎn)距離. 其次，本文給