clear;
close?all;
clc;
%?生成數據
data?=?[2?3;
????5?4;
????9?6;
????4?7;
????8?1;
????7?2];
%?給數據標號
for?i?=?1:?size（data1）
????data（i3）?=?i;
end
%?建立Kd樹
Kd_tree?=?Kd_tree_create（data）;
%?利用Kd樹進行kNN查詢
closest?=?Kd_tree_search_knn（Kd_tree?[63.1]?2）;

%%?使用data建立Kd樹
function?[tree]?=?Kd_tree_create（data）
%?生成Kd樹，每次分割以方差最大的維度進行分割
[num?dimension]?=?size（data）;
dimension?=?dimension?-?1;
for?i?=?1:?dimension
????data_var（i）?=?var（data（:i））;
end
[~?choose_dim]?=?max（data_var）;
data?=?sortrows（data?choose_dim）;
tree.id?=?data（round（num/2）end）;
tree.node?=?data（round（num/2）1:end-1）;
tree.dim?=?choose_dim;
tree.parent?=?[];
tree.left?=?[];
tree.right?=?[];

%?遞歸生成左右子樹
lefttree?=?[];
righttree?=?[];
if?round（num/2）?>?1
????leftdata?=?data（1:（round（num/2）-1）?:）;
????lefttree?=?Kd_tree_create（leftdata）;
????for?i?=?1:?size（lefttree?1）
????????if?isempty（lefttree（i）.parent）
????????????lefttree（i）.parent?=?tree.id;
????????????tree.left?=?lefttree（i）.id;
????????end
????end
end
if?round（num/2）?????rightdata?=?data（（round（num/2）+1）:end?:）;
????righttree?=?Kd_tree_create（rightdata）;
????for?i?=?1:?size（righttree?1）
????????if?isempty（righttree（i）.parent）
????????????righttree（i）.parent?=?tree.id;
????????????tree.right?=?righttree（i）.id;
????????end
????end
end
tree?=?[tree;?lefttree];
tree?=?[tree;?righttree];
end


%%?利用Kd樹進行kNN查詢
function?[closest_point]?=?Kd_tree_search_knn（Kd_tree?data?n）
%?從根節點開始一直查詢到葉節點，找到和data在一個區域的葉節點
closest?=?Kd_tree（1）;
while（1）
????if?closest.node（closest.dim）?>=?data（closest.dim）?&&?~isempty（closest.left）
????????closest?=?Kd_tree（find（[Kd_tree.id]==closest.left））;
????elseif?closest.node（closest.dim）?<=?data（closest.dim）?&&?~isempty（closest.right）
????????closest?=?Kd_tree（find（[Kd_tree.id]==closest.right））;
????else
????????break
????end
end

Kd_tree（find（[Kd_tree.id]==closest.id））.done?=?1;
closest_point?=?closest.node;
[max_dis?max_idx]?=?max（sum（（closest_point?-?data）.^2?2））;
max_dis?=?max_dis（1）;
max_idx?=?max_idx（1）;

%?從當前節點向上回溯
node_now?=?closest;
while（1）
????%?回溯