本文共 356 字，大约阅读时间需要 1 分钟。

7最邻近问题之二叉树

一、前言：K-NN、NN

K-NN：找K个离自己最近的点 NN:以这一点做圆心，r为半径，邻域内的点都是最近点。 寻找点云临近点困难原因： 1、点云不规则 2、点云是三维的 3、点云数据量大 核心思想：空间分割。

二、 二叉树：

左边的数小于根节点小于右边的数。如图： 给定一个一维数组，构建二叉树： 小的放左边，大的放右边。 代码: 复杂度： O(log2n)-O(n) 递归方法： 循环方法： 栈： 复杂度：O（h） 三种顺序的遍历： 中序：排序 前序：复制树 后序：删除节点 输入一个点：11，找它的最近点：

BST-knn:

代码：

Radius NN:

没有最坏距离，不能为0，已经固定，半径内的点都是最邻近点。

复杂度：O（logn）-O(n) 原始的二叉树不适宜于二维、三维。

转载地址：http://xcexi.baihongyu.com/