一、定义
二叉树：在计算机科学中，二叉树是每个节点最多有两个子树的树结构。
二、模拟
- 定义我们的二叉树
- 节点，保存值，并有一个 show 方法
1
2
3
4
5
| function Node(data, left, right) {
this.data = data;
this.left = left;
this.right = right;
}
|
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
| function BST(){
this.root = null;
this.insert = insert;
}
// 插入新节点
function insert(data){
var n = new Node(data, null, null);
if(this.root = null){
// 第一次初始化根节点
this.root = n;
}else{
var current = this.root;
var parent;
while(true){
parent = current;
// 小于节点插入左子树，否则插入右子树
if(data < current.data){
current = current.left;
if(currnet === null){
parent.left = n;
break
}
}else{
current = current.right;
if(current === null){
parent.right = n;
break
}
}
}
}
}
|
- 说到二叉树，肯定想到了前序，中序，后序，层序遍历，现在模拟一下
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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
| function order(type){
var str = '';
// 先序遍历
function preOrder(node){
if(node !== null){
str += node.data + ' ';
preOrder(node.left);
preOrder(node.right);
}
}
// 中序遍历
function inOrder(node) {
if(!(node == null)) {
inOrder(node.left);
str += node.data + ' ';
inOrder(node.right);
}
}
// 后续遍历
function lastOrder(node){
if(!(node == null)){
lastOrder(node.left);
lastOrder(node.right);
str += node.data + ' ';
}
}
// 层序遍历(广度优先遍历)
function levelOrder(node){
var res = [];
res.push(node);
while(res.length){
if(res[0].left !== null){
res.push(res[0].left);
}
if(res[0].right !== null){
res.push(res[0].right);
}
str += res.shift().data + ' ';
}
}
if(type === 'preOrder'){
preOrder(this.root);
}else if(type === 'inOrder'){
inOrder(this.root);
}else if(type === 'lastOrder'){
lastOrder(this.root);
}else if(type === 'levelOrder'){
levelOrder(this.root);
}
console.log(str);
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| // 求树的高度
function height(){
var node = this.root;
var res = [];
function _hei(n, hei){
if(n.left !== null){
_hei(n.left, hei + 1)
}else{
res.push(hei)
}
if(n.right !== null){
_hei(n.right, hei + 1)
}else{
res.push(hei)
}
}
_hei(node, 1);
console.log(Math.max(...res));
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| var nums = new BST();
nums.insert(23);
nums.insert(45);
nums.insert(16);
nums.insert(37);
nums.insert(3);
nums.insert(99);
nums.insert(22);
nums.insert(22);
console.log('先序遍历：');
nums.order('preOrder');
console.log('中序遍历：');
nums.order('inOrder');
console.log('后序遍历：');
nums.order('lastOrder');
console.log('层序遍历：');
nums.order('levelOrder');
console.log('树的高度：');
nums.height();
|
- 结果
