Python algorithm practice week6 tree

0x01 Linear data structure

Linear data structure is a way for computer to organize data

• A linear structure is a collection of data elements
  • There is a unique first element
  • There is a unique tail element
  • Except for the first and last elements , All elements have a unique pioneer
  • Except for the first and last elements , All elements have a unique successor

Common linear data structures are ： Array 、 Stack 、 queue 、 Chain list, etc

Array

Python The language does not provide an array data type , You usually use lists as arrays .

Stack

Stack (Stack) It's a special kind of list

The core operation of stack

The realization of the stack Python It is very efficient for lists to add and remove elements from the last position , Stack operation can be realized naturally

list = []
list.append(1)
list.append(2)
print(list)
# [1,2]
list.pop
print(list)
# [1]

queue

queue (Quene) It is also a special list

The core operation of the queue

Implementation of queues Queues implemented with lists are not suitable for ( Adding data to the header can only use insert Method needs to move other data ),collections.deque yes Python Dual ended queue provided , Support adding and deleting data from either end , Fast

1. collections import deque
2. = deque() dq.append(1) dq.append(2) print(dq) # deque([1,2]) dq.popleft() # deque([2]) dq.popleft() # deque([])

0x02 The concept of tree

A tree is not a linear structure , It's nonlinear , Trees are widely used in computer science , Including the operating system 、 graphics 、 Databases and computer networks .

Tree terminology

• node (Node) Each data element in the tree is called a node , Nodes are the basic components of a tree .
• edge (Edge) Edges are also an essential part of a tree . The side has a direction , Link two nodes , And express the connection between the two .

Except for the root node, each node has only one link to other nodes Into the side ( Point to the edge of the node ), Each node may have many Out of the way ( An edge pointing from this node to another node )

• The root node (Root) The root node is the only node in the tree that has no edge
• route (Path) A path is an ordered arrangement of nodes connected by edges .
• Child node set (Children) When the incoming edge of one node comes from another node , Call the former a child of the latter , All child nodes of the same node constitute a set of child nodes .
• Parent node (Parent) A node is the parent node of all nodes connected to its edge
• Brother node (Sibling) All child nodes of the same node are siblings of each other
• subtree (Subtree) A subtree is a collection of all the edges and descendants of a child node of a parent node
• Leaf nodes (Leaf Node) Nodes without children are called leaf nodes
• The layer number (Level) The number of levels of a node refers to the number of edges in the path from the root node to the node
• Height (Height) The height of the tree is equal to the maximum number of layers of all nodes

The definition of a tree

A tree is a collection of nodes and edges that connect nodes , It has the following characteristics ：

• One node is designed as the root node
• Except for the root node , Each node is connected to its unique parent node by an edge
• You can follow a unique path from the root node to each node
• If each node of the tree has at most two child nodes , be called Binary tree

0x03 Binary tree

The definition of binary tree

• A binary tree is composed of n(n≥0) A finite set of nodes 、 An ordered tree with at most two subtrees per node . It's either an empty set , Or a root sum called left 、 Two disjoint binary trees of the right subtree .
• Degree of node and degree of tree The number of subtrees each node has is called the degree of the node , The maximum degree of all nodes in a tree is called the degree of the tree
• The degree of binary tree is 2

Characteristics of binary trees

• A binary tree is an ordered tree , Even if there is only one subtree , It is also necessary to distinguish between the left 、 Right subtree ;
• The degree of each node of a binary tree cannot be greater than 2, Can only take 0、1、2 One of the three
• There are five forms of all nodes in a binary tree : Empty node 、 Nodes without left and right subtrees 、 Only the nodes of the left subtree 、 Only nodes of right subtree and nodes with left and right subtrees

Properties of binary trees

• The second order of binary tree i Layer has at most 2^i-1 Nodes
• Any binary tree T, If the number of leaf nodes is N0, Degree is 2 The node number of is N2, be N0=N2-1
• Full binary tree ： When every layer of the tree is full , The tree is called a full binary tree .
• Perfect binary tree ： In a binary tree , Except for the last floor , If the rest of the layers are full , And the last layer is either full , Or there are several consecutive nodes missing on the right , This tree is called a complete binary tree
• Full binary tree is a special case of complete binary tree
• Depth is h The number of nodes of the full binary tree is 2^h-1

Traversal of binary tree

Access all nodes in the tree in a certain order , And the value of each node is accessed only once

• There are three possible traversal orders
  • The first sequence traversal ： First visit the root node and then traverse the left subtree , Finally, traverse the right subtree
  • In the sequence traversal ： Middle order traversal first traverses the left subtree , Then access the root node , Finally, traverse the right subtree
  • After the sequence traversal ： First, traverse the left subtree , And then I go through the right subtree , Finally, visit the root node