preface

The content of this comb is the tree in the topic of data structure, if you see the tree this kind of data structure, full head headache, think it is difficult to understand, if so, then this article may be a little help to you.

As the saying goes, in order to grasp and understand, we must first understand its concept, nature and so on.

The introduction tree is developed around the following points πŸ‘‡

  • Basic concepts of trees
  • Basic terminology
  • The types of trees
  • Binary tree concept
  • Traversal of binary trees
  • Binary tree problem summary

Public account front UpUp, return binary tree, you can obtain the brain map.

Contact πŸ‘‰TianTianUp. If you have any questions, you can contact the author.

Brain figure πŸ‘‡

Basic concepts of trees

Trees are used to simulate data sets with tree-like structure. Or you can think of it as an abstract data structure or a data structure that implements this abstract data type to simulate a collection of data that has a tree-like structure.

So, according to the definition given by Wikipedia, we seem to understand this:

It is composed of n (n>0) finite nodes to form a hierarchical set. It’s called a tree because it looks like an upside-down tree, meaning it has roots up and leaves down. It has the following characteristics:

  • Each node has limited or no children.
  • A node without a parent is called the root node.
  • Each non-root node has one and only one parent;
  • In addition to the root node, each child node can be divided into multiple disjoint subtrees.
  • There are no cycles in the tree.

At this point, we need to take out a picture to see πŸ‘‡

From the diagram, the five characteristics above can be summed up well

  • As the root node, A has no parent node, so it is the root node.
  • All nodes except root node (A) have parents, and each node has limited or no children.
  • If you start at a node, you can divide it into many subtrees, for example, if you start at node B.

Now that we know a little about trees, we need to understand some of their terminology.

Basic terminology

For a more formal summary, here’s a description from Wikipedia:

  1. Degree of node: the number of subtrees contained by a node is called the degree of the node;
  2. Tree degree: in a tree, the largest node degree is called tree degree;
  3. Leaf node or terminal node: node with degree zero;
  4. Non-terminal node or branch node: node whose degree is not zero;
  5. Parent node or parent node: If a node has children, this node is called the parent node of its children.
  6. Child node or child node: The root node of the subtree that a node contains is called the child node of that node.
  7. Sibling node: nodes with the same parent node are called sibling nodes.
  8. Node hierarchy: the root is defined as the first layer, the child nodes of the root are defined as the second layer, and so on.
  9. Depth: For any node N, the depth of n is the unique path length from the root to n, and the depth of the root is 0;
  10. Height: for any node N, the height of n is the longest path from n to a leaf, and the height of all leaves is 0;
  11. Cousin node: nodes whose parent node is in the same layer are Cousins of each other.
  12. Ancestor of a node: all nodes from the root to the branch through which the node passes;
  13. Descendant: Any node in the subtree rooted in a node is called the descendant of the node.
  14. Forest: a collection of m (m>=0) trees that do not intersect each other is called a forest.

You can understand these concepts in combination with the above diagram, and by combining the two, you are sure to have a better understanding of the tree.

With these basic concepts and some technical terms in mind, we need to make a classification of trees and see what kinds of trees there are.

The types of trees

Now that we understand the concept of trees and the basic terminology, the next thing we need to expand on is the types of trees.

We can use wikipedia as the criteria for classification πŸ‘‡

  • Unordered tree: A tree in which there is no sequential relationship between the children of any node. This tree is called unordered tree, also known as free tree.
  • Ordered tree: A tree in which the children of any node have a sequential relationship is called an ordered tree.
    • Binary tree: A tree with at most two subtrees per node is called a binary tree.
      • Complete binary tree: For a binary tree, assume its depth is D (d>1). Except for the d layer, the number of nodes in other layers has reached the maximum, and all nodes in the D layer are closely arranged continuously from left to right, such a binary tree is called a complete binary tree.
        • Full binary tree: a complete binary tree in which all leaf nodes are at the lowest level;
      • Balanced binary tree (AVL tree) : binary tree if and only if the height difference between the two subtrees of any node is not greater than 1;
      • Sorted Binary Search Tree (Binary Search Tree) : also called Binary Search Tree, ordered Binary Tree;
    • Huffman tree: The binary tree with the shortest weighted path is called Huffman tree or optimal binary tree;
    • B tree: A self-balanced binary search tree that optimizes read and write operations, maintains data order, and has more than two subtrees.

