js 二叉树遍历

2018-06-24 02:16:01来源：未知阅读 ()

二叉树定义这里不再赘述。

我这里有个二叉树：

var tree = {
    "id": 0,
    "name": "root",
    "left": {
        "id": 1,
        "name": "Simon",
        "left": {
            "id": 3,
            "name": "Carl",
            "left": {
                "id": 7,
                "name": "Lee",
                "left": {
                    "id": 11,
                    "name": "Fate"
                }
            },
            "right": {
                "id": 8,
                "name": "Annie",
                "left": {
                    "id": 12,
                    "name": "Saber"
                }
            }
        },
        "right": {
            "id": 4,
            "name": "Tony",
            "left": {
                "id": 9,
                "name": "Candy"
            }
        }
    },
    "right": {
        "id": 2,
        "name": "right",
        "left": {
            "id": 5,
            "name": "Carl",
        },
        "right": {
            "id": 6,
            "name": "Carl",
            "right": {
                "id": 10,
                "name": "Kai"
            }
        }
    }
};

1.使用前序遍历，并将所有name输出。

function getListWithDLR(node) {
    if(node){
        console.log(node.name);
        getListWithDLR(node.left);
        getListWithDLR(node.right);
    }
}
getListWithDLR(tree); //调用函数，并把二叉树传进去。

2.使用中序遍历，并将所有name输出。

function getListWithLDR(node) {
    if(node){
        getListWithLDR(node.left);
        console.log(node.name);
        getListWithLDR(node.right);
    }
}
getListWithLDR(tree);

3.使用后序遍历，并将所有name输出。

function getListWithLRD(node) {
    if(node){
        getListWithLDR(node.left);
        getListWithLDR(node.right);
        console.log(node.name);
    }
}
getListWithLRD(tree);

原理：使用迭代。

4. 根据name找id。

function findIdByName(name,node) {
    if(node){
        if (node.name === name) {
            console.log(node.id);
        } else {
            findIdByName(name, node.left);
            findIdByName(name, node.right);
        }
    }
}
findIdByName('Carl',tree);

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有