Tree data structure

A tree is an abstract model of hierarchical data. In reality, the organizational structure of a family tree or company is very similar to the data structure of a tree.

Terminology for trees

A tree structure consists of a series of nodes that have parent-child relationships. Each node has a parent (except for the root node) and zero or more nodes.

The node at the top of the tree is called the root node. It has no parent node. Each element in the tree is called a node, and nodes are divided into inner nodes and outer nodes. Nodes that have at least one child node are called internal nodes. Nodes without child elements are called external nodes or leaf nodes.

A subtree consists of a node and its descendants.

The depth of a node depends on the number of its ancestor nodes.

Binary tree

A node in a binary tree can have at most two child nodes: one on the left and one on the right.

A binary search tree is a type of binary tree, but it only allows you to store values smaller (than the parent) on the left node and larger (than the parent) on the right node.

Traversal of binary trees

Binary tree traversal is divided into depth – first traversal and breadth – first traversal. Depth-first traversal can be divided into middle-order, pre-order and post-order traversal.

Depth-first traversal

In the sequence traversal

Middle-order traversal refers to visiting the left node first, then the root node, and finally the right node.

Recursive algorithm:

  1. If the binary tree is empty, the algorithm ends. Otherwise:
  2. Middle order traverses the left subtree of the root node;
  3. Access the root;
  4. Middle order traverses the right subtree of the root node;

Implementation:

  _inOrderTraverseNode(node, cb) {
    if(node ! = =null) {
      this._inOrderTraverseNode(node.left, cb)
      cb(node.key)
      this._inOrderTraverseNode(node.right, cb)
    }
  }
Copy the code

Non-recursive algorithms:

  1. Initialize a stack by pushing the root node onto the stack and marking it as the current node (node).
  2. If the stack is not empty, go to Step 3. Otherwise, no further action is required.
  3. If the current node has a left subtree and is not touched, go to Step 4. Otherwise, skip Step 5.
  4. Mark the current node “touched”, assign the left subtree of the current node to the current node (node=node.left) and push the current node to the stack, and return to Step 3.
  5. Clear the touched mark of the current node, remove a node in the stack marked as the current node, and access it. If the right subtree of the current node is not empty, the right subtree of the node will be pushed to the stack, and go to Step 3.
  inOrderTraverseNoRecursion(cb, node) {
    node = node || this.root
    let stack = new Stack()
    stack.push(node)
    while(! stack.isEmpty()) {// The left node is pushed first
      if(node.left && ! node.touched) { node.touched =true
        node = node.left
        stack.push(node)
        continue
      }
      node.touched && delete node.touched
      node = stack.pop()
      cb && cb(node.key)
      node.right && stack.push(node.right)
    }
  }
Copy the code

The first sequence traversal

Recursive algorithm:

  1. If the binary tree is empty, the algorithm ends; otherwise:
  2. Access the root;
  3. Preemptively traverses the left subtree of the root node;
  4. Preemptively traverses the right subtree of the root.
  _preOrderTraverseNode(node, cb) {
    if(node ! = =null) {
      cb(node.key)
      this._preOrderTraverseNode(node.left, cb)
      this._preOrderTraverseNode(node.right, cb)
    }
  }
Copy the code

Non-recursive algorithms:

  1. Initialize a stack and push the root node onto the stack;
  2. If the stack is not empty, steps 3 to 4 are repeated; otherwise, the execution ends.
  3. Get a node out of the queue, access the node;
  4. If the right subtree of the node is non-empty, the right subtree of the node is pushed; if the left subtree of the node is non-empty, the left subtree of the node is pushed.
  preOrderTraverseNoRecursion(cb, node) {
    node = node || this.root
    let stack = new Stack()
    stack.push(node)
    while(! stack.isEmpty()) { node = stack.pop() cb && cb(node.key)// The right node is pushed first
      node.right && stack.push(node.right)
      node.left && stack.push(node.left)
    }
  }
Copy the code

After the sequence traversal

Recursive algorithm:

  1. If the binary tree is empty, the algorithm ends; otherwise:
  2. The left subtree of the root node is traversed sequentially.
  3. The right subtree of the root node is traversed sequentially;
  4. Access the root.
  _postOrderTraverseNode(node, cb) {
    if(node ! = =null) {
      this._postOrderTraverseNode(node.left, cb)
      this._postOrderTraverseNode(node.right, cb)
      cb(node.key)
    }
  }
Copy the code

Non-recursive algorithms:

  1. Initializes a stack, pushing the root node onto the stack and marking it as the current node (item);
  2. If the stack is not empty, go to Step 3. Otherwise, no further action is required.
  3. If the current item has a left subtree and is not touched, perform 4. If the item is touched left but not right, perform 5; otherwise, perform 6.
  4. If the item flag is touched left, assign the left subtree of the current node to the current node (item=item.left) and push the current node onto the stack, returning to 3.
  5. If the item flag is touched right, assign the right subtree of the current node to the current node (item=item.right) and push the current node onto the stack, returning to 3.
  6. Clear the touched flag for the current item, eject a node on the stack, and then mark the top node as the current item, and return to 3.
  postOrderTraverseNoRecursion(cb, node) {
    node = node || this.root
    let stack = new Stack()
    stack.push(node)

    while(! stack.isEmpty()) {// The left node is pushed first
      if(node.left && ! node.touched) { node.touched ='left'
        node = node.left
        stack.push(node)
        continue
      }

      // if there is a right node and it is not accessed, it is pushed
      if(node.right && node.touched ! = ='right') {
        node.touched = 'right'
        node = node.right
        stack.push(node)
        continue
      }

      let item = stack.pop()

      item.touched && delete item.touched

      cb && cb(item.key)

      // Point to the top node of the stack
      node = stack.peek()
    }
  }
Copy the code

Breadth-first traversal

Degree priority traversal binary tree (sequential traversal) is realized by queue, starting from the first layer of binary tree (root node), traversal layer by layer from top to bottom; Nodes are accessed from left to right in the same layer.

Nodes of a binary tree are accessed from root to leaf and from left to right subtree. Steps:

  1. Initialize a queue and queue the root.
  2. If the queue is not empty, repeat steps 3 to 4; otherwise, the execution ends.
  3. Get a node out of the queue, access the node;
  4. If the left subtree of this node is non-empty, the left subtree of this node is queued; if the right subtree of this node is non-empty, the right subtree of this node is queued.

Recursive implementation:

  // breadth-first traversal (recursive)
  breadthFirstSearch(cb, node) {
    node = node || this.root
    let queue = new Queue()
    queue.enqueue(node)
    bfs(cb)
    function bfs(cb) {
      if (queue.isEmpty()) return
      let item = queue.dequeue()
      cb && cb(item.key)
      item.left && queue.enqueue(item.left)
      item.right && queue.enqueue(item.right)
      bfs(cb)
    }
  }
Copy the code

Non-recursive implementation:

  breadthFirstSearchNoRecursion(cb, node) {
    node = node || this.root
    let queue = new Queue()
    queue.enqueue(node)
    let pointer = 0
    while (pointer < queue.size()) {
      let item = queue.list[pointer++]
      cb && cb(item.key)
      item.left && queue.enqueue(item.left)
      item.right && queue.enqueue(item.right)
    }
  }
Copy the code

Complete implementation

The full code is available on Github