一、數(shù)據(jù)結(jié)構(gòu)里的逐點(diǎn)插入法、排序二叉樹

逐點(diǎn)插入法

三角剖分是一種研究方法。三角剖分≠TIN

三角剖分是代數(shù)拓?fù)鋵W(xué)里最基本的研究方法。 以曲面為例， 我們把曲面剖開成一塊塊碎片，要求滿足下面條件： （1）每塊碎片都是曲邊三角形； （2）曲面上任何兩個(gè)這樣的曲邊三角形，要么不相交，要么恰好相交于一條公共邊（不能同時(shí)交兩條或兩條以上的邊)。

而**TIN**是：不規(guī)則三角網(wǎng)，當(dāng)在建立TIN的時(shí)候，用到三角剖分的方法。

假設(shè)V是二維實(shí)數(shù)域上的有限點(diǎn)集，邊e是由點(diǎn)集中的點(diǎn)作為端點(diǎn)構(gòu)成的封閉線段, E為e的集合。那么該點(diǎn)集V的一個(gè)三角剖分T=(V,E)是一個(gè)平面圖G，該平面圖滿足條件：

1.除了端點(diǎn)，平面圖中的邊不包含點(diǎn)集中的任何點(diǎn)。

2.沒(méi)有相交邊。

3.平面圖中所有的面都是三角面，且所有三角面的合集是散點(diǎn)集V的凸包。

逐點(diǎn)插入法算法思想

1、首先，對(duì)于樣本中的點(diǎn)集進(jìn)行排序，在這里以x坐標(biāo)從小到大進(jìn)行排序（也可以按照y坐標(biāo)）。放入數(shù)組_vertices中。

2、然后，需要構(gòu)造出一個(gè)超級(jí)三角形，超級(jí)三角形要能夠?qū)颖局械狞c(diǎn)全都包含在其內(nèi)（不能再其邊上）。并將超級(jí)三角形存入 三角形列表_triangles中。并將超級(jí)三角形的三邊存入polygon（是用來(lái)存儲(chǔ)臨時(shí)新產(chǎn)生的邊）中。

3、然后開始對(duì)_vertices中的點(diǎn)進(jìn)行遍歷，如果該點(diǎn)在_triangles中三角形的外接圓內(nèi)（在圓上也相當(dāng)于在圓內(nèi)）時(shí)，則需要將這些三角形從列表中刪除，然后將當(dāng)前點(diǎn)連接剛剛刪除的三角形的三個(gè)頂點(diǎn)，從而形成三個(gè)新的三角形，并將這三個(gè)新三角形加入列表_triangles中。

4、當(dāng)對(duì)樣本點(diǎn)集中的點(diǎn)遍歷完之后，還需要將第二步中所構(gòu)造的超級(jí)三角形刪除（因?yàn)槌?jí)三角形的三個(gè)頂點(diǎn)不屬于樣本點(diǎn)集中的點(diǎn)）。最終形成的列表triangles就是三角剖分的三角網(wǎng)了。

排序二叉樹

二叉樹是一樹的一種，但應(yīng)用比較多，所以需要深入學(xué)習(xí)，二叉樹的每個(gè)節(jié)點(diǎn)非常多只有兩個(gè)子節(jié)點(diǎn)(但不一定非得要有兩個(gè)節(jié)點(diǎn))。

二叉樹與度為2的樹的區(qū)別：
1、度為2的的樹必須有三個(gè)節(jié)點(diǎn)以上(否則就不叫度為二了，一定要先存在)，二叉樹可以為空。
2、二叉樹的度不一定為2,比如斜樹。
3、二叉樹有左右節(jié)點(diǎn)區(qū)分，而度為2的樹沒(méi)有左右節(jié)點(diǎn)的區(qū)分。

延伸閱讀：

二、二叉樹性質(zhì)

1、二叉樹有用樹的性質(zhì)

2、非空二叉樹葉子節(jié)點(diǎn)數(shù)=度為2的節(jié)點(diǎn)數(shù)+1.本來(lái)一個(gè)節(jié)點(diǎn)如果度為1.那么一直延續(xù)就一個(gè)葉子，但如果出現(xiàn)一個(gè)度為2除了延續(xù)原來(lái)的一個(gè)節(jié)點(diǎn)，會(huì)多出一個(gè)節(jié)點(diǎn)需要維系。所以到最后會(huì)多出一個(gè)葉子。

3、非空第i層非常多有2^(i-1)個(gè)節(jié)點(diǎn)。

4、高為h的樹非常多有(2^h)-1個(gè)節(jié)點(diǎn)(等比求和)。