A tree is a nonlinear data structure, a hierarchical structure defined in terms of branching relationships, and thus morphologically resembles an upside-down tree in nature, whereas the root of the tree goes up and the leaves go down in a data structure.
What's a tree?
01Definitions
A tree is a finite set of n (n>=0) elemental nodes, and when n=0, it is called an empty tree.
The following requirements shall be satisfied for non-empty trees:
(1) There is and only one root node;
(2) When n>1, the remaining nodes can be divided into m (m>=0) finite sets that do not intersect with each other, where each set is in turn a tree by itself, called the root's subtree.
From the definitions we can draw the following conclusions:
1) Trees are branching hierarchical structures;
2) Only the root node has no parent node in the tree;
3) Except for the root node, the remaining nodes have one and only one parent;
4) Each node in the tree, can have zero or more children;
5) There is one and only one path from the root node to any node other than itself;
02Terminology
1. Node-related
root node: There exists only one root node in the tree, located at the topmost level of the tree, and it has no parent node;
leaf node: The leaf node is located at the very end of the tree and does not have any nodes in its lower levels.
child node: The lower nodes of a given node, relative to that node are called child nodes;
parent node: The upper node of a node, relative to that node is called the parent node;
2. Structure-related
(of a speech etc) profundity: The number of edges that pass from the root node to a given node; the root node is 0, its children are 1, and so on from the top down.
high degree: The number of edges from a node to its farthest leaf node. The height of the tree is the height of the root node, all leaf nodes are of height 0, their parent nodes are 1, and so on from the bottom up.
arrangement of ideas: Refers to the level at which the node is located, with the root node being level 0, its children being level 1, and so on from the top down.
subtree: Any tree structure in which some node is the root node in a tree.
3. Relationship-related
sibling node: A child node that has a common parent.
ancestor node: All nodes experienced on the path from the root node to this node, including parent nodes, grandfather nodes, etc., in addition to itself.
successor node: All lower nodes of this node, including children, grandchildren, etc.
4. Other terms
Tree Degrees: refers to the width of the tree, which can also be interpreted as the number of branches of a node, i.e., the number of direct children of a node, and the maximum value of the degree among all the nodes is considered as the degree of the tree;
Paths and path lengths: The sequence of all edges experienced from one node to another is the path, and the number of all edges on the path is the path length;
deforestation: Refers to a collection of several trees that do not intersect each other;
03binary tree
Based on the number of nodes we can classify trees into two categories: binary trees and N-fork trees.
binary tree: A tree with at most two children per node;
forked tree: A tree with at most n children per node;
One of the most commonly used is the binary tree, let's talk about binary trees in detail.
1. Definitions
(1) Each node has at most two children, called left and right child nodes;
(2) Both the left and right subtrees formed by the left and right child nodes are also binary trees;
2. Nature
(1) Any binary tree tree, if the number of nodes is n, the number of edges is n-1;
(2) In a binary tree, the ith level has at most 2^i nodes;
(3) A binary tree of depth k with a total number of nodes of at least 2k nodes with at most 2(k+1)-1 nodes;
(4) In a non-empty binary tree, if n0 denotes the number of leaf nodes and n2 denotes the number of nodes of degree 2 (i.e., with two nodes), then n0 = n2 + 1;
3. Iteration
Binary tree traversal refers to accessing all nodes in a binary tree in a specific order, and commonly used traversal methods include: preorder traversal, intermediate traversal, postorder traversal, and hierarchical traversal.
preorder traversal
access order: root node - > left subtree - > right subtree
move：
(1) Access to the root node;
(2) Pre-order traversal of the left subtree;
(3) Pre-order traversal of the right subtree.
schema：
medium-order traversal
access order: left subtree - > root node - > right subtree
move：
(1) Middle-order traversal of the left subtree;
(2) Accessing the root node;
(3) Middle-order traversal of the right subtree.
schema：
backward traversal
access order: left subtree - > right subtree - > root node
move：
(1) Post-order traversal of the left subtree;
(2) Post-order traversal of the right subtree;
(3) Access to the root node;
schema：
hierarchical traversal
access order: Layer 0 - > Layer 1 - > ...... - > Layer n (each layer is treated in order from left to right)
move：
(1) Initialization: create an empty queue and add the root node to the queue;
(2) Traversal:
When the queue is not empty:
Takes a node from the queue and accesses the value of that node;
If the node has a left child, add the left child to the queue;
If the node has a right child, add the right child to the queue;
(3) Repeat step 2 until the queue is empty;
schema：
classifier for sums of money: The test method code as well as the sample source code have been uploaded to the code repository for those who are interested./hugogoos/Planner