数据结构里的逐点插入法、排序二叉树是什么?

一、数据结构里的逐点插入法、排序二叉树

逐点插入法

三角剖分是一种研究方法。三角剖分≠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个节点(等比求和)。