Queue BFS 初步学习

最近在学习数据结构的时候,学到了树的广度优先搜索可以使用队列来实现,今天尝试着写一下:

定义一棵树:

let tree = {
	"10": {
		value: "10",
		left: "4",
		right: "17",
	},
	"4": {
		value: "4",
		left: "1",
		right: "9",
	},
	"17": {
		value: "17",
		left: "12",
		right: "18",
	},
	"1": {
		value: "1",
		left: null,
		right: null,
	},
	"9": {
		value: "9",
		left: null,
		right: null,
	},
	"12": {
		value: "12",
		left: null,
		right: null,
	},
	"18": {
		value: "18",
		left: null,
		right: null,
	},
};
//定义搜索方法,关键有两点:
// 1、进入队列的时候一定是层序,
// 2、同时访问结束的节点,一定要出队列
const BreadthFirstSearch = (tree, rootNode, searchValue)=>{
  //定义一个队列
  let queue= [];
  queue.push(rootNode);
  while(queue.length>0) {
    //拿出队列的第一个元素赋值给currentNode
    let currentNode = queue[0];
    console.log('currentValue is:',currentNode.value);
    if (currentNode.value === searchValue ) {
      console.log('Found it');
      return;
    }
    //进入队列的顺序一定是层序
    if (currentNode.left !== null) {
      queue.push(tree[currentNode.left]);
    }
    if (currentNode.right !== null) {
      queue.push(tree[currentNode.right]);
    }
    //访问过的元素直接出队列
    queue.shift();
  }
  console.log('sorry not such node');
}
BreadthFirstSearch(tree, tree[10], "42");
BreadthFirstSearch(tree, tree[17], "18");

以前觉得数据结构很难,实际上学习起来的话,抓住关键的点,还是比较容易理解的额

版权声明:著作权归作者所有。

thumb_up 0 | star_outline 0 | textsms 0