Since there are so many tree classification words, so we need to master it one by one, I personally think, master binary tree this structure is enough, it is also the simplest tree, the most widely used type.

So, let’s talk about binary trees.

The idea of a binary tree

Binary tree is a typical tree-like structure. As its name suggests, a binary tree is a tree structure in which each node has at most two subtrees, usually referred to as “left subtrees” and “right subtrees”.

The picture is from the Internet, but its exact provenance is unknown.

From the content of this image, it should be clear to show the structure of binary tree.

As for the properties of binary trees, you can refer to the following figure as supplementary knowledge, personally feel that this is not the key.

The important thing is that we need to know how it traverses.

Traversal of binary trees

We know that there are three common traversal methods for binary tree traversal, which are as follows:

  • The former sequence traversal
  • In the sequence traversal
  • After the sequence traversal

For any kind of traversal, not only do we need to master the non-recursive version of it, but for the recursive version of it, we need to learn the basic skills of one’s algorithm, so let’s take a look.

The former sequence traversal

Click here to practice pre-order traversal of binary trees

Give you the root node of the binary tree, root, and return a pre-traversal of its node value.

Suppose we mock the fake data πŸ‘‡

Input:1.null.2.3]
   1
    \
     2
    /
   3Output:1.3.2]
Copy the code

So according to our understanding of the preceding traversal, we can write the solution pseudocode πŸ‘‡

// TianTianUp
// * function TreeNode(val, left, right) {
// * this.val = (val===undefined ? 0 : val)
// * this.left = (left===undefined ? null : left)
// * this.right = (right===undefined ? null : right)
/ / *}
let preorderTraversal  = (root, arr = []) = > {
    if(root) {
      arr.push(root.val)
      preorderTraversal(root.left, arr)
      preorderTraversal(root.right, arr)
    }
    return arr
  }
Copy the code

The non-recursive version πŸ‘‡

For non-recursion, we need to use a data structure to store its nodes, the need to use is the stack, its idea can refer to πŸ‘‡

  • The root node is the target node and starts traversing its children
  • 1. Access the target node
  • 2. The left child is pushed -> until the left child is empty
  • 3. Remove the node from the stack, select the child on the right as the target node, and perform 1, 2, and 3 in sequence
  let preorderTraversal = (root, arr = []) = > {
    const stack = [], res = []
    let current = root
    while(current || stack.length > 0) {
      while (current) {
        res.push(current.val)
        stack.push(current)
        current = current.left
      }
      current = stack.pop()
      current = current.right
    }
    return res
  }
Copy the code

In the sequence traversal

Given a binary tree, return its middle-order traversal.

Example:

Enter: [1, NULL,2,3] 1 2/3

Output: 31 [1]

Advanced: The recursive algorithm is simple, can you do it with an iterative algorithm?

Source: LeetCode link: leetcode-cn.com/problems/bi… Copyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.

Recursive version πŸ‘‡

const inorderTraversal  = (root, arr = []) = > {
  if(root) {
    inorderTraversal(root.left, arr)
    arr.push(root.val)
    inorderTraversal(root.right, arr)
  }
  return arr
}
Copy the code

The non-recursive version, which I won’t explain here, is the same as the sequential traversal, the same idea, using a stack to maintain node information.

const inorderTraversal = (root, arr = []) = > {
  const stack = [], res = []
  let current = root
  while(current || stack.length > 0) {
    while (current) {
      stack.push(current)
      current = current.left
    }
    current = stack.pop()
    res.push(current.val)
    current = current.right
  }
  return res
}
Copy the code

Subsequent traversal

Given a binary tree, return its backward traversal.

Example:

Enter: [1, NULL,2,3] 1 2/3

Output: [3, 2, 1]

Advanced: The recursive algorithm is simple, can you do it with an iterative algorithm?

Source: LeetCode link: leetcode-cn.com/problems/bi… Copyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.

