ツリーデータの検索方法---javascript

説明
このような問題があると仮定します.次のようなデータ構造のデータをください.id=01001002のtextの値を求めます.

var tree = [{
    id: '01000000',
    text: '  ',
    children: [{
        id: '01001000',
        text: '   ',
        children: [
            {
                id: '01001001',
                text: '   ',
                children: null
            },{
                id: 12,
                text: '   ',
                children: null
            }
        ]
    }]
},{
    id: '02000000',
    text: '  ',
    children: [{
        id: '02001000',
        text: '   ',
        children: [{
            id: '02001001',
            text: '   ',
            children: null
        }]
    }]
}];

これは明白な多叉樹の樹形構造であり、一般的にこの樹形構造には深さ優先エルゴードと広さ優先エルゴードが採用される.
深さ優先巡回
深さ優先エルゴードの原則は、頂点から始まります.2.現在のノードにサブノードがある場合、現在のノードのすべてのサブノードを巡回する.

//     
function deepSearch(tree){
    for(var i = 0; iif(tree[i].children && tree[i].children.length>0) {
            deepSearch(tree[i].children);
        }
    }
}

//    
function deepSearch(tree) {
    var stark = [];

    stark = stark.concat(tree);

    while(stark.length) {
        var temp = stark.shift();
        if(temp.children) {
            //          ，             
            stark = temp.children.concat(stark);
        }
        console.log(temp);
    }
}

私たちの問題に戻ります.次の2つの解法を提供します.

//   
function deepQuery(tree,id) {
    var isGet = false;
    var retNode = null;
    function deepSearch(tree,id){
        for(var i = 0; iif(tree[i].children && tree[i].children.length>0) {
                deepSearch(tree[i].children,id);
            }
            if(id === tree[i].id || isGet) {
                isGet||(retNode = tree[i]);
                isGet = true;
                break;
            }
        }
    }
    deepSearch(tree,id);
    return retNode;
}

//    
function deepQuery(tree, id){
    var stark = [];

    stark = stark.concat(tree);

    while(stark.length) {
        var temp = stark.shift();
        if(temp.children) {
            stark = temp.children.concat(stark);
        }
        if(id === temp.id) {
            return temp;
        }
    }
}

再帰は適時に循環を飛び出すことができません.だから外で一つのマークを定義します.検索したい結果が見つかったかどうかを表しています.見つけたら、その後の循環から跳び出します.再帰しないで直接結果を見つけたらリターンすればいいです.
広さ優先巡回
広度優先エルゴードの原則は、ルートノードから開始することである.2.すべてのサブノードを巡回します.3.第1のサブノードから、広さ優先巡回を再実行する.コードは以下の通りです

function breadthSearch(tree) {
    var stark = [];

    stark = stark.concat(tree);

    while(stark.length) {
        var temp = stark.shift();
        if(temp.children) {
            stark = stark.concat(temp.children);
        }
        console.log(temp);
    }
}

私たちの問題に対する解決法:

function breadthQuery(tree, id) {
    var stark = [];

    stark = stark.concat(tree);

    while(stark.length) {
        var temp = stark.shift();
        if(temp.children) {
            stark = stark.concat(temp.children);
        }
        if(temp.id === id) {
            return temp;
        }
    }
}

IDの特徴を利用して処理します.
データに規則がない場合、私たちは通常遍歴方式で私たちが欲しいデータを検索するしかないです.しかし、仮に私たちのデータにはこのような特徴があるとします.1.idは8桁の数字で構成されています.2.1-2位は省を表す.3-5位は市を表します.4.6-8位は県を表します.5.デフォルトは0で代替して、たとえば北京の省レベルのidは1で、北京のこの省レベルの地区のidは01000000です.この時に私達に1つのidをあげて、私達は急速に彼のそれぞれの階層のidを獲得することができて、急速に位置を測定しやすいです.この方法は、階層的に固定された、かつ、IDに一定の規則があるデータにのみ適用される.