Double non undergraduate students enter the factory, while I am still quietly climbing trees at the bottom (Part 1)

Individuality signature ： The most important part of the whole building is the foundation , The foundation is unstable , The earth trembled and the mountains swayed . And to learn technology, we should lay a solid foundation , Pay attention to me , Take you to firm the foundation of the neighborhood of each plate .
Blog home page ： Qigui's blog
special column ： data structure （C Language version ）
From the south to the North , Don't miss it , Miss this article ,“ wonderful ” May miss you la
Code , There are notes ！！！
Triple attack( Three strikes in a row ):Comment,Like and Collect—>Attention

Three elements of data structure ： Logical structure 、 The operation of data 、 Storage structure （ Physical structure ）. The storage structure is different , The operation is implemented in different ways .

1、 Trees

1.1、 Basic concepts

Trees are $n(n\ge 0)$ A finite set of nodes ,n=0 The number of instant settlement points is 0, It's called the empty tree .
Any non empty tree should meet ：

• There is and only one specific node called root
• When n>1 when , The rest of the nodes can be divided into m（m>0） A finite set of disjoint , Each of these sets is itself a tree , And called the subtree of the root node .

The characteristics of non empty trees ：

• There is only one root node
• Nodes without successors are called leaf nodes
• A node with a successor is called a branch node
• Except for the root node , Any node has only one precursor
• Each node can have 0 One or more successors

Logical representation of tree ：

• Tree representation
• Venn diagram representation
• Indentation notation
• Bracket notation

1.2、 Basic terminology

1.2.1、 Description of the relationship between nodes

• Ancestral node
• Children's node
• Parents node （ Parent node ）
• Child node
• Brother nodes
• Cousin node
• route ： The path between two nodes can only be from top to bottom
• The length of the path ： Pass by several sides

1.2.2、 Attribute description of nodes and trees

attribute ：

• The hierarchy of nodes （ depth ）—— Count from top to bottom （ The default from the 1 Start ）
• The height of the node —— Count from the bottom up
• The height of the tree （ depth ）—— How many floors in total
• The degree of node —— There are several children （ Number of branches ） notes ： Degree of non leaf node >0, Degree of leaf node =0
• The degree of a tree ： The maximum value of the degree of each node

1.2.3、 Ordered trees 、 Disordered trees

Logically , Whether the sub trees are in order , Whether the positions are interchangeable
Judge ： It depends on what is stored in the tree , Whether it is necessary to use the left and right positions of nodes to reflect some logical relations

• Ordered trees ： Logically , The subtrees of the nodes in the tree are ordered from left to right , Not interchangeable
• Disordered trees ： Logically , The subtrees of the nodes in the tree are unordered from left to right , interchangeable

1.2.4、 The forest

The forest is $m(m\ge 0)$ A collection of disjoint trees .

1.3、 Properties of trees

• 1、 Number of nodes = Total degree +1
  The degree of node —— How many children do you have （ Number of branches ）

• 2、 Degree is m Number of numbers 、m The difference between fork trees

  • Degree is m The tree of
    • At least one node degree =m
    • It must be a non empty tree
  • m Fork tree
    • The degree of all nodes is allowed to be <m
    • It could be an empty tree

• 3、 Degree is m The tree of i Layer up to have a $m^{i-1}$ Nodes （$i\ge 1$）
  m Fork tree —— The first i Layer up to have a $m^{i-1}$$individualjunctionspot（i\ge 1$）

• 4、 The height is h Of m A fork tree has at most $\frac{m^h-1}{m-1}$ Nodes

• 5、 The height is h Of m Fork trees have at least m*h-1 Nodes
  The height is h、 Degree is m The trees of at least h+m-1 Nodes

• 6、 have n Of nodes m The minimum height of the fork tree is $\lceil lo{g}_m(n(m-1)+1)\rceil$

2、 The storage structure of the tree

2.1、 Parenting （ Sequential storage ）

