6.二叉树的深度优先搜索和广度优先搜索代码实现（JavaScript版）

二叉树的深度优先搜索代码实现（JavaScript版）：

<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
</head>

<body>
    <script>
        function Node(value) {
            this.value = value;
            this.left = null;
            this.right = null;
        }

        var nodeA = new Node("a");
        var nodeB = new Node("b");
        var nodeC = new Node("c");
        var nodeD = new Node("d");
        var nodeE = new Node("e");
        var nodeF = new Node("f");
        var nodeG = new Node("g");

        nodeA.left = nodeB;
        nodeA.right = nodeC;
        nodeB.left = nodeD;
        nodeB.right = nodeE;
        nodeC.left = nodeF;
        nodeC.right = nodeG;

        function deepSort(root, target) { //深度搜索二叉树
            if (root == null) return false;
            if (root.value == target) return true;
            var left = deepSort(root.left, target); //搜索左子树
            var right = deepSort(root.right, target); //搜索右子树

            return left || right; //target是否在左右子树里
        }

        console.log(deepSort(nodeA, "g"));

    </script>
</body>

</html>

二叉树深度优先搜索

二叉树的广度优先搜索代码实现（JavaScript版）：

<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
</head>

<body>
    <script>
        function Node(value) {
            this.value = value;
            this.left = null;
            this.right = null;
        }

        var nodeA = new Node("a");
        var nodeB = new Node("b");
        var nodeC = new Node("c");
        var nodeD = new Node("d");
        var nodeE = new Node("e");
        var nodeF = new Node("f");
        var nodeG = new Node("g");

        nodeA.left = nodeB;
        nodeA.right = nodeC;
        nodeB.left = nodeD;
        nodeB.right = nodeE;
        nodeC.left = nodeF;
        nodeC.right = nodeG;

        function breadthSort(rootList, target) {
            if (rootList == null || rootList.length == 0) return false;
            var childList = []; //存放下一层的所有子节点
            for (var i = 0; i < rootList.length; i++) {//依次遍历所有节点
                if (rootList[i].value == target) {
                    return true;
                } else {
                    childList.push(rootList[i].left);//把节点的左子节点放入
                    childList.push(rootList[i].right);//把节点的右子节点放入
                }
            }

            return breadthSort(childList, target);//在下一层节点中继续搜索
        }

        console.log(breadthSort([nodeA], "g"));
    </script>
</body>

</html>

二叉树的广度优先搜索

赞 (0)

相关推荐