void KDTree::buildKdTree(KDTree *tree, vector<vector<double>> data, unsigned int depth)
{
    //樣本的數(shù)量
    unsigned long samplesNum = data.size();
    //終止條件
    if (samplesNum == 0)
    {
        return;
    }
    if (samplesNum == 1)
    {
        tree->root = data[0];
        return;
    }
    //樣本的維度
    unsigned long k = data[0].size();//坐標(biāo)軸個(gè)數(shù)
    vector<vector<double> > transData = Transpose(data);
    //選擇切分屬性
    unsigned splitAttribute = depth % k;
    vector<double> splitAttributeValues = transData[splitAttribute];
    //選擇切分值
    double splitValue = findMiddleValue(splitAttributeValues);
    //cout << "splitValue" << splitValue  << endl;

    // 根據(jù)選定的切分屬性和切分值，將數(shù)據(jù)集分為兩個(gè)子集
    vector<vector<double> > subset1;
    vector<vector<double> > subset2;
    for (unsigned i = 0; i < samplesNum; ++i)
    {
        if (splitAttributeValues[i] == splitValue && tree->root.empty())
            tree->root = data[i];
        else
        {
            if (splitAttributeValues[i] < splitValue)
                subset1.push_back(data[i]);
            else
                subset2.push_back(data[i]);
        }
    }

    //子集遞歸調(diào)用buildKdTree函數(shù)
    tree->left_child = new KDTree;
    tree->left_child->parent = tree;
    tree->right_child = new KDTree;
    tree->right_child->parent = tree;
    buildKdTree(tree->left_child, subset1, depth + 1);
    buildKdTree(tree->right_child, subset2, depth + 1);
}

vector<double> KDTree::searchNearestNeighbor(vector<double> goal, KDTree *tree)
{
    /*第一步：在kd樹中找出包含目標(biāo)點(diǎn)的葉子結(jié)點(diǎn)：從根結(jié)點(diǎn)出發(fā)，
    遞歸的向下訪問kd樹，若目標(biāo)點(diǎn)的當(dāng)前維的坐標(biāo)小于切分點(diǎn)的
    坐標(biāo)，則移動(dòng)到左子結(jié)點(diǎn)，否則移動(dòng)到右子結(jié)點(diǎn)，直到子結(jié)點(diǎn)為
    葉結(jié)點(diǎn)為止,以此葉子結(jié)點(diǎn)為“當(dāng)前最近點(diǎn)”
    */
    unsigned long k = tree->root.size();//計(jì)算出數(shù)據(jù)的維數(shù)
    unsigned d = 0;//維度初始化為0，即從第1維開始
    KDTree* currentTree = tree;
    vector<double> currentNearest = currentTree->root;
    while(!currentTree->is_leaf())
    {
        unsigned index = d % k;//計(jì)算當(dāng)前維
        if (currentTree->right_child->is_empty() || goal[index] < currentNearest[index])
        {
            currentTree = currentTree->left_child;
        }
        else
        {
            currentTree = currentTree->right_child;
        }
        ++d;
    }
    currentNearest = currentTree->root;

    /*第二步：遞歸地向上回退， 在每個(gè)結(jié)點(diǎn)進(jìn)行如下操作：
    (a)如果該結(jié)點(diǎn)保存的實(shí)例比當(dāng)前最近點(diǎn)距離目標(biāo)點(diǎn)更近，則以該例點(diǎn)為“當(dāng)前最近點(diǎn)”
    (b)當(dāng)前最近點(diǎn)一定存在于某結(jié)點(diǎn)一個(gè)子結(jié)點(diǎn)對應(yīng)的區(qū)域，檢查該子結(jié)點(diǎn)的父結(jié)點(diǎn)的另
    一子結(jié)點(diǎn)對應(yīng)區(qū)域是否有更近的點(diǎn)（即檢查另一子結(jié)點(diǎn)對應(yīng)的區(qū)域是否與以目標(biāo)點(diǎn)為球
    心、以目標(biāo)點(diǎn)與“當(dāng)前最近點(diǎn)”間的距離為半徑的球體相交）；如果相交，可能在另一
    個(gè)子結(jié)點(diǎn)對應(yīng)的區(qū)域內(nèi)存在距目標(biāo)點(diǎn)更近的點(diǎn)，移動(dòng)到另一個(gè)子結(jié)點(diǎn)，接著遞歸進(jìn)行最
    近鄰搜索；如果不相交，向上回退*/

    //當(dāng)前最近鄰與目標(biāo)點(diǎn)的距離
    double currentDistance = measureDistance(goal, currentNearest, 0);

    //如果當(dāng)前子kd樹的根結(jié)點(diǎn)是其父結(jié)點(diǎn)的左孩子，則搜索其父結(jié)點(diǎn)的右孩子結(jié)點(diǎn)所代表
    //的區(qū)域，反之亦反
    KDTree* searchDistrict;
    if (currentTree->is_left())
    {
        if (currentTree->parent->right_child == nullptr)
            searchDistrict = currentTree;
        else
            searchDistrict = currentTree->parent->right_child;
    }
    else
    {
        searchDistrict = currentTree->parent->left_child;
    }

    //如果搜索區(qū)域?qū)?yīng)的子kd樹的根結(jié)點(diǎn)不是整個(gè)kd樹的根結(jié)點(diǎn)，繼續(xù)回退搜索
    while (searchDistrict->parent != nullptr)
    {
        //搜索區(qū)域與目標(biāo)點(diǎn)的最近距離
        double districtDistance = abs(goal[(d+1)%k] - searchDistrict->parent->root[(d+1)%k]);

        //如果“搜索區(qū)域與目標(biāo)點(diǎn)的最近距離”比“當(dāng)前最近鄰與目標(biāo)點(diǎn)的距離”短，表明搜索
        //區(qū)域內(nèi)可能存在距離目標(biāo)點(diǎn)更近的點(diǎn)
        if (districtDistance < currentDistance )//&& !searchDistrict->isEmpty()
        {

            double parentDistance = measureDistance(goal, searchDistrict->parent->root, 0);

            if (parentDistance < currentDistance)
            {
                currentDistance = parentDistance;
                currentTree = searchDistrict->parent;
                currentNearest = currentTree->root;
            }
            if (!searchDistrict->is_empty())
            {
                double rootDistance = measureDistance(goal, searchDistrict->root, 0);
                if (rootDistance < currentDistance)
                {
                    currentDistance = rootDistance;
                    currentTree = searchDistrict;
                    currentNearest = currentTree->root;
                }
            }
            if (searchDistrict->left_child != nullptr)
            {
                double leftDistance = measureDistance(goal, searchDistrict->left_child->root, 0);
                if (leftDistance < currentDistance)
                {
                    currentDistance = leftDistance;
                    currentTree = searchDistrict;
                    currentNearest = currentTree->root;
                }
            }
            if (searchDistrict->right_child != nullptr)
            {
                double rightDistance = measureDistance(goal, searchDistrict->right_child->root, 0);
                if (rightDistance < currentDistance)
                {
                    currentDistance = rightDistance;
                    currentTree = searchDistrict;
                    currentNearest = currentTree->root;
                }
            }
        }//end if

        if (searchDistrict->parent->parent != nullptr)
        {
            searchDistrict = searchDistrict->parent->is_left()?
                            searchDistrict->parent->parent->right_child:
                            searchDistrict->parent->parent->left_child;
        }
        else
        {
            searchDistrict = searchDistrict->parent;
        }
        ++d;
    }//end while
    return currentNearest;
}