每天推薦一個 GitHub 優質開源項目和一篇精選英文科技或編程文章原文，歡迎關注開源日報。交流QQ群：202790710；微博：https://weibo.com/openingsource；電報群 https://t.me/OpeningSourceOrg

今日推薦開源項目：《強化 Node.js ndb》傳送門：GitHub鏈接

推薦理由：ndb 是谷歌推出的一款 Node.js 的調試工具，畢竟是 Node.js，很多時候你都會看到它。這個 Node.js 的調試工具可以幫助你進行諸如增加斷點這樣的調試用操作，興許使用 Node 的朋友什麼時候就用的上這個。

今日推薦英文原文：《A Bit about Binary Tree》作者：Hitesh Kumar

原文鏈接：https://medium.com/smelly-code/a-bit-about-binary-tree-111e2d600974

推薦理由：二叉樹，學數據結構的時候，遲早會碰上這個的，而且興許還會一起碰上左旋轉右旋轉之類的，不過總而言之，二叉樹是遲早都要學的

A Bit about Binary Tree

In the previous post, A Gentle Introduction to Trees ?, we acquainted ourselves with trees and their properties. We saw that the naturally hierarchical data are well represented using trees. We learned that the topmost element in the hierarchy/tree which does not have any parent is called the root of a tree. Today』s post talks about a special type of tree called Binary Tree.

Binary tree is a tree where each node can have maximum two children. Since there are only two children so it』s quite intuitive to call them left and right child. Let』s get our hands dirty and code a BinaryTreeNode class in JavaScript as per the definition above.

/**
 * Represent a BinaryTreeNode
 */
class BinaryTreeNode {

    constructor(value) {

        // Value which our beloved node represents.
        this.value = value;

        // Reference of the left child.
        this.left = null;

        // Reference of the right child.
        this.right = null;

    }
}

Here』s our first binary tree created using the BinaryTreeNode class.

const root = new BinaryTreeNode(10);
const left = new BinaryTreeNode(20);
const right = new BinaryTreeNode(30);
root.left = left;
root.right = right;
console.log(root);

// Our first binary tree.
// 
//    10
//   /  \
//  20   30

This is a naive way to create a binary tree. There are many far better ways to create a binary tree. We will discuss some of them as we move on.

There are four basic operations Create, Read, Update and Delete(CRUD), which are performed on every data structure. Let』s perform them on Binary Tree as well. At first, we』ll start with the 「Read」 operation cause it』s relatively easy(a million thanks to recursion). Also, it will strengthen our bond with the binary tree.

Traversal

Reading data from a data structure is also known as traversal. As we know Binary Tree is a non-linear data structure. So its data can be traversed in many ways. In general, data traversal for trees is categorized as Breadth First Traversal(BFS) aka Level Order Traversal and Depth First Traversal(DFS).

Note. These traversal methods are not specific to binary trees. They can be used for any tree. But, for brevity, we』ll only discuss them for binary trees.

Depth First Traversal

In depth-first traversal, we start with the root node and go into the depth of it. We dive deep as much as possible until we reach the end. Once we reach the bottom i.e. the leaf node, we backtrack to traverse other nodes. It』s really important to notice that while diving or backtracking, how are we dealing with the root node or the node acting as root node? Are we traversing root node before diving? Are we traversing root node after backtracking? Answer of these questions leads to 3 new categories of depth-first traversal in-order, pre-order and post-order. I hope I my poor articulation is not confusing you.

Inorder Traversal

For in-order traversal, we start with the root node and go to the left of the tree as far as possible until we reach the end or leaf node. If there』s any leaf node, we read its data and backtrack to the immediate parent node or root node. Otherwise, we simply read data from the root node and move the right child, if there』s any, and repeat the same for the right node. The traversal sequence for in-order is left-root-right. Here are some sample binary trees which we will use for traversing.

       Sample binary trees
       ====================

    1)                      2)
  -----                   ------
    a                       j
  /   \                   /   \
 b     c                 f     k
                       /  \     \
                      a    h     z

For tree 1) and 2), in-order traversals will be b-a-c and a-f-h-j-k-z. Let me explain how we got them. For tree 1), we start with its root node i.e. node a and move to the left that is node b. Then we again move to the left of node b. Since there』s no node to visit which means we have reached to the farthest left. We read/print its data and move back(backtrack) to the root node a. We read data from it and move to its right child that is node c. and repeat the same for it. Similarly, we can traverse tree 2).

Let』s see how does it look in the code.

/**
 * Prints the values of binary tree in-order.
 * 
 */
const traverseInorder = (root) => {
  
  if (root === null) {
    return;
  }
  
  // Traverse the left node.
  traverseInorder(root.left);
  
  // Print root node's value.
  console.log(root.value);
  
  //Traverse the right node.
  traverseInorder(root.right);
};

We learned from our previous post that trees are recursive in nature. So we leveraged their recursiveness and wrote a recursive function traverseInorder which traverses a binary tree in order. As we know that for every recursive solution there』s an equivalent iterative solution. And we can go with the iterative solution as well but to keep it simple we will continue with recursion and will discuss the iterative solution on some other day.

In-order traversal is commonly used for binary search tree cause for BST it retrieves data in sorted order.

Preorder Traversal

