This is the 11th day of my participation in the More text Challenge. For more details, see more text Challenge

The search of binary tree can be extended in many ways, which can be extended to search of tree, search of graph, and search of graph can be extended to logic of crawler. Today we’re going to look at the most basic binary tree search. In the previous article, we talked about several kinds of traversal of binary trees, so what is traversal for? Traversal is for search. For example, if I give you a binary tree, and there’s a bunch of stuff in the binary tree, and I ask you the question, is C in the binary tree, then we need to know if there’s c in the binary tree, and we need to search for the binary tree. In binary tree before we have to find the things inside, search for a first, if find when you find a few things and you don’t have to keep looking, we know there is this thing, if we all binary tree of contents to find again, did not find this stuff, so we know binary tree does not have this thing.

Search is divided into two types, one is depth first search, the other is breadth first search.

A depth-first search follows an edge of a node, goes all the way to black, then returns to the starting node, continues on to the next edge, returns if the target node is found, and traverses the entire node if not found. Since a binary tree has only two edges, the depth-first search for a binary tree starts from the root node, traverses the left subtree first, and then traverses the right subtree, which is equivalent to the first order traversal.

Breadth first search is layer by layer. As shown in the figure above, the breadth-first search starts from A, and if not found, the search will continue from the second layer CB. If the target node is found, the search will return, and if not, the search will traverse all nodes layer by layer.

Depth-first search is better suited for exploring the unknown, because it’s about going as far as you can, first.

Breadth-first search is better for exploring local areas, like I know there’s something I’m looking for near here, so I’m going to look for it level by level.

Code to achieve depth first search

function Node(value) {
    this.value = value;
    this.left = null;
    this.right = null;
}

var a = new Node("a");
var b = new Node("b");
var c = new Node("c");
var d = new Node("d");
var e = new Node("e");
var f = new Node("f");
var g = new Node("g");

a.left = c;
a.right = b;
b.left = d;
b.right = e;
c.left = f;
c.right = g;

function deepSearch(root,target){
    if (root == null) return false;
    if (root.value == target) return true;
    
    var left = deepSearch(root.left,target);
    var right = deepSearch(root.right,target);
    return left || right;
}
console.log(deepSearch(a,'d'));

Copy the code

The code implements breadth-first search

function Node(value) {
    this.value = value;
    this.left = null;
    this.right = null;
}

var a = new Node("a");
var b = new Node("b");
var c = new Node("c");
var d = new Node("d");
var e = new Node("e");
var f = new Node("f");
var g = new Node("g");

a.left = c;
a.right = b;
b.left = d;
b.right = e;
c.left = f;
c.right = g;

function f1(rootList,target){
    if (rootList == null || rootList.length == 0) return false;
    var childList = [];// The list contains the children of all nodes at the current level, so that when passed in to the next level, the list can be traversed through all nodes at the next level.
    for (var i = 0; i < rootList.length; i++) {
         if(rootList[i] ! = =null && rootList[i].value == target) {
             return true;
         } else{ childList.push(rootList[i].left); childList.push(rootList[i].right); }}return f1(childList,target);
}
console.log(f1([a],'e'));
Copy the code