kd树的创建及搜索 matlab实现

matlab实现kd树的创建和配套的搜索程序，注释详细，还附有算法思路讲解。欢迎下载

function [node] = cut_by_r（XrcurrentNode）
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% 根据第r维对X进行切分获得节点
% X：数据点集
% r：切分维度
% node：结构体
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Node_template = struct（...
    ‘isRoot‘0...      是否是根节点，0不是，1是
    ‘isLeaf‘0...      是否是叶子节点
    ‘isLeft‘0...      是否是左孩子
    ‘isRight‘0...     是否是右孩子 用于搜索时找兄弟结点
    ‘hasLeft‘0...     是否有左孩子
    ‘hasRight‘0...    是否有右孩子
    ‘parent‘-1...     父亲结点，用于搜索时回溯
    ‘val‘-1...        切分点坐标
    ‘left‘-1...       左节点（依然是结构体）
    ‘right‘-1...      右节点
    ‘leftSet‘-1...    分到右边的点集（矩阵）-1表示空集
    ‘rightSet‘-1...   分到左边的点集（矩阵），-1表示空集 
    ‘r‘-1...          切分维度）;
    ‘visited‘0....     搜索时是否访问标志），0为未访问，1为访问过
    ‘index‘-1 ...      下标
    ）;                  %节点结构体模板

dim = size（X1）-1;    %数据点的维度
num = size（X2）;    %数据集点数
node = currentNode;
node.r = r;
if num == 1
    %数据集中只有一个点
    node.val = X（1:dim1）;
    node.isLeaf = 1;
    node.index = X（dim+1:）;
else
    X_sorted = sort_by_r（Xr）;
    mid = ceil（num/2）;
    node.val = X_sorted（1:dimmid）;
    node.index = X_sorted（dim+1mid）;
    if mid>1
        node.leftSet = X_sorted（:1:ceil（num/2）-1）;
    end
    if mid        node.rightSet = X_sorted（:ceil（num/2）+1:end）;
    end
end
r = mod（rdim）+1;
if node.leftSet ~= -1
    node.hasLeft = 1;
    node.left = Node_template;
    node.left.parent = node;
    node.left.isLeft = 1;
    node.left = cut_by_r（node.leftSetrnode.left）;
end
if node.rightSet ~= -1
    node.hasRight = 1;
    node.right = Node_template;
    node.right.parent = node;
    node.right.isRight = 1;
    node.right = cut_by_r（node.rightSetrnode.right）;
end

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件         28  2018-08-08 14:35  kdTree\.git\COMMIT_EDITMSG

     文件        298  2018-08-06 21:28  kdTree\.git\config

     文件         73  2018-08-06 21:28  kdTree\.git\description

     文件         23  2018-08-06 21:28  kdTree\.git\HEAD

     文件        478  2018-08-06 21:28  kdTree\.git\hooks\applypatch-msg.sample

     文件        896  2018-08-06 21:28  kdTree\.git\hooks\commit-msg.sample

     文件       3327  2018-08-06 21:28  kdTree\.git\hooks\fsmonitor-watchman.sample

     文件        189  2018-08-06 21:28  kdTree\.git\hooks\post-update.sample

     文件        424  2018-08-06 21:28  kdTree\.git\hooks\pre-applypatch.sample

     文件       1642  2018-08-06 21:28  kdTree\.git\hooks\pre-commit.sample

     文件       1348  2018-08-06 21:28  kdTree\.git\hooks\pre-push.sample

     文件       4898  2018-08-06 21:28  kdTree\.git\hooks\pre-rebase.sample

     文件        544  2018-08-06 21:28  kdTree\.git\hooks\pre-receive.sample

     文件       1492  2018-08-06 21:28  kdTree\.git\hooks\prepare-commit-msg.sample

     文件       3610  2018-08-06 21:28  kdTree\.git\hooks\update.sample

     文件        689  2018-08-08 14:35  kdTree\.git\index

     文件        240  2018-08-06 21:28  kdTree\.git\info\exclude

     文件        498  2018-08-08 14:35  kdTree\.git\logs\HEAD

     文件        498  2018-08-08 14:35  kdTree\.git\logs\refs\heads\master

     文件        174  2018-08-06 21:28  kdTree\.git\logs\refs\remotes\origin\HEAD

     文件        282  2018-08-08 14:36  kdTree\.git\logs\refs\remotes\origin\master

     文件        191  2018-08-08 14:35  kdTree\.git\objects\07\34e26a1c221516a829fd27013c83152fa9d676

     文件        509  2018-08-06 21:28  kdTree\.git\objects\0a\42d1775bd0826ecd725160b18d9d2b6c965c59

     文件        255  2018-08-08 14:35  kdTree\.git\objects\0b\43ec2ba421b51ef85591b95feb88670dbc0981

     文件        252  2018-08-06 21:33  kdTree\.git\objects\1d\35ea9d23f4889213b948434585ac47b58fdbcd

     文件        277  2018-08-08 14:35  kdTree\.git\objects\21\d5a4ce991c7c4d633793107ddd1469461e7f71

     文件         54  2018-08-06 21:28  kdTree\.git\objects\3a\19e3c40d319060988ac3018bc62285f847a58c

     文件         79  2018-08-06 21:28  kdTree\.git\objects\4d\2cec4e8ca99a9848297069918fe11ebc9927cc

     文件        212  2018-08-06 21:33  kdTree\.git\objects\55\5bab3fd4d4549376d4b668ca61bd1c972fb33d

     文件        727  2018-08-06 21:33  kdTree\.git\objects\57\9fe9102074cf76ea130cdd2ee2951b8858591c

............此处省略66个文件信息