1/ Tree definition and basic terminology
Tree structure is a kind of important nonlinear data structure, among which tree and binary tree are the most commonly used hierarchical structure defined by branch relation. Tree structure exists widely in the objective world, such as the family tree of human society and various social organizations; It is also widely used in the field of computer, such as in the compiler program, the tree can be used to represent the grammatical structure of the source program; In database system, tree structure is also one of the important organization forms of information. In machine learning, decision tree, random forest, GBDT and so on are common tree models. In the tree structure, there are three types of nodes, namely root node, middle node and leaf node. In a tree, there is only one root node and no left and right child nodes are leaf nodes. How many layers a tree has, and how deep (or tall) the tree is. Based on the height of the tree, we can know how many nodes the tree has at most. And 2 to the k minus 1 nodeCopy the code
Definition and basic properties of 2/ binary tree
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).Copy the codeAccording to the definition of binary tree, it has the following important properties as shown in the figure below:
3 over full binary tree
A tree is a full binary tree if its depth is K and it has 2 to the k minus 1 nodes. Full binary tree, and every node except the leaf node has 2 child nodes. For a full binary tree, you can never add a new node.Copy the code
4/ binary tree traversal
The so-called binary tree traversal refers to how to patrol each node in the tree according to a certain search path, so that each node is visited once, and only once. For binary trees, the common traversal methods are: sequential traversal, middle traversal, post-sequential traversal, and hierarchical traversal. These traversal methods are generally implemented using recursive algorithms. The operation of sequential traversal is defined as: if the binary tree is empty, the operation is empty; Otherwise (1) access the root node; (2) Traverse the left subtree in order first; (3) Traverse the right subtree in order first. The operation of middle-order traversal is defined as: if the binary tree is empty, the operation is empty; Otherwise, the order in (1) traverses the left subtree; (2) Access the root node; (3) In order to traverse the right subtree. The operation of post-order traversal is defined as: if the binary tree is empty, the operation is empty; Otherwise, (1) the left subtree is traversed sequentially; (2) The right subtree is traversed sequentially; (3) Access the root node. The operation of sequence traversal is defined as: if the binary tree is empty, it is empty; Otherwise, access is hierarchical from top to bottom and left to right. For example, the following figure shows the sequence traversal: 18 7 3 4 11 5 1 3 6 2 4 The sequence traversal is: 3 7 4 18 1 5 3 11 2 6 4 the sequence traversal is: 3 4 7 1 3 5 2 4 6 11 [[18], [7, 11], [3, 4, 5, 6], [1, 3, 2, 4]Copy the code
5/ Binary tree python code implementation
from graphviz import Digraph
import uuid
from random import sample
# binary tree class
class BTree(object) :
# initialization
# build a binary tree
def __init__(self, data=None, left=None, right=None) :
# For a node, it consists of three parts, and data, left child, right child
self.data = data # data fields
self.left = left # left subtree
self.right = right # right subtree
self.dot = Digraph(comment='Binary Tree')
# preorder traversal
def preorder(self) :
if self.data is not None:
print(self.data, end=' ')
if self.left is not None:
self.left.preorder()
if self.right is not None:
self.right.preorder()
# order traversal
def inorder(self) :
if self.left is not None:
self.left.inorder()
if self.data is not None:
print(self.data, end=' ')
if self.right is not None:
self.right.inorder()
Post order traversal
def postorder(self) :
if self.left is not None:
self.left.postorder()
if self.right is not None:
self.right.postorder()
if self.data is not None:
print(self.data, end=' ')
# sequence traversal
def levelorder(self) :
Return the left child of a node
def LChild_Of_Node(node) :
return node.left if node.left is not None else None
Return the right child of a node
def RChild_Of_Node(node) :
return node.right if node.right is not None else None
# order traversal list
level_order = []
Whether to add data from the root node
if self.data is not None:
level_order.append([self])
# The height of the binary tree
height = self.height()
if height >= 1:
Add nodes instead of data to level_ORDER for the second and subsequent levels
for _ in range(2, height + 1):
level = [] # Nodes for this layer
for node in level_order[-1] :Add the left child if the left child is not empty
if LChild_Of_Node(node):
level.append(LChild_Of_Node(node))
If the right child is not empty, add the right child
if RChild_Of_Node(node):
level.append(RChild_Of_Node(node))
If the layer is not empty, add it
if level:
level_order.append(level)
Fetch data from each layer
for i in range(0, height): # layer
for index in range(len(level_order[i])):
level_order[i][index] = level_order[i][index].data
return level_order
# The height of the binary tree
def height(self) :
# empty tree height = 0,
if self.data is None:
return 0
The height of the root node is 1
elif self.left is None and self.right is None:
return 1
# As long as one is not None, recurse
elif self.left is None and self.right is not None:
return 1 + self.right.height()
elif self.left is not None and self.right is None:
return 1 + self.left.height()
# return a maximum value for the depth of the tree
else:
return 1 + max(self.left.height(), self.right.height())
# the leaves of a binary tree
def leaves(self) :
# If there is no data field, return None
if self.data is None:
return None
# No left child, no right child, such nodes are leaf nodes, print out
elif self.left is None and self.right is None:
print(self.data, end=' ')
# Recurse if there is a right child
elif self.left is None and self.right is not None:
self.right.leaves()
# Recurse if there are left children
elif self.right is None and self.left is not None:
self.left.leaves()
# If both the left and right children have it, then both sides are recursive
else:
self.left.leaves()
self.right.leaves()
# Use Graphviz to visualize binary trees
def print_tree(self, save_path='./Binary_Tree.gv', label=False) :
# colors for labels of nodes
colors = ['skyblue'.'tomato'.'orange'.'purple'.'green'.'yellow'.'pink'.'red']
Draw a binary tree with a node as the root
def print_node(node, node_tag) :
# node color
color = sample(colors,1) [0]
if node.left is not None:
left_tag = str(uuid.uuid1()) # Left node data
self.dot.node(left_tag, str(node.left.data), style='filled', color=color) # left node
label_string = 'L' if label else ' ' # Whether to label the connection line to indicate a left subtree
self.dot.edge(node_tag, left_tag, label=label_string) The left node is connected to its parent
print_node(node.left, left_tag)
if node.right is not None:
right_tag = str(uuid.uuid1())
self.dot.node(right_tag, str(node.right.data), style='filled', color=color)
label_string = 'R' if label else ' ' # Whether to label the connection line to indicate the right subtree
self.dot.edge(node_tag, right_tag, label=label_string)
print_node(node.right, right_tag)
# if the tree is not empty
if self.data is not None:
root_tag = str(uuid.uuid1()) # root node tag
self.dot.node(root_tag, str(self.data), style='filled', color=sample(colors,1) [0]) Create the root node
print_node(self, root_tag)
self.dot.render(save_path) Save the file as the specified file
Copy the codeIn the above code, create binary tree class BTree, implement the following methods: 1. Initialization method: The tree stores data. The left subtree and the right subtree are left and right. The default value is None. 1. Preorder () method: recursively achieve the sequential traversal of the binary tree; 1. Inorder () method: recursive realization of middle order traversal of binary tree; 1. Postorder () method: recursively achieve the post-order traversal of the binary tree; 1. Levelorder () method: recursive implementation of binary tree sequence traversal; 1. Height () method: calculate the height of binary tree; 1. Leaves () method: calculate the binary tree leaves; 1. Print_tree () method: Use Graphviz to realize binary tree visualization. The parameters to be set are save_path and label. Save_path is the file saving path. Label is the label that determines whether to add the left and right subtrees of the binary tree to the Graphviz file. It is used to tell which subtree is the left and which is the right subtree. It can be set by the user.Copy the code