Store each node in sequence , Each node stores the information pointing to the parents “ The pointer ”.

• advantage ： It is convenient to check the parents of the specified node
• shortcoming ： The child who checks the specified node can only traverse from the beginning
• Empty data leads to slower traversal

#define MaxSize 100
typedef struct
{
    
	ElemType data;		// Store the value of the node 
	int parent;			// Where to store your parents 
}PTree[MaxSize];		//PTree Storage structure type for both parents 

2.2、 Child representation （ The order + Chain store ）

Store each node in sequence , Save the child chain header pointer in each node

• advantage ： It's convenient to find children , It is convenient for computers to specify the degree of nodes
• shortcoming ： It is inconvenient to find the parent node

MaxSons Number of nodes for the most children , Or the degree of the tree .

typedef struct
{
    
	ElemType data;			// The value of the node 
	struct node *sons[MaxSons];		// Point to the child node 
}TSonNode;			// Node type in child chain storage structure 

2.3、 Child brother notation （ Chain store ）

Store the tree with a binary linked list —— Left child right brother
Design for each node 3 Domains ：

• A data element field
• The first child node to the left of the node （ eldest son ） A pointer to the domain
• A pointer field that points to the next sibling of the node

The storage structure of child brother chain is actually the storage structure that converts the tree into a binary tree

typedef struct tnode
{
    
	ElemType data;			// The value of the node 
	struct tnode *hp;		// Point to brother 
	struct tnode *vp;		// Point to the child node 
}TSBNode;			// The node type of child brother chain storage structure 

2.4、 Trees 、 The conversion of forest and binary tree

The essence ： Use a binary linked list to store the forest —— Left child right brother . The root nodes of each tree in the forest are regarded as brothers

2.4.1、 The forest 、 The tree turns into a binary tree

• Add a line between all the neighboring brothers in the tree
• For each node in the tree, only the connection between it and the eldest child is reserved , Delete the connection with other children
• Take the root node of the tree as the axis , Turn the whole tree clockwise 45°, Make it structured

2.4.2、 A binary tree is reduced to a forest 、 Trees

• If a node is the left child of its parents , Then the right child of the node 、 The right child of the right child is connected with the parent node of the node by connecting
• Delete the connection between all parent nodes and right child nodes in the original binary tree
• Sort out the tree obtained from the previous two steps , That is, take the root node as the axis , Turn it counter clockwise 45°, Make it structured

3、 Trees 、 The traversal of the forest

3.1、 Tree traversal

The traversal operation of the tree refers to accessing all nodes in the tree in a certain way, and each node is accessed only once . Tree traversal mainly includes root traversal 、 Post root traversal and hierarchical traversal . Be careful ： The first root traversal and the second root traversal of the tree are recursive .

3.1.1、 First root through

If the tree is not empty , So let's go to the root , Then traverse the roots of each subtree in turn

3.1.2、 Back root traversal （ Depth-first traversal ）

If the tree is not empty , First, traverse the root of each subtree in turn , Finally, access the root node . The back root traversal sequence of the tree is the same as the middle sequence of the corresponding binary tree of the tree

3.1.3、 Level traversal （ Breadth first traversal ）

1. If the tree is not empty , Then the root node joins the queue ;2. If the queue is not empty , The team leader element goes out of the team and visits , At the same time, join the children of this element in turn ;3. repeat 2 Step until the queue is empty .（ Implement... With queues ）

3.2、 The traversal of the forest

3.2.1、 The first sequence traversal

If the forest is not empty , Then traverse according to the following rules ：
Visit the root of the first tree in the forest ; Traversing the subtree forest of the root node of the first tree ; First, we traverse the forest made up of the remaining trees after the first tree is removed .

3.2.2、 In the sequence traversal

If the forest is not empty , Then traverse according to the following rules ：
Traversing the subtree forest of the root node of the first tree in the forest ; Visit the root of the first tree ; The middle order traverses the forest made up of the remaining trees after the first tree is removed .