Binary tree

concept

Binary tree: has a maximum of two children, left and right.

• The root node
• A leaf node
• Height: The level of the binary tree

Binary search tree:

Sorted binary trees satisfy the following characteristics: small on the left and large on the right. Maximal child node at level I: 2^(i-1), also called binary search tree. The code implements a tree by first defining each node:

function Node(data, left, right) {
  this.data = data;
  this.left = left;
  this.right = right;
  this.show = show;
}
Copy the code

The second is the implementation of the main BST constructor:

    function BST() {
      this.root = null;
      this.insert = insert;
      this.insertNode = insertNode;
      this.inOrder = inOrder;
      this.preOrder = preOrder;
      this.postOrder = postOrder;

      // Find: specific value maximum minimum value
      this.find = find;
      this.max = max;
      this.min = min;

      / / delete
      this.remove = remove;
    }
Copy the code

1: show

function show() {
  return this.data;
}
Copy the code

1: insert

• The first recursive method is implemented:

function insert(value) {
  let newNode = new Node(value, null.null);
  if (!this.root) {
    this.root = newNode;
  } else {
    this.insertNode(newNode, this.root); }}function insertNode(newNode, root) {
  if (newNode.data < root.data) {
    if (root.left === null) {
      root.left = newNode;
    } else {
      this.insertNode(newNode, root.left); }}else {
    if (root.right === null) {
      root.right = newNode;
    } else {
      this.insertNode(newNode, root.right); }}}Copy the code

• Second traversal implementation

function insert(value) {
  let newNode = new Node(value, null.null);
  if (!this.root) {
    this.root = newNode;
  } else {
     let current = this.root;
     let parent;
     while (true) {
      parent = current;
      if (value < current.data) {
        current = current.left;
        if (current === null) {
          parent.left = newNode;
          break; }}else {
        current = current.right;
        if (current === null) {
          parent.right = newNode;
          break;
        }
      }
    }
  }
}
Copy the code

3: middle order traversal inOrder

Starting with the leaf nodes, the final result is shown in order from small to large.

// middle order traversal
function inOrder(node) {
  if(node ! = =null) { inOrder(node.left); putstr(node.show()); inOrder(node.right); }}Copy the code

4: Traverses preOrder first

The root node is accessed first, then the left subtree, then the right subsection

    function preOrder(node) {
      if(node ! = =null) { putstr(node.show()); preOrder(node.left); preOrder(node.right); }}Copy the code

5: postOrder is traversed sequentially

Back-order traversal: first visit the leaf node, then the left subtree and the right subtree traversal access

    function postOrder(node) {
      if(node ! =null) { postOrder(node.left); postOrder(node.right); putstr(node.show()); }}Copy the code

6: Max

    function max() {
      let maxV = null;
      let current = this.root;
      while (current.right) {
        current = current.right;
      }
      return current;
    }
Copy the code

7: min

    function min() {
      let maxV = null;
      let current = this.root;
      while (current.left) {
        current = current.left;
      }
      return current;
    }

Copy the code

8: find

    function find(v) {
      let current = this.root;
      while (current) {
        if (v < current.data) {
          current = current.left;
        } else if (v > current.data) {
          current = current.right;
        } else {
          returncurrent; }}return null;
    }
Copy the code

9: remove

Binary tree deletion: find the first want to delete the node, and then considering the three conditions – : the node is a leaf node to its parent reference set to null – the node has a child node: because this node is certainly the parent node is small, so the direct child nodes of the parent node to delete the node has two child nodes

function remove(v) {
  // Find the node to delete

  let current = this.root;
  let parent = null;
  let isLeftChild = false;

  while(current.data ! == v) { parent = current;if (v < current.data) {
      isLeftChild = true;
      current = current.left;
    } else {
      isLeftChild = false;
      current = current.right;
    }

    // The same node is not found
    if (current === null) return false;
  }

  console.log("reove", current, parent);

  // Delete the root node
  if (current.left === null && current.right === null) {
    if (current === this.root) {
      this.root = null;
    } else if (isLeftChild) {
      parent.left = null;
    } else {
      parent.right = null; }}// The deleted node has only one child node
  else if (current.right === null) {
    // We need to consider the case of parent == this.root
    if (current === this.root) this.root = current.left;
    else if (isLeftChild) {
      parent.left = current.left;
    } else{ parent.right = current.left; }}else if (current.left === null) {
    // We need to consider the case of parent == this.root
    if (current === this.root) this.root = current.right;
    else if (isLeftChild) {
      parent.left = current.right;
    } else{ parent.right = current.right; }}// The deleted node has two children
  // The subsequent complement will not be implemented for the time being
}
Copy the code

test

    var b = new BST();
    b.insert(56);
    b.insert(22);
    b.insert(10);
    b.insert(30);
    b.insert(81);
    b.insert(15);
    b.insert(11);
    b.insert(9);
    b.insert(17);
    console.log(b);
    b.postOrder(b.root);
    console.log("= = =", putstr());

    // var fv = b.find(9);
    // console.log(fv);

    console.log("The minimum node is", b.min());
    console.log("The maximum node is", b.max());

    b.remove(9);
Copy the code