1. The definition of a tree

Trees (Tree) yes n(n≥0) A finite set of nodes .n=0 Time is called empty tree . In any non-empty tree :
( 1) There is and only one specific one called a root ( Root ) The node of ;
(2) When n>1 when , The rest of the nodes can be divided into m(m>0 ) A finite set that doesn’t intersect each other T1、T2、… Tm, Each set itself is a tree , And called the root of the subtree ( SubTree ), As shown in the figure below .


Two more points need to be emphasized for the definition of the tree :

• n>0 When the root node is unique , It is impossible to have multiple root nodes , Don’t mix with the big trees in reality , Real trees have many roots , It’s a real tree , A tree in a data structure can only have one root node .
• m>0 when , There is no limit to the number of subtrees , But they must be disjoint . The two structures like the following figure do not meet the definition of the tree , Because they all have intersecting subtrees .
  

2. Node classification

The node of the tree Contains a data element and branches that point to its subtree . node The number of subtrees owned is called the degree of nodes (Degree). Degree is 0 The nodes of are called leaf nodes (Leaf) Or terminal node ; The degree is not for 0 The nodes of are called non terminal nodes or branch nodes . Remove the root node outside , Branch nodes are also called internal nodes . The degree of a tree Is the maximum degree of each node in the tree . As shown in the figure below , Because the maximum degree of this tree node is node D Degree , by 3, So the degree of the tree is also 3.

3. The relationship between nodes

The root of a node’s subtree is called the child of the node (Child), Accordingly , This node is called the parents of children (Parent). Why not father or mother , It’s called parents ? For a node, its parents are the same , The only one , So we can only call it parents .
Children of the same parents call each other brothers (Sibling). The ancestor of a node is all nodes from the root to the branch it passes through . So for H Come on ,D、B、A Are its ancestors . conversely , Any of the subtrees rooted at a node – Nodes are called descendants of the node .B There are D、G、H、I, As shown in the figure below .

3. Other related concepts of trees

The hierarchy of nodes (Level) Starting from the root , Root first – layer , The child of root is the second layer . If a node is at 1 layer , Then the root of its subtree is at l+1 layer . Their parents are in the same – The nodes of the layer are cousins to each other . Obviously… In the picture below D、E、F It’s cousins , and G、H、I、J It’s also . The maximum level of nodes in a tree is called the depth of the tree (Depth) Or height , The depth of the current tree is 4.

4. Comparison of linear table and tree

5. Summary of some terms about trees

• node ： A data element in the tree .
• The degree of node (degree)： The number of any node subtree , Write it down as d(v).
• leaf (leaf)： Degree is 0 The node of , Also known as end node .
• Branching nodes ： The degree is not for 0 The node of , Also known as non end node .
• Branch ： The relationship between nodes .
• Internal nodes ： Except for the root Branching nodes .
• The degree of a tree ： The maximum node degree in the tree .
• children ( son ) ： The root of a node’s subtree is called the child of the node ( The subsequent )
• Parents ( father ) ： A node is the parent of the root node of its subtree ( Forward trend )
• brother (sibling)： Nodes with the same parents .
• The ancestors ： All nodes on the path from the root node to the node are called the ancestors of the node .
• descendants ： The nodes on all subtrees of the node are called the descendants of the node .
• The hierarchy of nodes ： The root node is defined as the 1 layer , The son of root is defined as the 2 layer ,…, By analogy . Write it down as L(v).
• Depth of tree ( Height ) ： The maximum value of each node level .
• male cousins ： Nodes where parents are on the same layer .
• Ordered trees ： The subtrees of nodes are sequential ( Brothers are big and small 、 In order )
• route ： In the tree k Each node nl ,n2… ,nk, Satisfy ni yes ni+1 My parents , call n1 To nk There is a way. path .
• The length of the path ： Number of branches = Number of nodes on the path – 1
  Be careful ： Root has no parents , Leaves have no children ;
  vi yes vj My parents , be L(vi)=L(vj)-1;
  Are cousins’ parents brothers ? not always .

5. Common representations of trees

1. Visual representation
The nodes are represented by circles , Elements are written in circles , The connection indicates that the relationship between elements is rooted in , The leaves are under ( That is, the tree grows down ）

2. Set representation :
According to the set definition of the tree , Write the set partition .

3. Venn diagram representation :
A visual representation of a set representation , Use a graph to represent a set

4. Directory notation :
Describe a tree as a Book , book – Chapter – section – Section –

5. Generalized table The demonstration :
Describe a tree as a generalized table , The subtree corresponds to the sub table .

The first one is most commonly used , But it’s not suitable for computers !