Wondershare EdrawMind
MindMap Gallery Data Structure Chapter 5 Tree
- 21
Data Structure Chapter 5 Tree
Data Structure Chapter 5 Summary of tree knowledge, including empty trees and non-empty trees, nodes, paths, horizontal comparisons between trees and nodes, properties of trees, types of trees, etc.
Edited at 2022-08-10 17:15:31
- Recommended to you
- Outline
Chapter 5 Tree
1. Empty tree and non-empty tree
empty tree
The number of nodes is 0
non-empty tree
There is only one root node
Nodes without successor nodes are called "leaf nodes"
Nodes that have successor nodes are called "branch nodes"
Except for the root node, any node has exactly one predecessor.
Any node can have 0 or more successors
2. Node
ancestor node
Descendants node
Parent node: the direct predecessor of a node
Child node: the direct successor of a node
Sibling nodes: nodes on the same level
Cousin node: Node at the same level that is not a parent node
3. path
Paths between nodes: counting from top to bottom, how many edges have been passed, then what is the length of the path?
Tree path: sum of all path lengths
4. Horizontal comparison of trees and nodes
Node
Height: calculated from bottom up
Degree: How many children (branches) there are, what is the degree?
Depth: Calculated from top to bottom, the default depth is 1, but some questions will default to 0
Tree
Height (depth) of the tree: how many layers there are in total
Degree: The maximum value of the degrees of all nodes is the degree of the tree
Path: The path of a tree is the sum of the lengths of all paths
The maximum value of the height (depth) of all nodes is the height (depth) of the tree
What needs special attention is that the degree of the tree is the maximum value of the degrees of all nodes, but the path of the tree is the sum of all lengths.
5. tree nature
The number of nodes in the tree = the sum of the degrees of all nodes + 1
tree of degree M
1. The degree of any node＜=M
2. There is at least one node with degree M
3. It must be a non-empty tree with at least M 1 nodes (when there is only a root node and the root node degree is M)
4. A tree with height h and degree M has at least h M-1 nodes.
M-ary tree (each node has at most M children)
1. Can be an empty tree
2. Allow the degree of all nodes <= M
3. An M-ary tree with height h has at least h nodes.
4. An M-ary tree with height h has at most (M^h-1)/(M-1) nodes.
5. The minimum height of an M-ary tree with n nodes is
The tree with degree M and the i-th level of the M-ary tree (i<=1) have at most M i-1th power nodes.
6. tree type
Ordered tree: Each subtree in the tree is ordered from left to right and is not interchangeable.
Unordered tree: the subtrees of the tree are unordered and interchangeable
Binary tree
1. Features: Each node has at most two subtrees (that is, there is no node with degree greater than 2 in the binary tree), and the binary tree is divided into left and right, and the order cannot be reversed.
2. Several special binary trees
full binary tree
Definition: A binary tree with a height of h and 2^h-1 nodes is called a full binary tree (actually, each level of the tree contains the most nodes, that is, every node except the leaf nodes The degrees of are all 2)
Features
1. All leaf nodes of a full binary tree are at the bottom level
2. Start numbering the full binary tree from top to bottom and from left to right. Then for the node numbered i, its left child node is 2i, its right child node is 2i 1, and its parent node is i/2 rounded
3. There is no node with degree 1
complete binary tree
Definition: A binary tree with height h and n nodes is called a complete binary tree if and only if each node exactly corresponds to the nodes numbered 1~n in the full binary tree with height h.
Features
1. Leaf nodes only appear on the two layers with the largest number of layers.
2. If there is a node with degree 1, there can only be 1
3. Start numbering the complete binary tree from top to bottom and from left to right. Then for the node numbered i, its left child node is 2i, its right child node is 2i 1, and its parent node is i/2 rounded
4. Once a node with number i is a leaf node or has only a left child, then the nodes with number greater than i are all leaf nodes.
5. If i<=n/2, then node i is a branch node, and the others are leaf nodes (a complete binary tree has 1001 nodes, 1001/2=500, that is, 500 branch nodes, and the other 501 are leaf nodes. )
6. The height of a complete binary tree with n nodes (full binary tree) is log2(n 1) or
7. For a complete binary tree, the number of nodes with degrees 0, 1, and 2 can be inferred from the number of nodes n.
If there are 2k nodes, there must be n1=1, n0=k, n2=k-1
If there are 2k 1 nodes, there must be n1=0, n0=k, n2=k-1
Binary sorting tree
balanced binary tree
3. Properties of binary trees
1. The number of leaf nodes of a non-empty binary tree is equal to the number of nodes with degree 2 1, that is, n0=n2 1
2. A non-empty binary tree (including full binary tree and complete binary tree) has at most nodes on the kth level.
3. A non-empty binary tree with height h (including full binary tree and complete binary tree) has at most (2^h)-1 nodes.
4. A binary linked list with n nodes contains n 1 empty link fields.
4. Binary tree storage structure
5. Binary tree traversal
1. Preorder traversal (around the root)
2. In-order traversal (left root right)
3. Postorder traversal (left and right roots)
4. Level traversal (the binary tree is traversed layer by layer)
5. Derivation of binary tree structure from traversal sequence
The sequence combination that can uniquely determine a binary tree
Hit first
After the middle
in layer
The sequence combination of a binary tree cannot be uniquely determined
Without inorder traversal, a unique binary tree cannot be inferred
6. clue binary tree
Significance: The purpose of the clue binary tree is to speed up the process of finding the predecessor and successor of a node.
Node structure: lchild* ltag data rtag rchild*
tag flag field
When tag=0, child points to the left (right) child
When tag=1, child points to the predecessor (successor)
The predecessor and successor of a clue binary tree depends on what kind of traversal it is
7. trees and forests
tree storage structure
parent representation
Use a continuous space to store each node, and add a pseudo pointer to each node to indicate the position of its parent node in the array.
Features: It is easy to find parents, but difficult to find children.
child representation
The child representation is to link the child nodes of each node with a single linked list to form a linear structure. At this time, if there are n nodes, there will be n child linked lists. (The child list of leaf nodes is an empty list)
Features: It is easy to find children, but it is difficult to find parents.
List of children with parents
Child brother representation (important)
This method is also called binary tree representation, which can easily convert a tree into a binary tree (left child, right brother)
Conversions between trees, forests and binary trees
1. Convert tree to binary tree
1) Add a line: Add a line between brothers 2) Erase: For each node, except for its left child, remove the relationship between it and the remaining children. 3) Rotation: Taking the root node of the tree as the axis, rotate the integer 45 degrees clockwise. Memory Tip: Brothers stay together until they have the eldest son The process is as follows: Add line -> Erase line -> Rotate
2. Convert binary tree to tree
step: 1) Add a line: If a node is the left child of its parents, connect the right child of the node, the right child of the right child, etc. with the parent nodes of the node with a line. 2) Erase: delete all connections between parent nodes and right child nodes in the original binary tree 3) Adjustment: Arrange the tree obtained in the first two steps, that is, take the node as the axis and rotate it 45° counterclockwise to make the structure hierarchical. Memorization formula: connect the left child with the right child and remove the original line from the right child The process is as follows: Add line->Erase line->Adjust (rotate)
3. Convert forest to binary tree
(1) First convert each tree into a binary tree; (2) The first binary tree does not move. Starting from the second binary tree, the root node of the latter binary tree is used as the right child node of the root node of the previous binary tree and connected with lines. When all binary trees are connected, the resulting binary tree is the binary tree obtained by forest conversion.
4. Convert binary tree to forest
Converting a binary tree to a forest is relatively simple. The steps are as follows: (1) First delete the connection between each node and the right child node to obtain a separated binary tree; (2) Convert each separated binary tree into a tree; (3) Organize the trees obtained in step (2) and standardize them, thus obtaining the forest
Traversal of trees and forests
tree traversal
Root traversal first
Visit the root node first, and then visit each subtree of the root node. When traversing the subtree, you still follow the rule of root first, then subtree.
Its traversal sequence is the same as the preorder sequence of the binary tree corresponding to this tree.
back root traversal
Visit each subtree first, then visit the root node. When traversing the subtree, you still follow the rule of root first, then subtree.
Its traversal sequence is the same as the in-order sequence of the binary tree corresponding to this tree.
Level traversal
Basically the same idea as binary tree level traversal
Traveling through the forest
Preorder traversal of the forest
Visit the root node of the first tree in the forest, first traverse the forest of subtrees of the root node in the first tree, and finally traverse the forest composed of the remaining trees after excluding the first tree.
Traversing the forest in sequence
In-order traverses the sub-tree forest of the root node of the first tree in the forest, then visits the root node of the first tree, and finally in-order traverses the forest composed of the remaining trees after excluding the first tree.
8. Huffman tree
Definition: Among the binary trees with n weighted nodes, the tree with the smallest weighted path (WPL) is the Huffman tree.
The weighted path of the node
The product of the number of edges from the root of the tree to any node and the weight of the node is the weighted path length of the node.
The structure of Huffman tree
Characteristics of Huffman tree
1. Each initial node becomes a leaf node, and the smaller the weight, the greater the path length from the node to the root node.
2. A total of N-1 new nodes (double-branch nodes) are created during the construction process, so the total number of nodes in the Huffman tree is 2N-1.
3. Each construction selects 2 trees as the children of the new node, so there is no node with degree 1 in the Huffman tree.
9. And search the collection
Definition: Union-find is a tree model, mainly used to solve some element grouping problems. It manages a series of disjoint sets
Storage structure (very similar to parent notation)
You can use the absolute value of the root node S[] to represent how many nodes there are under it.
Find and Union operations
Find: Search the value of S[] upwards from the target node until a node with S[] of -1 is found, which is the root node. The time complexity is O(n)
Union: Just change the S[] of the root node of one tree to the subscript of the root node of another tree. The time complexity is O(1)
Optimization of Find operation (compressed path)
Every time you search, the root node is found first, and then all nodes on the path are hung under the root node.
central theme
theme
theme
theme