Definition and basic terms of tree

The basic concept of tree

Trees ： yes n(n≥0) A finite set of nodes T. In any non-empty tree ：
① There is and there is only one particular node , It's called the root of the tree (root), It doesn't have a direct precursor , But there are zero or more direct successors .
② rest n-1 Nodes can be divided into m(m≥0) A finite set that doesn't intersect each other T1,T2,…Tm, among Ti Another tree , A subtree called a root . The definition of a tree is recursive , namely “ There are trees in the trees ”.
Diagram of the logical structure of the tree ： Like an inverted tree

A graphical representation of a tree

① Inverted tree structure representation （ Tree representation ）

② Venn diagram representation （ Nested set representation ）

③ Generalized table representation （ Nested bracket notation ）
(A(B(E(K,L),F),C(G),D(H(M),I,J)))
④ Indentation notation

Tree related terms

node ： That is, the elements in the tree , Contains its own information and branch information pointing to other nodes .
The degree of node ： The number of the node tree .
The degree of a tree ： The maximum degree of all nodes in the tree .

leaf node ： Degree is 0 The node of , Terminal node , Leaf node for short 、 leaf .
Branching nodes ： The degree is not for 0 The node of , That is, non terminal nodes .
The hierarchy of nodes ： We start at the root , The level of the root node is 1, The immediate successor level of the root is 2, And so on .
The height of the tree ( depth )： The maximum value of the hierarchy of all nodes in the tree .
children ： Direct successor node .
Parents ： Direct precursor node .
brother ： Nodes with the same parents .
male cousins ： Nodes of the same layer that are not siblings .
The ancestors ： All nodes on the path from the root to the node .
descendants ： Direct and indirect successor nodes .
predecessors ： A node with a layer number smaller than this node .
Junior ： Nodes with a layer number larger than this node .
Ordered trees ： In the tree T in , If each subtree Ti In order of precedence , It's called an ordered tree .
isomorphism ： For two trees , By renaming the node appropriately , You can make the two trees exactly equal （ The nodes correspond to each other , The correlation of corresponding nodes is also equal ）.
example ： have 3 Ordered trees with different nodes have a total of 5 Kind of ：

The forest ： m(m≥0) A collection of disjoint trees . Delete the root node of a non empty tree , The tree becomes a forest ; conversely , Add a unified root node to the forest , The forest becomes a tree .

Abstract data type definition of tree

ADT Tree{
    
 Data objects ： Element set D, Element properties are the same .
 Data relation ： if D It's empty , Empty tree ; if D Contains only one element , be R It's empty ; otherwise R={
    H}, Binary relationship H={
    < node , children >,...,< node , children >}, Root node root There is no precursor , Other nodes have only one precursor , Subsequent nodes can have zero or more .
 Basic operation ： On the set of tree operations .
}ADT Tree;

D = { A,B,C,D,E,F,G,H,I,J,K,L,M }
R = { H }
H = { <A,B>,<A,C>,<A,D>,<B,E>, <B,F>,
<E,K>,<E,L>,<C,G>, <D,H>,<D,I>,<D,J>,
<H,M> }

Welcome to join me for wechat exchange and discussion （ Please note csdn Add ）