Js implementation tree
function BinarySearchTree() {
var Node = function (key) { / / {1}
this.key = key;
this.left = null;
this.right = null;
};
var root = null; / / {2}
/ / insert
this.insert = function (key) {
var newNode = new Node(key); / / {1}
if (root === null) { / / {2}
root = newNode;
} else {
insertNode(root, newNode); / / {3}}};var insertNode = function (node, newNode) {
if (newNode.key < node.key) { / / {4}
if (node.left === null) { / / {5}
node.left = newNode; / / {6}
} else {
insertNode(node.left, newNode); / / {7}}}else {
if (node.right === null) { / / {8}
node.right = newNode; / / {9}
} else {
insertNode(node.right, newNode); / / {10}}}};// middle order traversal
this.inOrderTraverse = function (callback) {
inOrderTraverseNode(root, callback); / / {1}
};
var inOrderTraverseNode = function (node, callback) {
if(node ! = =null) { / / {2}
inOrderTraverseNode(node.left, callback); / / {3}
callback(node.key); / / {4}
inOrderTraverseNode(node.right, callback); / / {5}}};// order traversal first
this.preOrderTraverse = function (callback) {
preOrderTraverseNode(root, callback);
};
var preOrderTraverseNode = function (node, callback) {
if(node ! = =null) {
callback(node.key); / / {1}
preOrderTraverseNode(node.left, callback); / / {2}
preOrderTraverseNode(node.right, callback); / / {3}}};// after the sequence traversal
this.postOrderTraverse = function (callback) {
postOrderTraverseNode(root, callback);
};
var postOrderTraverseNode = function (node, callback) {
if(node ! = =null) {
postOrderTraverseNode(node.left, callback); / / {1}
postOrderTraverseNode(node.right, callback); / / {2}
callback(node.key); / / {3}}};// Search for the maximum value
this.min = function () {
return minNode(root); / / {1}
};
var minNode = function (node) {
if (node) {
while(node && node.left ! = =null) { / / {2}
node = node.left; / / {3}
}
return node.key;
}
return null; / / {4}
};
// Search for the minimum value
this.max = function () {
return maxNode(root);
};
var maxNode = function (node) {
if (node) {
while(node && node.right ! = =null) { / / {5}
node = node.right;
}
return node.key;
}
return null;
};
// Search for a specific value
this.search = function (key) {
return searchNode(root, key); / / {1}
};
var searchNode = function (node, key) {
if (node === null) { / / {2}
return false;
}
if (key < node.key) { / / {3}
return searchNode(node.left, key); / / {4}
} else if (key > node.key) { / / {5}
return searchNode(node.right, key); / / {6}
} else {
return true; / / {7}}};// Remove a node
var removeNode = function (node, key) {
if (node === null) { / / {2}
return null;
}
if (key < node.key) { / / {3}
node.left = removeNode(node.left, key); / / {4}
return node; / / {5}
} else if (key > node.key) { / / {6}
node.right = removeNode(node.right, key); / / {7}
return node; / / {8}
} else { // key equals node.key
// First case -- a leaf node
if (node.left === null && node.right === null) { / / {9}
node = null; / / {10}
return node; / / {11}
}
// The second case -- a node with only one child node
if (node.left === null) { / / {12}
node = node.right; / / {13}
return node; / / {14}
} else if (node.right === null) { / / {15}
node = node.left; / / {16}
return node; / / {17}
}
// The third case -- a node with two children
var aux = findMinNode(node.right); / / {and}
node.key = aux.key; / / {and}
node.right = removeNode(node.right, aux.key); / / {} 20
return node; / / {21}}};// Get the maximum tree depth
this.maxDepth = function () {
return maxDep(root);
}
var maxDep = function (tree) {
if (tree === null) {
return 0;
}
return 1 + Math.max(maxDep(tree.left), maxDep(tree.right)); }}var tree = new BinarySearchTree();
tree.insert(10)
tree.insert(15)
tree.insert(5)
tree.insert(2)
tree.insert(7)
tree.insert(13)
tree.insert(17)
tree.postOrderTraverse((v) = > {
console.log(v)
})
console.log('-- -- -- -- -- -- -- -- -- --')
console.log(tree.max())
console.log(tree.min())
console.log(tree.search(8))
console.log(tree.search(7))
console.log(tree.maxDepth())
Copy the codeJS implements linked lists
function LinkedList() {
// Helper class: represents the item to be added to the list
let node = function (element) {
this.element = element;
this.next = null;// The next node of this node is temporarily empty
};
let length = 0;
let head = null;
this.append = function append(element) {
let node = new Node(element);/ / 1
let current;/ / 2
/ / 3
if (head === null) {
head = node
} else {
current = head
while (current.next) {
current = current.next
}
current.next = node
}
length++;/ / 4
};
this.insert = function insert(position, element) {
if (position >= 0 && position <= length) {
// When position is length, the append method is added to the end node
let node = new Node(element);
let current = head;
let previous;// Add a node in position to the previous node of the current node between previos and current
if (position = 0) {
node.next = head;
head = node;
} else {
for (let i = 0; i < position; i++) {
pervious = current;
current = current.next;
}
pervious.next = node;
node.next = current;
}
length++;
return true;
} else {
return false; }};// Add a node at the specified location
this.remove = function (element) {};// Delete the specified node
this.removeAt = function (position) {};// Delete the node at the specified location
this.searchElement = function (element) {};// Find the location of the specified element
this.searchPosition = function (position) {};// Find the element at the specified position
}
Copy the code