Unlike the data structures of linear tables such as arrays and queues, trees are nonlinear structures. In addition to trees, graphs are also nonlinear structures.

The binary tree is shown below.

Nodes and edges

It consists of nodes and edges connecting nodes in a tree, and a binary tree has at most two child nodes. There are several concepts about nodes:

  1. Parent node: Node 1 is the parent node of nodes 2 and 3.
  2. Child nodes: Nodes 4 and 5 are child nodes of node 2.
  3. Sibling nodes: nodes 2 and 3 are sibling nodes.
  4. Leaf node: nodes without child nodes are leaf nodes, such as nodes 4 and 5.
  5. Root node: a node without a parent is the root node, such as node 1.

There are several concepts about tree hierarchies:

  1. Height of node: the longest path from the node to the leaf node, that is, the number of edges;
  2. Depth of node: the number of edges experienced by the root node to this node;
  3. Layer number of nodes: depth + 1;
  4. Tree height: Equal to the height of the root node.

The following diagrams help you understand the concepts of node height, depth, and layer.

Special binary tree

A binary tree is called a full binary tree if the leaves are all at the same level and each node has two children except the leaves. The legend above is a full binary tree.

A binary tree is called a complete binary tree if the last leaf nodes are on the left and the number of nodes in the other layers is maximized. If we remove node 7 from the diagram above, the condition of a full binary tree is met.

Storage of binary trees

Binary tree storage is also dependent on the most basic data structure:

  • An array of
  • The list

For array storage, we can use the following rules to specify where each node is stored in the array.

  1. Assume that the parent storage index is I;
  2. The position of the left child node of this node is 2 * I, and that of the right child node is 2 * I + 1.
  3. The root node is stored in bit 1.

The following figure helps to understand how binary tree arrays are stored. As you can see, full binary trees use array storage to make full use of array space. Incomplete binary trees result in a waste of array space.

For linked list storage, we use the following structure to build a binary tree.

class Node {
    Node leftChild;
    Node rightChild;
}
Copy the code

Traversal of binary trees

There are two types of tree and graph traversal:

  1. Depth-first traversal: If there is a child node with a deeper hierarchy, this node is traversed first; otherwise, other nodes with the same hierarchy are traversed.
  2. Breadth-first traversal: if sibling nodes of the same level exist, sibling nodes are traversed first, otherwise child nodes are traversed.

Depth-first traversal of trees can be divided into three types:

  1. Sequential traversal: access the current node — access the left subtree — access the right subtree;
  2. Middle-order traversal: access the left subtree — access the current node — access the right subtree;
  3. Back-order traversal: Access the left subtree — access the right subtree — access the current node.

As an example, the traversal sequence is as follows:

  1. Foreorder traversal: 1, 2, 4, 5, 3, 6, 7;
  2. Middle order traversal: 4, 2, 5, 1, 6, 3, 7;
  3. Backorder traversal: 4, 5, 2, 6, 7, 3, 1.

The recursive codes for the three traversals are as follows.

void preOrder(Node root) {
    if (root == null) return;

    print(root)
    preOrder(root.left);
    preOrder(root.right);
}

void inOrder(Node root) {
    if (root == null) return;

    inOrder(root.left);
    print(root)
    inOrder(root.right);
}

void postOrder(Node root) {
    if (root == null) return;

    postOrder(root.left);
    postOrder(root.right);
    print(root)
}
Copy the code

conclusion

This time we understand the basic knowledge of binary tree, binary tree characteristics, binary tree array and linked list storage, binary tree traversal. We’ll talk a little bit about the application of binary trees, and how it optimizes the complexity of search algorithms.