Definition and basic terms of tree

The definition of a tree

Start from a node called the root node , Then each branch grows in turn , A new node can be connected to each branch , Branches can be called edges ; The orange node in the figure has branches at the next level , Nodes like this can be called branch nodes ; The green node has no other branches below , It can be called leaf node .

Empty tree

The number of nodes is 0 The tree of , There is no node .

Not empty trees

1. There is only one node
2. Nodes without successors are called “ leaf node ” （ Or terminal node ）
3. Nodes with successors are called “ Branching nodes ” （ Or non terminal node ）
4. Any node except the root node There is and only one Forerunner
5. Each node can have 0 One or more successor nodes

subtree

Pictured above A Is the root node , It can be said that this root node has three sub trees , And the three subtrees are disjoint .

The subtree can be regarded as a new tree , Pictured above ,B The node becomes the root node of the tree , This tree can also be divided into two disjoint subtrees , The subtree on the right has only one node , The tree on the right can be regarded as a root node , At the same time, its sub trees are all empty trees .

Therefore, we can see that the tree is a recursively defined data structure , Any tree can be regarded as composed of root nodes and several disjoint subtrees .

Basic terminology

Ancestral node ： Starting from a node , Keep going up , Until you reach the root node , All nodes on this path are the ancestors of this node .

Children's node ： Starting from a node , The nodes under his branches are all his descendants .

Parents node ( The parent node )： The direct precursor of a node .

Child node ： The direct successor of a node .

Brother nodes ： These nodes of a father .

Cousin node ： Other nodes in the first layer except brother nodes .

route ： You can only go in one direction （ From the top down ）.

The length of the path ： Passed several sides .

Attribute description of nodes and trees

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 are there in total

The degree of node ： There are several children （ Branch ）

The degree of a tree ： The maximum value of each node degree

The degree is greater than 0 The node of is the branch node , It can also be called non leaf node ( Non terminal nodes ); Degree is 0 The node of is the leaf node ( Terminal node ).

Ordered trees and unordered trees

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

Disordered trees ： Logically , The subtrees of nodes in the tree are unordered from left to right ( The left and right positions of nodes do not reflect some logical relationships ), interchangeable .

The forest

from M A collection of disjoint trees , If these trees are connected to the same root node , The forest will become a tree .