Before the practice of the written test has been used to brush the Java, but also referred to a certain article to write a Java version of the binary tree common algorithm, because it will soon be a job interview, these days are preparing for the interview, I turned out the previous with javascript to write again, binary tree is basically recursive processing, is relatively simple, as a warm-up. In addition, if the author of the previous Java version sees it, you can leave a message and I will mark the article quote.

Javacript binary tree common algorithm implementation

Node constructor and binary tree constructor

function Node(key) {
    this.key = key;
    this.left = null;
    this.right = null;
}
function binaryTree() {
    this.root = null;
}
Copy the code

Insert nodes to generate a binary tree

binaryTree.prototype.insert = function(root, key) {
    var node = new Node(key);
    if(root === null) {// If the root node is empty, use this node as the root node. }else if(node.key < root.key) {// A node smaller than the left child is inserted either as a left child or recursively into the left departmentif (root.left === null) {
            root.left = node;
        } else{ this.insert(root.left, key); }}else{// The node larger than the right child is either inserted as the right child or recursively into the right portionif (root.right === null) {
            root.right = node;
        } else{ this.insert(root.right, key); }}}Copy the code

The first sequence traversal

/ / binaryTree sequence traversal recursive method. The first prototype. PreOrder =function(node) {
    if(node ! == null) { console.log(node.key); // Print the current node this.inorder (node.left); // Prints the left node this.inorder (node.right); / / print right node}} / / sequence traversal non-recursive method first / / the root node of the stack, if the stack is not empty, remove node print key value, and then in turn take nodes right or the left into the stack, in turn, repeat. BinaryTree prototype. PreOrder2 =function(node) {
    let stack = [];
    stack.push(node);
    while (stack.length > 0) {
        let n = stack.pop();
        console.log(n.key);
        if(n.right ! = null) { stack.push(n.right); }if(n.left ! = null) { stack.push(n.left); }}}Copy the code

In the sequence traversal

/ / sequence traversal recursive method of binaryTree. Prototype. InOrder =function(node) {
    if(node ! == null) { this.inOrder(node.left); console.log(node.key); this.inOrder(node.right); }} sequence traversal non-recursive method in / / / / in turn get left node into the stack until completion of the lower left corner nodes into the stack, the pop-up node print key, if the node has child nodes, right it into the stack binaryTree. Prototype. InOrder2 =function(node) {
    let stack = [];
    while(node ! = null || stack.length) {if(node ! = null) { stack.push(node); node = node.left; }else {
            letn = stack.pop(); console.log(n.key); node = n.right; }}}Copy the code

After the sequence traversal

binaryTree.prototype.postOrder = function(node) {
    if (node !== null) {
        this.inOrder(node.left);
        this.inOrder(node.right);
        console.log(node.key);
    }
}
Copy the code

Find the depth of the tree

binaryTree.prototype.treeDepth = function(node) {
    if (node === null) {
        return 0;
    }
    let left = this.treeDepth(node.left);
    let right = this.treeDepth(node.right);
    return (left > right) ? (left + 1) : (right + 1);
}
Copy the code

Check whether the two trees have the same structure

binaryTree.prototype.structCmp = function(root1, root2) {
    if(root1 == null && root2 == null) {// Return if the root node is emptytrue
        return true;
    }
    if(root1 = = null | | root2 = = null) {/ / a root node is empty a return is not nullfalse
        return false;
    }
    leta = this.structCmp(root1.left, root2.left); // The left side is the same and the right side is the samelet b = this.structCmp(root1.right, root2.right);
    returna && b; // The left subtree is identical and the right subtree is identical}Copy the code

The number of nodes at layer K is obtained

binaryTree.prototype.getLevelNum = function(root, k) {
    if (root == null || k < 1) {
        return 0;
    }
    if (k == 1) {
        return 1;
    }
    returnthis.getLevelNum(root.left, k - 1) + this.getLevelNum(root.right, k - 1); // Add the k-1 layer of the left subtree to the k-1 layer of the left subtree.Copy the code

Find the mirror image of the binary tree

binaryTree.prototype.mirror = function(node) {
    if (node == null) return; [node.left, node.right] = [node.right, node.left]; // Swap left and right subtrees and recurse this.mirror(node.left); this.mirror(node.right); }Copy the code

Nearest common ancestor node

binaryTree.prototype.findLCA = function(node, target1, target2) {
    if (node == null) {
        return null;
    }
    if(node. Key = = target1 | | node. The key = = target2) {/ / if the current node is equal to the one of the node is the current node for public ancestorsreturn node;
    }
    let left = this.findLCA(node.left, target1, target2);
    let right = this.findLCA(node.right, target1, target2);
    if(left ! = null && right ! = null) {// If no subtrees are found, the target nodes are in the left and right subtrees, and the root node is its ancestorreturn node;
    }
    return(left ! = null) ? left : right; // Return if found}Copy the code

The test

var tree = new binaryTree();
let arr = [45, 5, 13, 3, 23, 7, 111];
arr.forEach((node) => {
    tree.insert(tree.root, node);
});

var tree2 = new binaryTree();
let arr2 = [46, 6, 14, 4, 24, 8, 112];
arr2.forEach((node) => {
    tree2.insert(tree2.root, node);
});

tree.preOrder(tree.root);
tree.preOrder2(tree.root);
tree2.inOrder(tree2.root);
tree.inOrder2(tree.root);
let depth = tree.treeDepth(tree.root);
console.log(depth);
let isstructCmp = tree2.structCmp(tree.root, tree2.root);
console.log(isstructCmp);
let num = tree.getLevelNum(tree.root, 4);
console.log(num);
tree.mirror(tree.root);
tree.inOrder(tree.root);
let n = tree.findLCA(tree.root, 111, 3);
console.log(n);
Copy the code

Find the KTH largest value of quicksort

Quick sort

function quickSort(array) {
  if(array.length <= 1){
      return array;
  }
  let middle = Math.floor(array.length / 2)
  let pivot = array.splice(middle, 1);
  let left =[], right = [];
  for(let i = 0; i < array.length; i++) {
      if(array[i] < pivot) {
          left.push(array[i]);
      } else{ right.push(array[i]); }}return quickSort(left).concat(pivot, quickSort(right));
}
Copy the code

Quick sort improvement to find the KTH large value

Thought is fast line cut the array into the fact of three parts, K and (of course can also be an array from the left) on the right side of the array length, if the right length of the array for K – 1, among the elements is the first big K value, if the right length of the array is greater than or equal to K, is the first K elements must be in the right, then only need to right array recursive o K values, If the length of the right array is less than k-1, the k-th value is on the left, and the k-1-right-length value is on the left

function getK(array, k) {
  if(array.length <= 1){
      return array;
  }
  let middle = Math.floor(array.length / 2)
  let pivot = array.splice(middle, 1);
  let left =[], right = [];
  for(let i = 0; i < array.length; i++) {
      if(array[i] < pivot) {
          left.push(array[i]);
      } else{ right.push(array[i]); }}if(right.length == k - 1){
      return pivot;
  } else if (right.length >= k) {
      return getK(right, k);
  } else {
      returngetK(left, k-right.length-1); }}Copy the code

In addition, this method is not the best solution, there is a better solution is to build the minimum heap of K elements, replace the top element of the heap with new elements and adjust the heap, the final K elements is the largest K elements, time complexity NlogK, we have other methods or improvement comments welcome comments.