一、數據結構里的逐點插入法、排序二叉樹
逐點插入法
三角剖分是一種研究方法。三角剖分≠TIN
三角剖分是代數拓撲學里最基本的研究方法。 以曲面為例, 我們把曲面剖開成一塊塊碎片,要求滿足下面條件: (1)每塊碎片都是曲邊三角形; (2)曲面上任何兩個這樣的曲邊三角形,要么不相交,要么恰好相交于一條公共邊(不能同時交兩條或兩條以上的邊)。
而**TIN**是:不規則三角網,當在建立TIN的時候,用到三角剖分的方法。
假設V是二維實數域上的有限點集,邊e是由點集中的點作為端點構成的封閉線段, E為e的集合。那么該點集V的一個三角剖分T=(V,E)是一個平面圖G,該平面圖滿足條件:
1.除了端點,平面圖中的邊不包含點集中的任何點。
2.沒有相交邊。
3.平面圖中所有的面都是三角面,且所有三角面的合集是散點集V的凸包。
逐點插入法算法思想
1、首先,對于樣本中的點集進行排序,在這里以x坐標從小到大進行排序(也可以按照y坐標)。放入數組_vertices中。
2、然后,需要構造出一個超級三角形,超級三角形要能夠將樣本中的點全都包含在其內(不能再其邊上)。并將超級三角形存入 三角形列表_triangles中。并將超級三角形的三邊存入polygon(是用來存儲臨時新產生的邊)中。
3、然后開始對_vertices中的點進行遍歷,如果該點在_triangles中三角形的外接圓內(在圓上也相當于在圓內)時,則需要將這些三角形從列表中刪除,然后將當前點連接剛剛刪除的三角形的三個頂點,從而形成三個新的三角形,并將這三個新三角形加入列表_triangles中。
4、當對樣本點集中的點遍歷完之后,還需要將第二步中所構造的超級三角形刪除(因為超級三角形的三個頂點不屬于樣本點集中的點)。最終形成的列表triangles就是三角剖分的三角網了。
排序二叉樹
二叉樹是一樹的一種,但應用比較多,所以需要深入學習,二叉樹的每個節點非常多只有兩個子節點(但不一定非得要有兩個節點)。
二叉樹與度為2的樹的區別:
1、度為2的的樹必須有三個節點以上(否則就不叫度為二了,一定要先存在),二叉樹可以為空。
2、二叉樹的度不一定為2,比如斜樹。
3、二叉樹有左右節點區分,而度為2的樹沒有左右節點的區分。
延伸閱讀:
二、二叉樹性質
1、二叉樹有用樹的性質
2、非空二叉樹葉子節點數=度為2的節點數+1.本來一個節點如果度為1.那么一直延續就一個葉子,但如果出現一個度為2除了延續原來的一個節點,會多出一個節點需要維系。所以到最后會多出一個葉子。
3、非空第i層非常多有2^(i-1)個節點。
4、高為h的樹非常多有(2^h)-1個節點(等比求和)。