树 先序遍历 JS 算法 头条腾讯前端面经

算法题目

实现树的先序遍历

前提知识点:
了解数据结构: 树
了解什么是树的先序遍历

算法详解

这题考查了最基础的数据结构,树 和遍历算法

我们先看下什么是树【我们以二叉树为例,每个节点最多有两个子节点】
树结构

如上是我们经常描述的数据结构,它是一个类似这样的结构,一颗倒立的树
这里的跟节点是 g,每个节点都有子节点,每个子节点也有它的子节点,这样形成一个递归结构

g 的子节点是 e 和 f
e 的子节点是 a 和 b
f 的子节点是 c 和 d

先序遍历的顺序是 g e a b f c d
也就是 先访问根节点,其次左子节点,最后右子节点

下面我们用算法来得到这个先序序列
假设用来描述树的结点的数据结构是:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/**
* 这里先简单描述节点的数据结构类型
* 节点存储的值是 value
* 左节点指向为 leftNode
* 右节点指向为 rightNode
*/
function TreeNode(value, leftNode, rightNode) {
this.value = value;
this.leftNode = leftNode;
this.rightNode = rightNode;
}

/**
* 先序遍历
*/
function preOrder(headNode, seqArr) {
if (!headNode) {
return
}

seqArr.push(headNode.value);
preOrder(headNode.leftNode, seqArr);
preOrder(headNode.rightNode, seqArr);
}

var seq = []
var headNode = new TreeNode('g');
// 假设这里是构建树
create(headNode)

preOrder(headNode, seq)

console.log(seq);

最后seq得到的就是先序遍历序列了

这里用到的是递归的方式,当然递归也有一定的弊端,如果能理解到递归的过程,那是不错的

树的中序遍历 – BAT大厂面试题
树的后序遍历 – BAT大厂面试题

 
更多前端面试题和算法题,请搜索微信小程序 前端面试精华
Front-end interview essence
Front-end interview essence

坚持原创技术分享,谢谢鼓励我继续创作!