preface
In the last article of binary search tree, I have realized the efficient structure of tree, and have a deeper understanding of recursion. I also realized the idea of recursive traversal before, after and after binary search tree, that is, depth-first traversal. Binary search tree traversal, each node has three access opportunities. Pre-order traversal visits the node at the location of the first access opportunity, middle-order traversal visits the node at the location of the second access opportunity, and post-order traversal visits the node at the location of the third access opportunity. Let’s start with the non-recursive idea of tree traversal, also known as order traversal (breadth-first traversal). There are also features to remove tree nodes and more binary search trees.
It’s the same old saying: 20% can be mastered by reading articles, 80% can be mastered by coding, thinking and drawing. Source warehouse
Don’t be a perfectionist. Control the “degree”.
Too much pursuit of perfection will push yourself too tight, can produce various anxious state of mind, finally even doubt yourself, consider, don’t stop, mastering the degree, there is no you to put those you think completely got the control, and then became an expert at one area, on the contrary once you have very strong disgust, That means you’re going to give up or you’ve given up, and even though you wanted it to be 100, it’s zero because you gave it up.
Learn to act on your own goals. Don’t stray from your goals while studying. Prioritize. Difficult things, you can slowly look back. That will be more promising, more can improve their harvest.
Traversal of binary search trees – non-recursive writing
The recursive writing of the preceding traversal
Preorder traversal is the most natural traversal method, and it is also the most common traversal method. If there is no special case, preorder traversal is used in most cases. Access the node, then the left subtree of the node, then the right subtree of the node, and the process repeats. The beginning of a sequential traversal indicates the node visited first.
function preOrder(node) {
if (node == null) return;
/ /... Things to do
// Access the node
// Keep going to the left, then keep going back to the left, stop,
// Finally the whole operation repeats until it is completely terminated.
preOrder(node.left);
preOrder(node.right);
}
Copy the codeNonrecursive writing of a preordered traversal
Another data structure stack is used to simulate the system stack for recursive calls. Access the root node, push the root node onto the stack, and then pull the top element out of the stack to operate on the node. After the node operation is complete, the two subtrees of the node are accessed, that is, the left and right children of the node are pushed onto the stack in the order of first the right child and then the left child. This is because the stack is last in, first out, so the next node is pushed, the top element is pushed off the stack, the node is operated on, and then the two subtrees of the node are accessed. But this node is a leaf node, and both of its children are empty, so you don’t have to push anything in, and then you take the element at the top of the stack and operate on this node. After this node is done, access the two subtrees of this node, but this node is also a leaf node, so nothing is pushed in, the stack is empty, and the entire access is done.
No matter is the recursion is a recursive method and the results are consistent, the non-recursive method, the application of stack is to help you record your below which nodes to access, this process is very similar to using a simulation about the system stack in one call, equivalent to record the next step in order to access in the system stack which nodes.
Converting recursive algorithms into non-recursive algorithms is a very important application of stack data structure. The non-recursive implementation of binary search tree traversal is much more complex than the recursive implementation, because you use an auxiliary data structure to complete the process, using the stack data structure to simulate the system call stack, the semantics of the algorithm is much more difficult to read than the recursive implementation of the algorithm semantics.
The non-recursive implementation of middle-order traversal and post-order traversal of binary search tree is more complicated, especially for post-order traversal, but the non-recursive implementation of middle-order traversal and post-order traversal is not widely used in practice. But you can try to implement middle order, after order traversal of non-recursive implementation, mainly is to exercise your algorithm implementation, thinking logic implementation ideas. In the process of solving this problem may encounter some difficulties, you can solve this problem by looking at the information on the Internet, such problems may appear in the interview questions and exams, that is, the corresponding non-recursive implementation of middle-order and post-order traversal. In classic textbooks, there are generally non-recursive implementation of these three traversal. It can be seen from the realization of non-recursive traversal in the pre-order of binary search tree that it is completely possible to use the stack of simulation system to complete the operation of recursion into non-recursion. In one course for class “play algorithm interview” in the stack method to simulate the system completely, namely after the former sequence traversal turned non-recursive algorithm, which is different with the implementation of the classic textbook, but this way for your further understanding of the stack data structure or a binary search tree traversal and even the process of the system call is very meaningful.
For preorder traversal said whether recursive writing or non-recursive writing, for the tree is in the process of traversing the end, such a way to traverse is also called the depth-first traversal, eventually the traversal results first came to the tree’s deepest place, until no longer deep will begin to return to a layer, so the traverse is called depth-first traversal. The corresponding to depth-first traversal is breadth-first traversal, and the order of the results of breadth-first traversal is actually the order of one level traversal of the whole binary search tree.
Code sample
(class: MyBinarySearchTree, class: Main)
MyBinarySearchTree
// Custom binary search tree node
class MyBinarySearchTreeNode {
constructor(element, left = null, right = null) {
// The actual stored element
this.element = element;
// Left subtree of the current node
this.left = left;
// The right subtree of the current node
this.right = right; }}// Custom binary search tree
class MyBinarySearchTree {
constructor() {
this.root = null;
this.size = 0;
}
// Add elements to binary search tree +
add(element) {
if (element === null) throw new Error("element is null. can't store.");
this.root = this.recursiveAdd(this.root, element);
}
// Add elements to binary search tree recursive algorithm -
recursiveAdd(node, newElement) {
// Solve the most basic problem is the termination condition of recursive function calls
if (node === null) {
this.size++;
return new MyBinarySearchTreeNode(newElement);
}
// 1. The element of the current node is larger than the new element
// The new element is added to the left subtree of the current node
// 2. The element of the current node is smaller than the new element
// The new element is added to the right subtree of the current node
// 3. The element of the current node is equal to the new element
// Do nothing, because currently no repeating elements are added
if (this.compare(node.element, newElement) > 0)
node.left = this.recursiveAdd(node.left, newElement);
else if (this.compare(node.element, newElement) < 0)
node.right = this.recursiveAdd(node.right, newElement);
else{}// Break a complex problem into smaller problems of the same nature,
// Then solve the small question,
// Finally construct the answer to the original question
return node;
}
// Determine whether the binary search tree contains an element +
contains(element) {
if (this.root === null) throw new Error("root is null. can't query.");
return this.recursiveContains(this.root, element);
}
// Determine whether binary search tree contains an element recursive algorithm
recursiveContains(node, element) {
if (node === null) return false;
// The current node element is larger than the element to be searched
if (this.compare(node.element, element) > 0)
return this.recursiveContains(node.left, element);
else if (this.compare(node.element, element) < 0)
// The current element is smaller than the element to be searched
return this.recursiveContains(node.right, element);
// Two elements are equal
else return true;
}
// preorder traversal +
preOrder(operator) {
this.recursivePreOrder(this.root, operator);
}
// Preorder traversal recursive algorithm -
recursivePreOrder(node, operator) {
if (node === null) return;
// Call the action method
operator(node.element);
console.log(node, node.element);
// Continue to recursively traverse the left and right subtrees
this.recursivePreOrder(node.left, operator);
this.recursivePreOrder(node.right, operator);
}
// Preorder traversal non-recursive algorithm +
nonRecursivePreOrder(operator) {
let stack = new MyLinkedListStack();
stack.push(this.root);
let node = null;
while(! stack.isEmpty()) {// Unstack
node = stack.pop();
operator(node.element); // Access the current node
console.log(node.element);
// The stack is first in and then out. Nodes that need to be accessed later are placed in the stack first, and those that need to be accessed first are placed in the stack later
// Preorder traversal is to visit the current node, traverse the left subtree again, and finally traverse the right subtree
if(node.right ! = =null) stack.push(node.right);
if(node.left ! = =null) stack.push(node.left); }}// in order traversal +
inOrder(operator) {
this.recursiveInOrder(this.root, operator);
}
// Middle order traversal recursive algorithm -
recursiveInOrder(node, operator) {
if (node == null) return;
this.recursiveInOrder(node.left, operator);
operator(node.element);
console.log(node.element);
this.recursiveInOrder(node.right, operator);
}
// after traversal +
postOrder(operator) {
this.recursivePostOrder(this.root, operator);
}
// Backorder traversal recursive algorithm -
recursivePostOrder(node, operator) {
if (node == null) return;
this.recursivePostOrder(node.left, operator);
this.recursivePostOrder(node.right, operator);
operator(node.element);
console.log(node.element);
}
// Get the number of nodes in the binary search tree +
getSize() {
return this.size;
}
// Returns bool + if the binary search tree is empty
isEmpty() {
return this.size === 0;
}
// Add a comparison method to compare the size of the new element
Return 1 if the first element is larger than the second
// Return -1 if the first element is smaller than the second
// Return 0 if the first element is equal to the second
compare(elementA, elementB) {
if (elementA === null || elementB === null)
throw new Error("element is null. can't compare.");
// Write to death
if (elementA > elementB) return 1;
else if (elementA < elementB) return -1;
else return 0;
}
// Outputs information in the binary search tree
// @Override toString 2018-11-03-jwl
toString() {
let treeInfo = ' ';
treeInfo += this.getBinarySearchTreeString(this.root, 0, treeInfo);
return treeInfo;
}
// Write an auxiliary function to generate binary search tree information string
getBinarySearchTreeString(node, depth, treeInfo, pageContent = ' ') {
// The previous order traversal
if (node === null) {
treeInfo += this.getDepthString(depth) + 'null \r\n';
pageContent = this.getDepthString(depth) + 'null<br /><br />';
document.body.innerHTML += `${pageContent}`;
return treeInfo;
}
treeInfo += this.getDepthString(depth) + node.element + '\r\n';
pageContent =
this.getDepthString(depth) + node.element + '<br /><br />';
document.body.innerHTML += `${pageContent}`;
treeInfo = this.getBinarySearchTreeString(
node.left,
depth + 1,
treeInfo
);
treeInfo = this.getBinarySearchTreeString(
node.right,
depth + 1,
treeInfo
);
return treeInfo;
}
// Write an auxiliary function to generate a recursive depth string
getDepthString(depth) {
let depthString = ' ';
for (var i = 0; i < depth; i++) {
depthString += The '-';
}
returndepthString; }}Copy the codeMain
/ / the main function
class Main {
constructor() {
this.alterLine('MyBinarySearchTree Area');
let myBinarySearchTree = new MyBinarySearchTree();
let nums = [5.3.6.8.4.2];
for (var i = 0; i < nums.length; i++) {
myBinarySearchTree.add(nums[i]);
}
/////////////////
/ / / / 5
/ / / / / /
6 / / / / 3
// / \ \ //
// 2 4 8 //
/////////////////
this.alterLine('MyBinarySearchTree PreOrder Area');
myBinarySearchTree.preOrder(this.show);
this.alterLine('MyBinarySearchTree NonRecursivePreOrder Area');
myBinarySearchTree.nonRecursivePreOrder(this.show);
this.alterLine('MyBinarySearchTree InOrder Area');
myBinarySearchTree.inOrder(this.show);
this.alterLine('MyBinarySearchTree PostOrder Area');
myBinarySearchTree.postOrder(this.show);
}
// Display the content on the page
show(content) {
document.body.innerHTML += `${content}<br /><br />`;
}
// Display the dividing line
alterLine(title) {
let line = ` -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --${title}-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- `;
console.log(line);
document.body.innerHTML += `${line}<br /><br />`; }}// The page is loaded
window.onload = function() {
// Execute main function
new Main();
};
Copy the codeSequence traversal of binary search tree
Pre-order, mid-order and post-order traversal of binary search trees are all depth-first traversal in nature.
For a binary search tree each node has a value of depth, the root node is the node with depth zero, some textbooks will refer to the root node as the node with depth one, if you use the definition of an index in the computer world that’s using zero, the root node is level zero.
To traverse the first layer, then traverse layer 1, 0 times lixia layer again, such a layer traversal is called a breadth-first traversal, step by step down traverse the nodes on the breadth, expand a such traversal sequence is called a sequence traversal and breadth-first traversal, and not as before First go down a branches towards the deepest place.
For the realization of the sequence traversal or breadth-first traversal, usually not use recursive way to implement, but use a recursive manner, and in which you need to use another queue data structure, starting from the root node lined up to enter the queue, queue storage is to stay in the traversal of the element, Each time it traverses its elements, its children are queued, and so on.
First team root node, then the team the first element, there is one on the team the first element in the operation, after operation will be finished about elements of the children also team, then the elements in the queue for the operation, the elements in the queue and operation finished, let operation team about children of these elements, and finally to the elements in the queue, These elements are all leaf nodes, no left and right children, no need to join the queue, there are no elements in the queue, the whole process is done, and this process is a sequence of processing layer by layer, and this is the breadth-first traversal of a binary search tree, also known as hierarchical traversal.
Said relative to the depth-first traversal and breadth-first traversal is it quicker to find the advantages of the element you want to query, this difference is mainly used for the search strategy, rather than to use on the traverse this operation, although will traverse the binary tree all elements to access it again, this kind of circumstance depth-first traversal and breadth-first traversal is no different. But if you want to find a solution of a problem in a tree, it has said it will be from the root to separate the depth first node all ran to the tree is very deep, but it is likely the problem solution is not in such a deep place but very shallow, so a depth-first traversal takes a long time to access to the shallow place. For example, if the solution to the problem is very shallow on the right subtree, you start by traversing from the root node to the deepest part of the left subtree, it’s not necessary, but this is often used in algorithm design. For example, the shortest path of unauthorized graph, tree structure also has a very important application in algorithm design, especially in many cases to design an algorithm, it may not really need to discover the tree, but the whole process of the algorithm is completed in a virtual tree.
There are depth-first traversal and breadth-first traversal in the graph, and the essence of depth-first traversal in the tree and in the graph is the same, different points, for the graph you need to record whether a node has been traversed before, Because for the graph, the precursor of each node or the corresponding term in the tree model is that each node may have more than one parent, resulting in the problem of repeated access, which does not exist in the tree structure, so a corresponding record needs to be made in the graph structure.
Code sample
(class: MyBinarySearchTree, class: Main)
MyBinarySearchTree
// Custom binary search tree node
class MyBinarySearchTreeNode {
constructor(element, left = null, right = null) {
// The actual stored element
this.element = element;
// Left subtree of the current node
this.left = left;
// The right subtree of the current node
this.right = right; }}// Custom binary search tree
class MyBinarySearchTree {
constructor() {
this.root = null;
this.size = 0;
}
// Add elements to binary search tree +
add(element) {
if (element === null) throw new Error("element is null. can't store.");
this.root = this.recursiveAdd(this.root, element);
}
// Add elements to binary search tree recursive algorithm -
recursiveAdd(node, newElement) {
// Solve the most basic problem is the termination condition of recursive function calls
if (node === null) {
this.size++;
return new MyBinarySearchTreeNode(newElement);
}
// 1. The element of the current node is larger than the new element
// The new element is added to the left subtree of the current node
// 2. The element of the current node is smaller than the new element
// The new element is added to the right subtree of the current node
// 3. The element of the current node is equal to the new element
// Do nothing, because currently no repeating elements are added
if (this.compare(node.element, newElement) > 0)
node.left = this.recursiveAdd(node.left, newElement);
else if (this.compare(node.element, newElement) < 0)
node.right = this.recursiveAdd(node.right, newElement);
else{}// Break a complex problem into smaller problems of the same nature,
// Then solve the small question,
// Finally construct the answer to the original question
return node;
}
// Determine whether the binary search tree contains an element +
contains(element) {
if (this.root === null) throw new Error("root is null. can't query.");
return this.recursiveContains(this.root, element);
}
// Determine whether binary search tree contains an element recursive algorithm
recursiveContains(node, element) {
if (node === null) return false;
// The current node element is larger than the element to be searched
if (this.compare(node.element, element) > 0)
return this.recursiveContains(node.left, element);
else if (this.compare(node.element, element) < 0)
// The current element is smaller than the element to be searched
return this.recursiveContains(node.right, element);
// Two elements are equal
else return true;
}
// preorder traversal +
preOrder(operator) {
this.recursivePreOrder(this.root, operator);
}
// Preorder traversal recursive algorithm -
recursivePreOrder(node, operator) {
if (node === null) return;
// Call the action method
operator(node.element);
console.log(node, node.element);
// Continue to recursively traverse the left and right subtrees
this.recursivePreOrder(node.left, operator);
this.recursivePreOrder(node.right, operator);
}
// Preorder traversal non-recursive algorithm +
nonRecursivePreOrder(operator) {
let stack = new MyLinkedListStack();
stack.push(this.root);
let node = null;
while(! stack.isEmpty()) {// Unstack
node = stack.pop();
operator(node.element); // Access the current node
console.log(node.element);
// The stack is first in and then out. Nodes that need to be accessed later are placed in the stack first, and those that need to be accessed first are placed in the stack later
// Preorder traversal is to visit the current node, traverse the left subtree again, and finally traverse the right subtree
if(node.right ! = =null) stack.push(node.right);
if(node.left ! = =null) stack.push(node.left); }}// in order traversal +
inOrder(operator) {
this.recursiveInOrder(this.root, operator);
}
// Middle order traversal recursive algorithm -
recursiveInOrder(node, operator) {
if (node == null) return;
this.recursiveInOrder(node.left, operator);
operator(node.element);
console.log(node.element);
this.recursiveInOrder(node.right, operator);
}
// after traversal +
postOrder(operator) {
this.recursivePostOrder(this.root, operator);
}
// Backorder traversal recursive algorithm -
recursivePostOrder(node, operator) {
if (node == null) return;
this.recursivePostOrder(node.left, operator);
this.recursivePostOrder(node.right, operator);
operator(node.element);
console.log(node.element);
}
// sequence traversal
levelOrder(operator) {
let queue = new MyLinkedListQueue();
queue.enqueue(this.root);
let node = null;
while(! queue.isEmpty()) { node = queue.dequeue(); operator(node.element);console.log(node.element);
// The queue is first in first out, so the queue is from left to right
// The stack is last in, first out, so it is pushed from right to left
if(node.left ! = =null) queue.enqueue(node.left);
if(node.right ! = =null) queue.enqueue(node.right); }}// Get the number of nodes in the binary search tree +
getSize() {
return this.size;
}
// Returns bool + if the binary search tree is empty
isEmpty() {
return this.size === 0;
}
// Add a comparison method to compare the size of the new element
Return 1 if the first element is larger than the second
// Return -1 if the first element is smaller than the second
// Return 0 if the first element is equal to the second
compare(elementA, elementB) {
if (elementA === null || elementB === null)
throw new Error("element is null. can't compare.");
// Write to death
if (elementA > elementB) return 1;
else if (elementA < elementB) return -1;
else return 0;
}
// Outputs information in the binary search tree
// @Override toString 2018-11-03-jwl
toString() {
let treeInfo = ' ';
treeInfo += this.getBinarySearchTreeString(this.root, 0, treeInfo);
return treeInfo;
}
// Write an auxiliary function to generate binary search tree information string
getBinarySearchTreeString(node, depth, treeInfo, pageContent = ' ') {
// The previous order traversal
if (node === null) {
treeInfo += this.getDepthString(depth) + 'null \r\n';
pageContent = this.getDepthString(depth) + 'null<br /><br />';
document.body.innerHTML += `${pageContent}`;
return treeInfo;
}
treeInfo += this.getDepthString(depth) + node.element + '\r\n';
pageContent =
this.getDepthString(depth) + node.element + '<br /><br />';
document.body.innerHTML += `${pageContent}`;
treeInfo = this.getBinarySearchTreeString(
node.left,
depth + 1,
treeInfo
);
treeInfo = this.getBinarySearchTreeString(
node.right,
depth + 1,
treeInfo
);
return treeInfo;
}
// Write an auxiliary function to generate a recursive depth string
getDepthString(depth) {
let depthString = ' ';
for (var i = 0; i < depth; i++) {
depthString += The '-';
}
returndepthString; }}Copy the codeMain
/ / the main function
class Main {
constructor() {
this.alterLine('MyBinarySearchTree Area');
let myBinarySearchTree = new MyBinarySearchTree();
let nums = [5.3.6.8.4.2];
for (var i = 0; i < nums.length; i++) {
myBinarySearchTree.add(nums[i]);
}
/////////////////
/ / / / 5
/ / / / / /
6 / / / / 3
// / \ \ //
// 2 4 8 //
/////////////////
this.alterLine('MyBinarySearchTree PreOrder Area');
myBinarySearchTree.preOrder(this.show);
this.alterLine('MyBinarySearchTree NonRecursivePreOrder Area');
myBinarySearchTree.nonRecursivePreOrder(this.show);
this.alterLine('MyBinarySearchTree InOrder Area');
myBinarySearchTree.inOrder(this.show);
this.alterLine('MyBinarySearchTree PostOrder Area');
myBinarySearchTree.postOrder(this.show);
this.alterLine('MyBinarySearchTree LevelOrder Area');
myBinarySearchTree.levelOrder(this.show);
}
// Display the content on the page
show(content) {
document.body.innerHTML += `${content}<br /><br />`;
}
// Display the dividing line
alterLine(title) {
let line = ` -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --${title}-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- `;
console.log(line);
document.body.innerHTML += `${line}<br /><br />`; }}// The page is loaded
window.onload = function() {
// Execute main function
new Main();
};
Copy the codeSummary of learning methods
A lot of time learning knowledge, and is not a simple together they are studied, a lot of time to be able to achieve flexible use to understand the profound, all need to compare, deliberately to find the difference and connection between different methods, and to summarize different methods suitable for what kind of occasion. Only in this way can these knowledge be organically linked in your mind instead of fragments, and you can quickly and accurately tell what is the best way to solve different problems.
Delete nodes of binary search tree – delete Max and min
Removing a node from a binary search tree is relatively complex, so you can disassemble the operation first, starting with the simplest one.
Delete the minimum and maximum value of binary search tree, delete any element in binary search tree will reuse to delete the maximum and minimum value of binary search tree corresponding logic. To delete the maximum and minimum values in the binary search tree, first find the maximum and minimum values in the binary search tree.
Finding the maximum and the minimum in the binary search tree is very easy, every node of the left subtree all the values of the nodes is less than the current node, each node’s right child tree all the values of the nodes is greater than the current node, and then to the left, from the root node until no longer left, you can find the minimum value, and vice from the root node to the right, Until you can’t go any further to the right, you find the maximum. This operation is like working on a linked list, like finding the last node on a chain.
Delete largest element node, to remove the largest element of the node may have left child node but no right child nodes, so may cause can’t continue to the right and recursion is annulled, so this time to remove the node left child of the current node can be used to replace the current node, covering the operation is to delete the current this node. If you want to return the deleted maximum element node, you can query the maximum element node, save it in a variable, and then call the deleted maximum element node method, and finally return the saved variable.
Delete the smallest element node, the smallest element nodes may have the right to delete but have no children left child node, and recursion terminate leads to cannot continue to left, you can’t delete the node of the right children even delete together at the same time, so this time to remove the node right child of the current node can be used to replace the current node, The overwrite operation also deletes the current node. The other is the same as deleting the largest element, first query out, and then save, delete the largest element, and then return the variable of the largest element saved before.
Code sample
(class: MyBinarySearchTree, class: Main)
MyBinarySearchTree
// Custom binary search tree node
class MyBinarySearchTreeNode {
constructor(element, left = null, right = null) {
// The actual stored element
this.element = element;
// Left subtree of the current node
this.left = left;
// The right subtree of the current node
this.right = right; }}// Custom binary search tree
class MyBinarySearchTree {
constructor() {
this.root = null;
this.size = 0;
}
// Add elements to binary search tree +
add(element) {
if (element === null) throw new Error("element is null. can't store.");
this.root = this.recursiveAdd(this.root, element);
}
// Add elements to binary search tree recursive algorithm -
recursiveAdd(node, newElement) {
// Solve the most basic problem is the termination condition of recursive function calls
if (node === null) {
this.size++;
return new MyBinarySearchTreeNode(newElement);
}
// 1. The element of the current node is larger than the new element
// The new element is added to the left subtree of the current node
// 2. The element of the current node is smaller than the new element
// The new element is added to the right subtree of the current node
// 3. The element of the current node is equal to the new element
// Do nothing, because currently no repeating elements are added
if (this.compare(node.element, newElement) > 0)
node.left = this.recursiveAdd(node.left, newElement);
else if (this.compare(node.element, newElement) < 0)
node.right = this.recursiveAdd(node.right, newElement);
else{}// Break a complex problem into smaller problems of the same nature,
// Then solve the small question,
// Finally construct the answer to the original question
return node;
}
// Determine whether the binary search tree contains an element +
contains(element) {
if (this.root === null) throw new Error("root is null. can't query.");
return this.recursiveContains(this.root, element);
}
// Determine whether binary search tree contains an element recursive algorithm
recursiveContains(node, element) {
if (node === null) return false;
// The current node element is larger than the element to be searched
if (this.compare(node.element, element) > 0)
return this.recursiveContains(node.left, element);
else if (this.compare(node.element, element) < 0)
// The current element is smaller than the element to be searched
return this.recursiveContains(node.right, element);
// Two elements are equal
else return true;
}
// Find the element + of the maximum value in the binary search tree
maximum() {
if (this.size === 0) throw new Error('binary search tree is empty.');
return this.recursiveMaximum(this.root).element;
}
// Find the maximum element in the binary search tree node recursive algorithm -
recursiveMaximum(node) {
// The current node is the maximum node.
if (node.right === null) return node;
return this.recursiveMaximum(node.right);
}
// Remove the node with the largest element in the binary search tree, and return the element + of this node
removeMax() {
let maxElement = this.maximum();
this.root = this.recursiveRemoveMax(this.root);
return maxElement;
}
// Remove the node with the largest element in the binary search tree and return the recursive algorithm for this node -
recursiveRemoveMax(node) {
if (node.right === null) {
// Save the left subtree of the current node,
// Because the current node may not have a right subtree, but only a left subtree,
// Then the left subtree can replace the current node.
let leftNode = node.left;
node.left = null;
this.size--;
return leftNode;
}
node.right = this.recursiveRemoveMax(node.right);
return node;
}
// Find the minimum value + in the binary search tree
minimum() {
if (this.size === 0) throw new Error('binary search tree is empty.');
return this.recursiveMinimum(this.root).element;
}
// Find the least value of the binary search tree element of the node recursive algorithm -
recursiveMinimum(node) {
if (node.left === null) return node;
return this.recursiveMinimum(node.left);
}
// Remove the node of the least valued element in the binary search tree, and return the element + of this node
removeMin() {
let leftNode = this.minimum();
this.root = this.recursiveRemoveMin(this.root);
return leftNode;
}
// Remove the node of the least valued element in the binary search tree and return this node recursive algorithm -
recursiveRemoveMin(node) {
// Solve the simplest problem
if (node.left == null) {
let rightNode = node.right;
node.right = null;
this.size--;
return rightNode;
}
// Break complex problems into smaller problems of the same nature,
// Then solve these small problems and construct the answer to the original problem
node.left = this.recursiveRemoveMin(node.left);
return node;
}
// preorder traversal +
preOrder(operator) {
this.recursivePreOrder(this.root, operator);
}
// Preorder traversal recursive algorithm -
recursivePreOrder(node, operator) {
if (node === null) return;
// Call the action method
operator(node.element);
console.log(node, node.element);
// Continue to recursively traverse the left and right subtrees
this.recursivePreOrder(node.left, operator);
this.recursivePreOrder(node.right, operator);
}
// Preorder traversal non-recursive algorithm +
nonRecursivePreOrder(operator) {
let stack = new MyLinkedListStack();
stack.push(this.root);
let node = null;
while(! stack.isEmpty()) {// Unstack
node = stack.pop();
operator(node.element); // Access the current node
console.log(node.element);
// The stack is first in and then out. Nodes that need to be accessed later are placed in the stack first, and those that need to be accessed first are placed in the stack later
// Preorder traversal is to visit the current node, traverse the left subtree again, and finally traverse the right subtree
if(node.right ! = =null) stack.push(node.right);
if(node.left ! = =null) stack.push(node.left); }}// in order traversal +
inOrder(operator) {
this.recursiveInOrder(this.root, operator);
}
// Middle order traversal recursive algorithm -
recursiveInOrder(node, operator) {
if (node == null) return;
this.recursiveInOrder(node.left, operator);
operator(node.element);
console.log(node.element);
this.recursiveInOrder(node.right, operator);
}
// after traversal +
postOrder(operator) {
this.recursivePostOrder(this.root, operator);
}
// Backorder traversal recursive algorithm -
recursivePostOrder(node, operator) {
if (node == null) return;
this.recursivePostOrder(node.left, operator);
this.recursivePostOrder(node.right, operator);
operator(node.element);
console.log(node.element);
}
// sequence traversal
levelOrder(operator) {
let queue = new MyLinkedListQueue();
queue.enqueue(this.root);
let node = null;
while(! queue.isEmpty()) { node = queue.dequeue(); operator(node.element);console.log(node.element);
// The queue is first in first out, so the queue is from left to right
// The stack is last in, first out, so it is pushed from right to left
if(node.left ! = =null) queue.enqueue(node.left);
if(node.right ! = =null) queue.enqueue(node.right); }}// Get the number of nodes in the binary search tree +
getSize() {
return this.size;
}
// Returns bool + if the binary search tree is empty
isEmpty() {
return this.size === 0;
}
// Add a comparison method to compare the size of the new element
Return 1 if the first element is larger than the second
// Return -1 if the first element is smaller than the second
// Return 0 if the first element is equal to the second
compare(elementA, elementB) {
if (elementA === null || elementB === null)
throw new Error("element is null. can't compare.");
// Write to death
if (elementA > elementB) return 1;
else if (elementA < elementB) return -1;
else return 0;
}
// Outputs information in the binary search tree
// @Override toString 2018-11-03-jwl
toString() {
let treeInfo = ' ';
treeInfo += this.getBinarySearchTreeString(this.root, 0, treeInfo);
return treeInfo;
}
// Write an auxiliary function to generate binary search tree information string
getBinarySearchTreeString(node, depth, treeInfo, pageContent = ' ') {
// The previous order traversal
if (node === null) {
treeInfo += this.getDepthString(depth) + 'null \r\n';
pageContent = this.getDepthString(depth) + 'null<br /><br />';
document.body.innerHTML += `${pageContent}`;
return treeInfo;
}
treeInfo += this.getDepthString(depth) + node.element + '\r\n';
pageContent =
this.getDepthString(depth) + node.element + '<br /><br />';
document.body.innerHTML += `${pageContent}`;
treeInfo = this.getBinarySearchTreeString(
node.left,
depth + 1,
treeInfo
);
treeInfo = this.getBinarySearchTreeString(
node.right,
depth + 1,
treeInfo
);
return treeInfo;
}
// Write an auxiliary function to generate a recursive depth string
getDepthString(depth) {
let depthString = ' ';
for (var i = 0; i < depth; i++) {
depthString += The '-';
}
returndepthString; }}Copy the codeMain
/ / the main function
class Main {
constructor() {
this.alterLine('MyBinarySearchTree remove Min Node Area');
{
let tree = new MyBinarySearchTree();
let n = 100;
let random = Math.random;
for (var i = 0; i < n; i++) {
tree.add(n * n * n * random());
}
let array = new MyArray(n);
while(! tree.isEmpty()) { array.add(tree.removeMin()); }// The elements in the array are sorted from smallest to largest
console.log(array.toString());
for (var i = 1; i < n; i++) {
// If the element after the array is smaller than the element before the array
if (array.get(i) < array.get(i - 1))
throw new Error(
'error. array element is not (small - big) sort.'
);
}
console.log('removeMin test completed.');
this.show('removeMin test completed.');
}
this.alterLine('MyBinarySearchTree remove Max Node Area');
{
let tree = new MyBinarySearchTree();
let n = 100;
let random = Math.random;
for (var i = 0; i < n; i++) {
tree.add(n * n * n * random());
}
let array = new MyArray(n);
while(! tree.isEmpty()) { array.add(tree.removeMax()); }// The elements in the array are sorted from largest to smallest
console.log(array.toString());
for (var i = 1; i < n; i++) {
// If the element at the end of the array is larger than the element at the beginning of the array
if (array.get(i) > array.get(i - 1))
throw new Error(
'error. array element is not (big - small) sort.'
);
}
console.log('removeMax test completed.');
this.show('removeMax test completed.'); }}// Display the content on the page
show(content) {
document.body.innerHTML += `${content}<br /><br />`;
}
// Display the dividing line
alterLine(title) {
let line = ` -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --${title}-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- `;
console.log(line);
document.body.innerHTML += `${line}<br /><br />`; }}// The page is loaded
window.onload = function() {
// Execute main function
new Main();
};
Copy the codeDelete node of binary search tree – Delete any element
In binary search tree species to delete the maximum and minimum value of the logic, starting from the root node, left or right traversal, traversal to the left or right, record the right or left subtree of the node, and then return. Then, the left or right subtree of each node on the branch is covered layer by layer, and then the new node is returned layer by layer, until finally the root node is covered, so as to achieve the purpose of deleting the minimum or maximum node. The node with the smallest value is continuously traversed to the left and the right subtree is recorded at last, because the deleted node must be replaced by the right subtree of this node. Only in this way can the effect of deleting the node with the smallest value be achieved. The node with the maximum value deleted is traversed continuously to the right, and the left subtree is recorded at last. Because the deleted node is replaced by the left subtree of this node, only in this way can the effect of deleting the node with the maximum value be achieved.
If you delete any node in the binary search tree, you delete a node that only has a left child. The logic is similar. Let the left child of the node take its place. The node removed has only the right child, and the logic is the same: let the right child of the node take the place of the node. The deleted node is a leaf node, and the logic is the same because NULL is also a binary search tree, a node, and a child. The really difficult part was to delete the nodes with children on both sides. In 1962, Hibbard(computer scientist) proposed -Hibbard Deletion, find the node closest to the value of this node and replace this node with the largest one. That is, the left child of the right child who found the node (the smallest node on the left subtree of the right subtree). For example, if the node to be deleted is D, it is s = min(d->right). If you find the node that is larger or smaller than the current node, s is the successor of D. Run s->right = delMin(d->right). If s->left = d->left, return s->left. In addition to finding the successor S of node D to be deleted, you can also find the precursor P of the node to be deleted, that is, the right child of the left child of the node to be deleted (the largest node on the right subtree of the left subtree). The properties of binary search trees can be preserved whether the node to be deleted is replaced by a precursor or successor.
For binary search tree, compared with array, stack, queue, linked list these data structures are more complex, binary search tree itself is also the basis of learning other trees, such as balanced binary tree.
Code sample
(class: MyBinarySearchTree, class: Main)
MyBinarySearchTree
// Custom binary search tree node
class MyBinarySearchTreeNode {
constructor(element, left = null, right = null) {
// The actual stored element
this.element = element;
// Left subtree of the current node
this.left = left;
// The right subtree of the current node
this.right = right; }}// Custom binary search tree
class MyBinarySearchTree {
constructor() {
this.root = null;
this.size = 0;
}
// Add elements to binary search tree +
add(element) {
if (element === null) throw new Error("element is null. can't store.");
this.root = this.recursiveAdd(this.root, element);
}
// Add elements to binary search tree recursive algorithm -
recursiveAdd(node, newElement) {
// Solve the most basic problem is the termination condition of recursive function calls
if (node === null) {
this.size++;
return new MyBinarySearchTreeNode(newElement);
}
// 1. The element of the current node is larger than the new element
// The new element is added to the left subtree of the current node
// 2. The element of the current node is smaller than the new element
// The new element is added to the right subtree of the current node
// 3. The element of the current node is equal to the new element
// Do nothing, because currently no repeating elements are added
if (this.compare(node.element, newElement) > 0)
node.left = this.recursiveAdd(node.left, newElement);
else if (this.compare(node.element, newElement) < 0)
node.right = this.recursiveAdd(node.right, newElement);
else{}// Break a complex problem into smaller problems of the same nature,
// Then solve the small question,
// Finally construct the answer to the original question
return node;
}
// Determine whether the binary search tree contains an element +
contains(element) {
if (this.root === null) throw new Error("root is null. can't query.");
return this.recursiveContains(this.root, element);
}
// Determine whether binary search tree contains an element recursive algorithm
recursiveContains(node, element) {
if (node === null) return false;
// The current node element is larger than the element to be searched
if (this.compare(node.element, element) > 0)
return this.recursiveContains(node.left, element);
else if (this.compare(node.element, element) < 0)
// The current element is smaller than the element to be searched
return this.recursiveContains(node.right, element);
// Two elements are equal
else return true;
}
// Find the element + of the maximum value in the binary search tree
maximum() {
if (this.size === 0) throw new Error('binary search tree is empty.');
return this.recursiveMaximum(this.root).element;
}
// Find the maximum element in the binary search tree node recursive algorithm -
recursiveMaximum(node) {
// The current node is the maximum node.
if (node.right === null) return node;
return this.recursiveMaximum(node.right);
}
// Remove the node with the largest element in the binary search tree, and return the element + of this node
removeMax() {
let maxElement = this.maximum();
this.root = this.recursiveRemoveMax(this.root);
return maxElement;
}
// Remove the node with the largest element in the binary search tree and return the recursive algorithm for this node -
recursiveRemoveMax(node) {
if (node.right === null) {
// Save the left subtree of the current node,
// Because the current node may not have a right subtree, but only a left subtree,
// Then the left subtree can replace the current node.
let leftNode = node.left;
node.left = null;
this.size--;
return leftNode;
}
node.right = this.recursiveRemoveMax(node.right);
return node;
}
// Find the minimum value + in the binary search tree
minimum() {
if (this.size === 0) throw new Error('binary search tree is empty.');
return this.recursiveMinimum(this.root).element;
}
// Find the least value of the binary search tree element of the node recursive algorithm -
recursiveMinimum(node) {
if (node.left === null) return node;
return this.recursiveMinimum(node.left);
}
// Remove the node of the least valued element in the binary search tree, and return the element + of this node
removeMin() {
let leftNode = this.minimum();
this.root = this.recursiveRemoveMin(this.root);
return leftNode;
}
// Remove the node of the least valued element in the binary search tree and return this node recursive algorithm -
recursiveRemoveMin(node) {
// Solve the simplest problem
if (node.left == null) {
let rightNode = node.right;
node.right = null;
this.size--;
return rightNode;
}
// Break complex problems into smaller problems of the same nature,
// Then solve these small problems and construct the answer to the original problem
node.left = this.recursiveRemoveMin(node.left);
return node;
}
// Delete any node in the binary search tree
remove(element) {
this.root = this.recursiveRemove(this.root, element);
}
// Delete binary search tree recursion algorithm of any node
// Returns the root of the new binary search tree after deleting the corresponding element node
recursiveRemove(node, element) {
if (node === null) return null;
// The element value of the current node is smaller than the element to be deleted, so look for the right subtree of the current node
if (this.compare(node.element, element) < 0) {
node.right = this.recursiveRemove(node.right, element);
return node;
} else if (this.compare(node.element, element) > 0) {
// Look in the left subtree of the current node
node.left = this.recursiveRemove(node.left, element);
return node;
} else {
// If a node with the same value is found, start processing accordingly
// If the left subtree of the node is empty, the right subtree of the node overwrites the current node
if (node.left === null) {
let rightNode = node.right;
node.right = null;
this.size--;
return rightNode;
}
// If the right subtree of the current node is empty, then the left subtree of that node overwrites the current node
if (node.right === null) {
let leftNode = node.left;
node.left = null;
this.size--;
return leftNode;
}
// If the left and right subtrees of the current node are not empty, then the special operation begins
// 1. Find the smallest node in the right subtree of the current node and save it
// 2. Then delete the smallest node in the right subtree of the current node.
// 3. Let the saved node overwrite the current node
// 1. Right = the node that is returned after deleting the smallest node in the right subtree of the current node
// 2. Set the left of the saved node = left of the current node
// 4. Remove the current node from the binary search tree with the left and right values set to null
// 5. Return the saved node
let successtor = this.recursiveMinimum(node.right);
successtor.right = this.recursiveRemoveMin(node.right);
// Restore this.size from the removeMin operation
this.size++;
successtor.left = node.left;
// Start deleting the current node
node = node.left = node.right = null;
this.size--;
// Returns the current saved node
returnsuccesstor; }}// preorder traversal +
preOrder(operator) {
this.recursivePreOrder(this.root, operator);
}
// Preorder traversal recursive algorithm -
recursivePreOrder(node, operator) {
if (node === null) return;
// Call the action method
operator(node.element);
console.log(node, node.element);
// Continue to recursively traverse the left and right subtrees
this.recursivePreOrder(node.left, operator);
this.recursivePreOrder(node.right, operator);
}
// Preorder traversal non-recursive algorithm +
nonRecursivePreOrder(operator) {
let stack = new MyLinkedListStack();
stack.push(this.root);
let node = null;
while(! stack.isEmpty()) {// Unstack
node = stack.pop();
operator(node.element); // Access the current node
console.log(node.element);
// The stack is first in and then out. Nodes that need to be accessed later are placed in the stack first, and those that need to be accessed first are placed in the stack later
// Preorder traversal is to visit the current node, traverse the left subtree again, and finally traverse the right subtree
if(node.right ! = =null) stack.push(node.right);
if(node.left ! = =null) stack.push(node.left); }}// in order traversal +
inOrder(operator) {
this.recursiveInOrder(this.root, operator);
}
// Middle order traversal recursive algorithm -
recursiveInOrder(node, operator) {
if (node == null) return;
this.recursiveInOrder(node.left, operator);
operator(node.element);
console.log(node.element);
this.recursiveInOrder(node.right, operator);
}
// after traversal +
postOrder(operator) {
this.recursivePostOrder(this.root, operator);
}
// Backorder traversal recursive algorithm -
recursivePostOrder(node, operator) {
if (node == null) return;
this.recursivePostOrder(node.left, operator);
this.recursivePostOrder(node.right, operator);
operator(node.element);
console.log(node.element);
}
// sequence traversal
levelOrder(operator) {
let queue = new MyLinkedListQueue();
queue.enqueue(this.root);
let node = null;
while(! queue.isEmpty()) { node = queue.dequeue(); operator(node.element);console.log(node.element);
// The queue is first in first out, so the queue is from left to right
// The stack is last in, first out, so it is pushed from right to left
if(node.left ! = =null) queue.enqueue(node.left);
if(node.right ! = =null) queue.enqueue(node.right); }}// Get the number of nodes in the binary search tree +
getSize() {
return this.size;
}
// Returns bool + if the binary search tree is empty
isEmpty() {
return this.size === 0;
}
// Add a comparison method to compare the size of the new element
Return 1 if the first element is larger than the second
// Return -1 if the first element is smaller than the second
// Return 0 if the first element is equal to the second
compare(elementA, elementB) {
if (elementA === null || elementB === null)
throw new Error("element is null. can't compare.");
// Write to death
if (elementA > elementB) return 1;
else if (elementA < elementB) return -1;
else return 0;
}
// Outputs information in the binary search tree
// @Override toString 2018-11-03-jwl
toString() {
let treeInfo = ' ';
treeInfo += this.getBinarySearchTreeString(this.root, 0, treeInfo);
return treeInfo;
}
// Write an auxiliary function to generate binary search tree information string
getBinarySearchTreeString(node, depth, treeInfo, pageContent = ' ') {
// The previous order traversal
if (node === null) {
treeInfo += this.getDepthString(depth) + 'null \r\n';
pageContent = this.getDepthString(depth) + 'null<br /><br />';
document.body.innerHTML += `${pageContent}`;
return treeInfo;
}
treeInfo += this.getDepthString(depth) + node.element + '\r\n';
pageContent =
this.getDepthString(depth) + node.element + '<br /><br />';
document.body.innerHTML += `${pageContent}`;
treeInfo = this.getBinarySearchTreeString(
node.left,
depth + 1,
treeInfo
);
treeInfo = this.getBinarySearchTreeString(
node.right,
depth + 1,
treeInfo
);
return treeInfo;
}
// Write an auxiliary function to generate a recursive depth string
getDepthString(depth) {
let depthString = ' ';
for (var i = 0; i < depth; i++) {
depthString += The '-';
}
returndepthString; }}Copy the codeMain
/ / the main function
class Main {
constructor() {
this.alterLine('MyBinarySearchTree Remove Node Area');
{
let n = 100;
let tree = new MyBinarySearchTree();
let array = new MyArray(n);
let random = Math.random;
for (var i = 0; i < n; i++) {
tree.add(n * n * n * random());
array.add(tree.removeMin());
}
// The elements in the array are sorted from smallest to largest
console.log(array.toString());
for (var i = 0; i < n; i++) {
tree.remove(array.get(i));
}
console.log(
'removeMin test ' +
(tree.isEmpty() ? 'completed.' : 'no completed.'));this.show(
'removeMin test ' +
(tree.isEmpty() ? 'completed.' : 'no completed.')); }}// Display the content on the page
show(content) {
document.body.innerHTML += `${content}<br /><br />`;
}
// Display the dividing line
alterLine(title) {
let line = ` -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --${title}-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- `;
console.log(line);
document.body.innerHTML += `${line}<br /><br />`; }}// The page is loaded
window.onload = function() {
// Execute main function
new Main();
};
Copy the codeconclusion
At present, the binary search tree has been implemented to add element add, delete element remove, query element contains, traversal element order functions. There are other binary search tree functions as well.
For instance can be very convenient to get the binary search tree in the maximum and minimum values, it is because the binary search tree itself has a very important feature, that is binary search tree with order, the order sex is refers to all of the elements in the binary search tree are ordered, for example, using the sequence traversal traversal of the element is the element in place since the childhood, It is precisely the orderness that can conveniently obtain the maximum and minimum in the binary search tree, including its predecessors and successors that can be obtained if a value is given.
Because of this orderality, it is also possible to perform floor and ceil operations on it, that is, to find an element whose value is greater than that of an element or less than that of an element. The element specified in the precursors and successors must be in the binary search tree, and the element specified in floor and Ceil may not be in the binary search tree.
The corresponding binary search tree can also implement the rank and select methods, which specify the rank by which an element is found, and select, which is the reverse operation, which finds the rank of that element. Both operations can be implemented very easily with binary search trees. The best way to implement rank and select is to maintain a size for each node of the binary search tree. The size refers to the number of elements in the binary search tree rooted in this node. The size is equal to the number of elements in the binary search tree rooted in each node. That is, the number of each node including itself and its children below. Rank and select operations are easier to implement after each node maintains a size, that is, add a size to the node member variable, then for binary search tree operations such as add and remove operations, We also need to maintain the size of the node, so that it is very easy to implement the rank and select. If you want to see how many nodes there are in a binary search tree, you can simply look at root.size.
Maintain a depth binary search tree. For each node in the binary search tree, you can also maintain a depth value, which is the height of the node, which is the position of the node. Maintaining this value can be very helpful in some cases.
Binary search trees that support repeated elements only need to define that all nodes of the left subtree of each root node are less than or equal to the value of the root node, and all nodes of the right subtree of each root node are greater than the value of the root node. This definition well supports the implementation of binary trees of repeated elements.
The binary search tree can also be implemented by maintaining the count variable of each node, that is, keep a record of the number of elements represented by this node in the binary search tree, when you add the duplicate node, just call the corresponding node count++, if you delete the duplicate node, If count is zero, it is removed from the binary search tree.
other
The corresponding variation in binary search trees is mostly to maintain some data in Node, which allows you to handle other special cases easily. Problem sets can be found in LeetCode, tree tag: https://leetcode-cn.com/tag/tree/. For example, the first question, the maximum depth of a binary tree, this question is very similar to a linked list, it has an answer template, you should submit according to this template.
Binary search tree complexity analysis, binary search tree has two important application set and mapping, in fact, array and linked list can also achieve set and mapping, but binary search tree also has its limitations.