In calculator science, a tree is an abstract data type (ADT) or a data structure that implements such an abstract data type, used to simulate a collection of data that has a tree-like structure. It is composed of n (n>0) finite nodes to form a hierarchical set.

The characteristics of the tree

• Each node has zero or more child nodes;
• 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

The term

• Degree of node: the number of subtrees contained by a node is called the degree of the node;
• Tree degree: In a tree, the degree of the largest node is called tree degree;
• Leaf node or terminal node: node with degree zero;
• Non-terminal node or branch node: node whose degree is not zero;
• Parent node or parent node: If a node has children, this node is called the parent node of its children.
• Child node or child node: The root node of the subtree that a node contains is called the child node of that node.
• Sibling node: nodes with the same parent node are called sibling nodes.
• 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.
• 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;
• 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;
• Cousin node: nodes whose parent node is in the same layer are Cousins of each other.
• Ancestor of a node: all nodes from the root to the branch through which the node passes;
• Descendant: Any node in the subtree rooted in a node is the descendant of the node.
• Forest: the collection of m (m>=0) trees that do not intersect each other is called forest;

What is a binary 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;

Depth first

Depth-first traversal means to traverse the binary tree by depth first, including:

Front-order traversal traversal order -> root node -> left subtree -> right subtree

Middle-order traversal traverses the order -> left subtree -> root node -> right subtree

Back-order traversal traverses the order -> left subtree -> right subtree -> root node

First, define TreeNode:

class TreeNode:
    def __init__(self, value=None, left=None, right=None):
        self.value = value
        self.left = left  # left subtree
        self.right = right  # right subtree
Copy the code

Instantiate a TreeNode:

node1 = TreeNode("A",
                 TreeNode("B",
                          TreeNode("D"),
                          TreeNode("E")
                          ),
                 TreeNode("C",
                          TreeNode("F"),
                          TreeNode("G")))Copy the code

The former sequence traversal

def preTraverse(root):
    if root is None:
        return
    print(root.value)
    preTraverse(root.left)
    preTraverse(root.right)
Copy the code

Running results:

A
B
D
E
C
F
G
Copy the code

In the sequence traversal

def midTraverse(root):
    if root is None:
        return
    midTraverse(root.left)
    print(root.value)
    midTraverse(root.right)
Copy the code

Running results:

D
B
E
A
F
C
G
Copy the code

After the sequence traversal

def afterTraverse(root):
    if root is None:
        return
    afterTraverse(root.left)
    afterTraverse(root.right)
    print(root.value)
Copy the code

Running results:

D
E
B
F
G
C
A
Copy the code

breadth-first

Breadth-first traversal is hierarchical traversal, traversing layer by layer.

def levelOrder(root):
    # write your code here
    res = []
    If the root node is empty, the empty list is returned
    if root is None:
        return res
    # Simulate a queue storage node
    q = []
    # enqueue the root node first
    q.append(root)
    The loop terminates when the list is empty
    whilelen(q) ! = 0: length = len(q)for i in range(length):
            # Unqueue nodes of the same tier
            r = q.pop(0)
            if r.left is not None:
                # Non-empty left children join the team
                q.append(r.left)
            if r.right is not None:
                # Non-empty right children join the team
                q.append(r.right)
            res.append(r.value)
            print(r.value)
    return res
Copy the code

Running results:

A
B
C
D
E
F
G
Copy the code

Afterword.

So much for the review. Here nagging, data structure and calculation is very important, a lot of things are implemented without data structure and algorithm, such as mysql implementation used B+ tree, if we understand the principle, database performance optimization will be of great help. Another important point is that algorithms and data structures are indispensable for big factory interviews. Want to enter big factory? It’s still a good algorithm.

This article was first published in the public account “Zone7”, pay attention to the public account to get the latest tweets, background reply [National Day index] to get the source code.