1. The binary tree

Binary tree is an important type of tree structure. The data structure abstracted from many practical problems is often in the form of binary tree, even the general tree can be simply converted to binary tree, and the storage structure and algorithm of binary tree are relatively simple, so the binary tree is particularly important. The characteristic of binary tree is that each node can have at most two subtrees, and can be divided into left and right.

A binary tree is a set of N finite elements. The set is either empty or composed of an element called root and two disjoint binary trees called left and right subtrees respectively. It is an ordered tree. When the set is empty, the binary tree is called empty binary tree. In binary trees, an element is also called a node – quoted from Baike

1.1 My understanding of binary trees

I think a binary tree is like a fork, similar to something below 👇. But you can have multiple branches, you only have two binary trees.

Turning the above tree into a binary tree resembles the following structure.

If it’s a tree, it has roots. The roots of a binary tree are called root nodes, and the rest are called leaves. Leaf nodes also have parents and children. Trees have heights, binary trees have heights, and the number of times you go from the root node to the lowest node is high.

In addition to the height, the root node is the first layer. The maximum node tree for each level of a binary tree is equal to (number of levels n) 2n−12^n-12n−1. A binary tree of height m has at most two nodes equal to 2h−12^h-12h−1. In any binary tree, if the leaf node is N0 and degree 2 is n2, there must be n0=n2+ 1N0 =n2+ 1N0 =n2+1n0=n2+1.

The above binary tree has three heights and three levels.

1.2 Complete binary trees

A binary tree of depth K with n nodes is called a complete binary tree if and only if each node pairs with nodes numbered from 1 to n in a full binary tree of depth K

The characteristics of

  1. Leaf nodes can only appear at the lowest and sublowest levels.

  2. The lowest leaf nodes are mainly on the left side of the tree.

  3. If there are leaf nodes in the second to last layer, they must be in the right continuous position.

  4. If the node degree is 1, the node has only left children, that is, no right subtree.

  5. A complete binary tree with the same number of nodes has the smallest depth.

A full binary tree must be a complete binary tree, but not the other way around.

1.3 Full binary tree

If a binary tree has only nodes of degree 0 and degree 2, and the nodes of degree 0 are on the same level, it is a full binary tree

So each node either has no nodes or has two nodes. A structure like the following is a full binary tree.

The characteristics of

  1. Leaves can only appear in the bottom layer. Equilibrium is not possible on other layers.

  2. The degree of the non-leaf node must be 2.

  3. A binary tree with the same depth has the largest number of nodes and the largest number of leaves.

1.4 Implement a number

class BitTree {
    val = null;
    left = null;
    right = null;
    constructor(val, left = null, right = null) {
        this.val = val;
        this.left = left;
        this.right = right; }}Copy the code

1.5 Preorder traversal

Front-order traversal: starts at the root node, goes to the left node, and then to the right node. Root -> left -> right node

function preOrderTraverse(treeNode, arr) {
    if (treeNode) {
        arr.push(treeNode.val);
        preOrderTraverse(treeNode.left, arr);
        preOrderTraverse(treeNode.right, arr);
    }   
}

preOrderTraverse(treeNode, []);

Copy the code

2. Reference links

  1. In-depth study of binary tree (1) binary tree foundation