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

算法题目

实现树的中序遍历

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

算法详解

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

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

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

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

中序遍历的顺序是 a e b g c f 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, lNode, rNode) {
this.value = value;
this.leftNode = lNode;
this.rightNode = rNode;
}

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

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

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

inOrder(headNode, seq)

console.log(seq);

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

这里是递归实现,当然也有其他实现方案,有能力的可以自己先思考下…

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

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

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