-
Notifications
You must be signed in to change notification settings - Fork 0
/
binaryTree.html
153 lines (138 loc) · 4.32 KB
/
binaryTree.html
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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<meta http-equiv="X-UA-Compatible" content="ie=edge">
<title>js二叉树查询、删除</title>
</head>
<body>
<script>
// 二叉树构造函数
function BinaryTree() {
// 节点的构造函数
var Node = function(key) {
this.key = key; // 节点的值
this.left = null; // 左子树节点
this.right = null; // 右子树节点
}
// 根节点
var root = null;
// 插入root的子节点
var insertNode = function(parentNode, childNode){
// 左子树构造
if (childNode.key < parentNode.key) {
// 为空时赋值,否则继续延伸
if (parentNode.left === null) {
parentNode.left = childNode;
} else {
insertNode(parentNode.left, childNode);
}
} else { // 右子树的构造 childNode.key > parentNode.key
if (parentNode.right === null) {
parentNode.right = childNode;
} else {
insertNode(parentNode.right, childNode);
}
}
}
// 获取根节点
this.getRoot = function() {
return root;
}
// 插入节点的实例方法
this.insert = function(key) {
var thisNode = new Node(key);
// 根节点赋值
if (root === null) {
root = thisNode;
} else {
// 插入子节点
insertNode(root, thisNode);
}
}
// 中序遍历的实例方法
this.inOrderTraverse = function(node, printLog) {
if (node !== null) {
// 优先去找左子树,然后中间节点,最后右子树
this.inOrderTraverse(node.left, printLog);
printLog(node.key);
this.inOrderTraverse(node.right, printLog);
}
}
// 前序遍历的实例方法
this.preTraverse = function(node, printLog) {
if (node !== null) {
// 优先输出中间节点,然后寻找左子树,最后右子树
printLog(node.key);
this.preTraverse(node.left, printLog);
this.preTraverse(node.right, printLog);
}
}
// 后序遍历的实例方法
this.postTraverse = function(node, printLog) {
if (node !== null) {
// 优先输出左子树,然后寻找右子树,最后中间节点
this.postTraverse(node.left, printLog);
this.postTraverse(node.right, printLog);
printLog(node.key);
}
}
// 查询最小值
this.minNode = function(node) {
if (node !== null) {
while(node && node.left !== null) {
node = node.left;
}
return node.key;
}
return null;
}
// 查询最大值
this.maxNode = function(node) {
if (node !== null) {
while(node && node.right !== null) {
node = node.right;
}
return node.key;
}
return null;
}
// 查找指定值
this.searchNode = function(node, key) {
if (node === null) {
return false;
}
// 要查找的值小于当前节点的值,用左子树继续查找
if (key < node.key) {
return this.searchNode(node.left, key);
} else if (key > node.key) { // 要查找的值大于当前节点的值,用右子树继续查找
return this.searchNode(node.right, key);
} else {
return true;
}
}
}
// 节点数组
var nodes = [8, 3, 10, 1, 5, 14, 4, 6, 13];
// 打印方法
var printLog = key => console.log(key);
var binaryTree = new BinaryTree();
nodes.forEach( key => {
binaryTree.insert(key);
});
var root = binaryTree.getRoot();
// 中序遍历
// binaryTree.inOrderTraverse(root, printLog);
// 前序遍历
// binaryTree.preTraverse(root, printLog);
//后序遍历
// binaryTree.postTraverse(root, printLog);
// 最小节点
console.log('binaryTree.minNode(root): ', binaryTree.minNode(root));
// 最大节点
console.log('binaryTree.maxNode(root): ', binaryTree.maxNode(root));
console.log('searchNode(root, 1): ', binaryTree.searchNode(root, 2));
</script>
</body>
</html>