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

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

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