1. Terms and definitions related to trees

A tree is a basic “non-linear” data structure. Like trees in nature, data structure trees are divided into three parts: root, branch, and leaf. A diagram of a general data structure puts the root at the top and the leaf at the bottom.

1.1 Terminology related to trees

The term meaning
Root Root The only node in the tree that has no incoming edge
Path the Path An ordered list of nodes joined together by edges
Child node Children All incoming edges come from several nodes of the same node, which is called the child nodes of this node
Parent the Parent A node is the parent of nodes to which all its outgoing edges are connected
Sibling node Nodes with the same parent are called siblings
Subtree Subtree The set of a node and all of its descendants, and related edges
The Leaf Leaf node Nodes that have no children are called leaf nodes
The hierarchy Level The number of edges involved in the path from the root node to a node is called the node’s hierarchy
highly The maximum level of all nodes in a tree is called the height of the tree

1.2 define

A tree consists of several nodes and two edges connecting nodes, and has the following properties:

  • One of the nodes is set as the root;
  • Every node N (except the root node) is connected to an edge from node P, which is the parent of n;
  • Each node has a unique path from the root. If each node has at most two children, such a tree is called a binary tree.

2. The binary tree

The main research object of this paper is binary tree

2.1 Basic properties of binary trees

Binary Tree is a special Tree structure, which is characterized by each node has at most two subtrees (that is, there is no node with degree greater than 2 in the Binary Tree), and the subtrees of the Binary Tree are divided into left and right, and the order of the subtrees cannot be arbitrarily reversed (ordered Tree).

According to the definition of binary tree, it has the following important properties:

  1. It’s at the end of the binary treeAt most there areA node.
  2. Depth ofThe binary tree has at mostA node.
  3. For any binary tree, if the number of leaves is zero, the number of nodes of degree 2 is,.
  4. withThe depth of the complete binary tree of nodes is, includingRepresents the largest integer not greater than x.
  5. For a complete binary tree, if the node is numbered from top to bottom and left to right, its left child must be numbered 2i and its right child must be numbered 2i+1. The parent must be numbered I /2(except when I =1 is the root).

2.1 Implementation and traversal of binary tree

2.1.1 Implementation of binary tree
# binary tree class
class TreeNode(object) :
    # initialization
    def __init__(self, val=None, left=None, right=None) :
        self.val = val    # data fields
        self.left = left    # left subtree
        self.right = right  # right subtree
    # add node
    def add_node(self,root = None,item) :
        Create a node object
        node = BTree(item)
        if not root:
            root = node
            return 
        queue = []
        queue.append(root) Add the root node if it exists
        while queue:  # This loop is to find out where the new node is added
            node_data = queue.pop(0) # fetch node
            if node_data.left == None : If the left child of the node is empty, add a new node to the left child of the node
                node_data.left = node
                return
            elif node_data.right == Node: If the right child of the node is empty, add a new node to the right child of the node
                node.data.right = node
                ruturn
            else:# if none is empty, continue searching
                queue.append(node_data.left)
                queue.append(node.data.right)
Copy the code
2.1.2 Binary tree traversal

Two important traversal modes of binary trees are depth-first traversal and breadth-first traversal:

  1. Depth-first traversal: Traverses the nodes of the tree along its depth, searching branches of the tree as deep as possible.
Depth-first is divided into three types: pre-order traversal, mid-order traversal and post-order traversal. The difference is the order of output.

Sequential traversal
def p(tree) :
    if tree == None:
        return
    print(tree.val,end="")
    p(tree=tree.left)
    p(tree=tree.right)
    
# order traversal
def m(tree) :
    if tree == None:
        return
    m(tree=tree.left)
    print(tree.val,end="")
    m(tree=tree.right)
    
Post order traversal
def e(tree) :
    if tree == None:
        return
    e(tree=tree.left)
    e(tree=tree.right)
    print(tree.val,end="")
    
 
"" construct a binary tree: _3 / \ 9_20 / \ 15 7 ""
root = TreeNode(3)
root_l = TreeNode(9)
root_r = TreeNode(20)
root.left = root_l
root.right = root_r
root_r_l = TreeNode(15)
root_r_r = TreeNode(7)
root_r.left = root_r_l
root_r.right = root_r_r
Print the result of preorder, middle-order and post-order traversal respectively
print("First order." ,end="")
p(tree=root)
print("In order." ,end="")
m(tree=root)
print("After the order." ,end="")
e(tree=root)
9 3 15 20 7 9 15 7 20 3
Copy the code
  1. Breadth-first traversal: Traverses the nodes of the tree along the degree of the tree, layer by layer.
def b(tree) :
    if not tree:
        return None
    queue = [tree] # root node is not empty, add root node
    while queue:
        node = queue.pop(0)
        print(node.val,end="")
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)

"" construct a binary tree: _3 / \ 9_20 / \ 15 7 ""
root = TreeNode(3)
root_l = TreeNode(9)
root_r = TreeNode(20)
root.left = root_l
root.right = root_r
root_r_l = TreeNode(15)
root_r_r = TreeNode(7)
root_r.left = root_r_l
root_r.right = root_r_r
Print breadth-first traversal results
print("Breadth first:",end="")
b(tree=root)
# Breadth first: 3 9 20 15 7



# extension: order traversal of binary tree (reflecting hierarchy)
def levelOrder(tree) :
    queue = []
    result = []
    if not tree:
        return []
    else:
        queue.append(tree)
    while queue:
        data = []
        for _ in range(len(queue)):
            node = queue.pop(0)
            data.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        result.append(data)
    return result
   
[[3], [20, 9], [7, 15]]
Copy the code

The above is a simple introduction to the tree structure, mainly to understand the implementation of binary tree and traversal.