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

数据结构里的逐点插入法是三角剖分是代数拓扑学里最基本的研究方法。二叉树是一树的一种，但应用比较多，二叉树的每个节点非常多只有两个子节点(但不一定非得要有两个节点)。

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

逐点插入法

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