二叉树概述|博客系列
# 二叉树概述
# 二叉树概述
二叉树是非常基础并且是一种非常重要的数据结构, 正和它的名字一样, 二叉树的每个节点最多有两个子树.
我们可以先来看下面的这颗二叉树, 为了方便,我这里将left用L表示, right用R表示:
# 二叉树与JS
上面的二叉树可以用我们JavaScript的对象来进行表示, 相信大家很容易就能看懂:
var tree = {
value: "Root",
left: {
value: 'L',
left: {
value: 'LL'
},
right: {
value: 'LR'
}
},
right: {
value: 'R',
left: {
value: 'RL'
},
right: {
value: 'RR'
}
}
}
@前端进阶之旅: 代码已经复制到剪贴板
当前节点的值存放到value这个属性中, 左(右)子树存放到left(right) 中.
这样我们很容易就能写出数组[1, null, 2, 3]的二叉树：
# 定义一个二叉树的节点类
通过上面的JS对象，让我们来写一个可以生成单个节点的类：
// 定义一个二叉树的节点类
class Node {
constructor(value, left = null, right = null) {
this.value = value;
this.left = left;
this.right = right;
}
}
@前端进阶之旅: 代码已经复制到剪贴板
现在让我们用这个类来生成一颗简单的二叉树吧：
const tree = new Node(
'Root',
new Node(
'L',
new Node('LL'),
new Node('LR')
),
new Node(
'R',
new Node('RL'),
new Node('RR')
)
)
console.log(tree)
@前端进阶之旅: 代码已经复制到剪贴板
(这棵树在后面都会用到，大家知道后面案例的tree表示的是它就行了)
# 二叉搜索树
二叉搜索树(也叫二叉查找树)的特点：
- 左子树上所有节点的值必定全部小于根节点的值
- 右子树上所有节点的值必定全部大于根节点的值
- 左子树和右子树也分别为二叉搜索树
例如二叉搜索树：
const root = new Node(
2,
new Node(1),
new Node(
5,
new Node(4),
new Node(6)
)
);
@前端进阶之旅: 代码已经复制到剪贴板
[左子树][根][右子树]
// 对应为：
[1] [2] [4 5 6]
@前端进阶之旅: 代码已经复制到剪贴板
非二叉搜索树：
const root = new Node(
2,
new Node(3),
new Node(4)
)
@前端进阶之旅: 代码已经复制到剪贴板
[左子树][根][右子树]
// 对应为：
[3] [2] [4]
@前端进阶之旅: 代码已经复制到剪贴板
