-
Notifications
You must be signed in to change notification settings - Fork 1
/
bainary-search-tree.js
123 lines (103 loc) · 2.75 KB
/
bainary-search-tree.js
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
// the bainarry search implementaion;
// bainary tree representaion;
class CreateNode {
constructor(data) {
this.data = data;
this.left = null;
this.right = null;
}
}
function traversalTree(node) {
if (node == null) {
return;
}
traversalTree(node.left);
process.stdout.write(`${node.data} => `);
traversalTree(node.right);
}
function searchNode(node, num) {
if (!node) { return null }
if (node.data === num) {
return num;
}
else if (node.data < num) {
return searchNode(node.right, num)
} else if (node.data > num) {
return searchNode(node.left, num)
}
}
function insertNode(node, data) {
if (node == null) {
return new CreateNode(data);
}
if (node.data < data) {
node.right = insertNode(node.right, data);
}
if (node.data > data) {
node.left = insertNode(node.left, data);
}
return node; // we check do not attach the rest of tree;
};
function findInorderSuccessor(node) {
let current = node;
while(current.left !== null) {
current = current.left;
}
return current;
}
function deleteNode(data, node) {
if (node == null) {
return null;
} else if (node.data > data) {
node.left = deleteNode(data, node.left);
} else if (node.data < data) {
node.right = deleteNode(data, node.right);
} else { // if have one child or none
if (node.left == null) {
const temp = node.right;
node = null;
return temp
} else if (node.right == null) {
const temp = node.left;
node = null
return temp
}
{/*if have two child
find the inorder successor
replace node with inorderSuccessor*/}
node.data = findInorderSuccessor(node.right).data;
node.right = deleteNode(node.data, node.right);
}
return node;
};
//creat bainary tree;
const headNode = new CreateNode(10);
headNode.left = new CreateNode(6);
headNode.right = new CreateNode(15);
headNode.left.right = new CreateNode(7);
headNode.left.left = new CreateNode(5);
headNode.right.right = new CreateNode(16);
headNode.right.left = new CreateNode(14);
// test search;
console.log('----- search test -----');
console.log(searchNode(headNode, 14));
console.log(searchNode(headNode, 6));
console.log(searchNode(headNode, 3));
console.log(searchNode(headNode, 5));
console.log(searchNode(headNode, 10));
// test insert
console.log('----- insert test -----');
insertNode(headNode, 20);
insertNode(headNode, 4);
insertNode(headNode, 11);
insertNode(headNode, 11);
traversalTree(headNode);
// test delete
console.log('\n\n----- delete test -----');
// deleteNode(11, headNode);
console.log(deleteNode(4, headNode))
console.log(deleteNode(6, headNode))
console.log(deleteNode(11, headNode))
console.log(deleteNode(20, headNode))
console.log(deleteNode(6, headNode))
traversalTree(headNode);