Recursive version πŸ‘‡

const postorderTraversal  = (root, arr = []) = > {
  if(root) {
    postorderTraversal(root.left, arr)
    postorderTraversal(root.right, arr)
    arr.push(root.val)
  }
  return arr
}
Copy the code

The non-recursive version πŸ‘‡

In fact, well, after the first two, you will find that there are routines

const postorderTraversal = (root, arr = []) = > {
  const stack = [], res = []
  let current = root, last = null  // Last records the last node
  while(current || stack.length > 0) {
    while (current) {
      stack.push(current)
      current = current.left
    }
    current = stack[stack.length - 1]
    if(! current.right || current.right == last) { current = stack.pop() res.push(current.val) last = current current =null              // continue to reload
    } else {
      current = current.right
    }
  }
  return res
}
Copy the code

Hierarchical traversal of binary trees ⭐⭐

Link: Sequential traversal of a binary tree

Given a binary tree, return the values of nodes traversed in order. (That is, layer by layer, all nodes are accessed from left to right).

Example: binary tree: [3,9,20,null,null,15,7],

3

Over 9, 20, 15, 7

Returns the result of its hierarchical traversal:

[[3], [9,20], [15,7]

Source: LeetCode link: leetcode-cn.com/problems/bi… Copyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.

Recursive version πŸ‘‡

const levelOrder = function(root) {
  if(! root)return []
  let res = []
  dfs(root, 0, res)
  return res
}

function dfs(root, step, res){
  if(root){
      if(! res[step]) res[step] = [] res[step].push(root.val) dfs(root.left, step +1, res)
      dfs(root.right, step + 1, res)
    }
}
Copy the code

The non-recursive version πŸ‘‡

It’s the queue data structure, the first-in, first-out mechanism.

const levelOrder = (root) = > {
  let queue = [], res = []
  if (root) queue.push(root);
  while (queue.length) {
      let next_queue = [],
          now_res = []
      while (queue.length) {
          root = queue.shift()
          now_res.push(root.val)
          root.left && next_queue.push(root.left)
          root.right && next_queue.push(root.right)
      }
      queue = next_queue
      res.push(now_res)
  }
  return res
}
Copy the code

Topic summary

Or that sentence, the topic is not done, the rest of the brush leetcode, I also prepared some common binary tree problem set, the quality of the topic is still good πŸ‘‡

  • Minimum depth of binary tree ⭐
  • Maximum depth of binary tree ⭐
  • Same tree ⭐
  • Binary search tree range and ⭐
  • Symmetric binary tree ⭐
  • Convert an ordered array to a binary search tree ⭐
  • Hierarchical traversal of binary trees II⭐⭐
  • The most recent common ancestor of binary trees ⭐⭐
  • Verify binary search tree ⭐⭐
  • Total paths III⭐⭐
  • There are repeated elements III⭐⭐
  • Calculate the number of elements smaller than the current element on the right ⭐⭐⭐

❀️ thank you

If you find this article helpful:

  1. Click “like” to support it, so that more people can see this content.

  2. Pay attention to the public number front-end UpUp, contact the author πŸ‘‰ DayDay2021, we learn together and progress.

  3. If you feel good, you can also read TianTian’s recent article (thanks to Digg friends for their encouragement and support 🌹🌹🌹) :

    • “Algorithms and Data Structures” a brain map showing the beauty of dynamic programming algorithms (370+πŸ‘)

    • “Algorithms and Data Structures” The Beauty of the Trie Tree (200+πŸ‘)

    • “Algorithms and Data Structures” the Beauty of divide-and-conquer Algorithms (190+πŸ‘)

    • Algorithms and Data Structures “The Beauty of DFS and BFS algorithms (240+πŸ‘)

    • “Algorithms and Data Structures” sorting algorithms (220+πŸ‘)

    • Algorithms and Data Structures takes you through the beauty of hashing algorithms (210+πŸ‘)

    • “Algorithms and Data Structures” takes you through the beauty of backtracking algorithms (190+πŸ‘)

    • The 9 basic operations of the “Algorithms and Data Structures” list (190+πŸ‘)