Pre-order traversal is similar to in-order. The only difference is we traverse the root node first then, we move to the left and the right child. The traversal sequence is root-left-right. For tree 1) and 2) in our boring example pre-order traversals are a-b-c and j-f-a-h-k-z. Here』s the Js code.

/**
 * Print the values of binary tree in pre-order.
 * 
 */
const traversePreOrder = (root) => {

  if (root === null) {
    return;
  }

  // Print root node's value.
  console.log(root.value);

  // Traverse the left node.
  traversePreOrder(root.left);

  //Traverse the right node.
  traversePreOrder(root.right);
};

If you look at the code, you』ll realize that we have only changed the order of statement compared to in-order traversal. And that』s all is required.

Postorder Traversal

In post-order traversal, we traverse the root node in the end. The traversal sequence is left-right-root. For tree 1) and 2) post-order traversal will be b-c-a and a-h-f-z-k-j. Js code:

/**
 * Print the values of binary tree in post-order.
 * 
 */
const traversePostOrder = (root) => {
  if (root === null) {
    return;
  }

  // Traverse the left node.
  traversePostOrder(root.left);

  //Traverse the right node.
  traversePostOrder(root.right);

  // Print root node's value.
  console.log(root.value);
};

Breadth First Traversal

In the breadth-first traversal, we traverse tree horizontally i.e. we traverse tree by levels. We start with the root node (or first level), explore it and move to the next level. Then traverse all the nodes present on that level and move to the next level. We do the same for all remaining levels. Since nodes are traversed by levels, so breadth-first-traversal is also referred as Level Order Traversal. Here』s an illustration.

We accomplish level order traversal with the help of a queue. We create an empty queue and enqueue the root node. Then we do the followings, while the queue is not empty.
1. Dequeue a node.
2. Explore the node.
3. If the node has a left child, enqueue it.
4. If the node has a right child, enqueue it.

/**
 * Traverses  binary tree in level order. 
 * 
 */
const levelOrder = (root) => {
  if (root === null) {
    return;
  }
  
  const queue = [root];
  while (queue.length) {
    const node = queue.shift();
    // pirnt/explore node.
    console.log(node.value);
    // enqueue left
    if (node.left !== null) {
      queue.push(node.left);
    }
    // enqueue right.
    if (node.right !== null) {
      queue.push(node.right);
    }
  }
};

Create

There』s no restriction on the data stored in a binary tree which gives us the flexibility to create it. We will discuss following two popular methods to create a binary tree:
1. From array representation.
2. Level Order Insertion.

From array representation

A binary tree can also be represented using an array. For child i, in the array representation, the left child will be at 2*i + 1 and the right child will be at 2*i + 2. The index of the root node is 0. Here』s the JS code to create binary tree from array representation.

/**
 * Creates a binary tree from it's array representation.
 * 
 * @param {any[]} array
 */
const createTree = (array) => {
  if (!array.length) {
    return null;
  }
  const nodes = array.map(
    (value) => (value !== null ? new BinaryTreeNode(value) : null)
  );
  nodes.forEach((node, index) => {
    if (node === null) {
      return;
    }
    const doubleOfIndex = 2 * index;
    // Left node -> (2 * i) + 1.
    const lIndex = doubleOfIndex + 1;
    if (lIndex < array.length) {
      node.left = nodes[lIndex];
    }
    // Right node -> (2 * i) + 2.
    const rIndex = doubleOfIndex + 2;
    if (rIndex < array.length) {
      node.right = nodes[rIndex];
    }
  });
  return nodes[0];
}

Let』s consider an array and use above function to create a binary tree.

const array = [1, 2, 3, 4, 5, 6];
const tree = createTree(array);
console.log(tree);

// Tree represented by array.
//                1
//             /     \
//            2       3
//          /  \     /
//         4    5   6

Level Order Insertion

In this approach, we insert an item at the first available position in the level order.

/**
 * Insert the value into the binary tree at
 * first position available in level order.
 * 
 */
const insertInLevelOrder = (root, value) => {
  const node = new BinaryTreeNode(value);
  if (root === null) {
    return node;
  }
  const queue = [root];
  while (queue.length){
    const _node = queue.shift();
    if (_node.left === null) {
      _node.left = node;
      break;
    }
    queue.push(_node.left);
    if (_node.right === null) {
      _node.right = node;
      break;
    }
    queue.push(_node.right);
  }
  return root;
}

/**
 * Removes a node and it's subtrees from a 
 * binary tree.
 * @param root
 * @value 
 * 
 * @return updated root.
 */
const remove = (root, value) => {
  if (root === null) {
    return null;
  }
  if (root.value === value) {
    return null;
  }
  const queue = [root];
  while (queue.length) {
    const node = queue.shift();
    
    // If target is on left of parent.
    if (node.left && node.left.value === value) {
      node.left = null;
      return root;
    }
    queue.push(node.left);
    
    // If target is on right of parent.
    if (node.right && node.right.value === value) {
      node.right = null;
      return root;
    }
    queue.push(node.right);
    
  }
  return root;
};

let tree = fromArrayRepresentation([1, 2, 3, 4]);
tree = remove(tree, 2); // Remove 2 and 4(its child of 2).
console.log(tree);

每天推薦一個 GitHub 優質開源項目和一篇精選英文科技或編程文章原文，歡迎關注開源日報。交流QQ群：202790710；微博：https://weibo.com/openingsource；電報群 https://t.me/OpeningSourceOrg