Wondershare EdrawMind
MindMap Gallery Data structure_5 tree
- 25
Data structure_5 tree
Refer to Wangdao Computer Postgraduate Entrance Examination's "Data Structure" to independently summarize the knowledge points and share the necessary review materials, so that everyone can read and review when preparing for the exam and improve the review efficiency. I hope it will be helpful to everyone in preparing for the exam.
Edited at 2024-03-31 11:32:11
- Valentine's Day marketing campaign
This Valentine's Day brand marketing handbook provides businesses with five practical models, covering everything from creating offline experiences to driving online engagement. Whether you're a shopping mall, restaurant, or online brand, you'll find a suitable strategy: each model includes clear objectives and industry-specific guidelines, helping brands transform traffic into real sales and lasting emotional connections during this romantic season.
- 30 Creative Ideas for Valentine's Day
This Valentine's Day map illustrates love through 30 romantic possibilities, from the vintage charm of "handwritten love letters" to the urban landscape of "rooftop sunsets," from the tactile experience of a "pottery workshop" to the leisurely moments of "wine tasting at a vineyard"—offering a unique sense of occasion for every couple. Whether it's cozy, experiential, or luxurious, love always finds the most fitting expression. May you all find the perfect atmosphere for your love story.
- Milano Cortina 2026 Ice Hockey Schedule
The ice hockey schedule for the Milano Cortina 2026 Winter Olympics, featuring preliminary rounds, quarterfinals, and medal matches for both men's and women's tournaments from February 5–22. All game times are listed in Eastern Standard Time (EST).
Data structure_5 tree
- Valentine's Day marketing campaign
This Valentine's Day brand marketing handbook provides businesses with five practical models, covering everything from creating offline experiences to driving online engagement. Whether you're a shopping mall, restaurant, or online brand, you'll find a suitable strategy: each model includes clear objectives and industry-specific guidelines, helping brands transform traffic into real sales and lasting emotional connections during this romantic season.
- 30 Creative Ideas for Valentine's Day
This Valentine's Day map illustrates love through 30 romantic possibilities, from the vintage charm of "handwritten love letters" to the urban landscape of "rooftop sunsets," from the tactile experience of a "pottery workshop" to the leisurely moments of "wine tasting at a vineyard"—offering a unique sense of occasion for every couple. Whether it's cozy, experiential, or luxurious, love always finds the most fitting expression. May you all find the perfect atmosphere for your love story.
- Milano Cortina 2026 Ice Hockey Schedule
The ice hockey schedule for the Milano Cortina 2026 Winter Olympics, featuring preliminary rounds, quarterfinals, and medal matches for both men's and women's tournaments from February 5–22. All game times are listed in Eastern Standard Time (EST).
- Recommended to you
- Outline
Tree
Traversal of trees and forests
Notice
The order of accessing subtrees is from left to right.
Branch nodes in ordinary trees and forests do not necessarily have only two subtrees. Understand that tree traversal and forest traversal can no longer be limited to the root.
tree traversal
depth first traversal
Root traversal first
meaning
1. If the tree is not empty, visit the root node first, and then traverse each subtree of the root node in sequence (left → right)
2. When traversing subtrees, the principle of root first and then subtrees is still followed.
Identical to the preorder sequence of the corresponding binary tree (child sibling notation) of this tree
back root traversal
meaning
1. If the tree is not empty, first perform a post-root traversal on each subtree in turn, and finally visit the root node.
2. When traversing subtrees, we still follow the principle of root first (left and right subtrees) and then root.
Is the same as the inorder sequence of the corresponding binary tree (child sibling notation) of this tree
breadth-first traversal
Level-order traversal (implemented using queues)
If the tree is not empty, the root node is added to the queue
If the queue is not empty, the head element is dequeued and accessed. At the same time, add the children of the element to the queue in order (first left, right, then)
Traveling through the forest
preorder traversal
core
Visit the root node first, then access its corresponding subtree; still use the same rules for its subtrees
Visit the root node of the first tree in the forest
Pre-order traverse the subtree forest of the root node in the first tree
Preorder traversal of the forest consisting of the remaining trees after removing the first tree
It is equivalent to performing a root-first traversal of each tree in sequence.
It is equivalent to pre-order traversal of the binary tree (child brother method)
inorder traversal
core
Visit its corresponding subtree first, then visit the root node; still use the same rules for its subtrees
In-order traverse the subtree forest of the root node in the first tree
Visit the root node of the first tree in the forest
In-order traversal of the forest consisting of the remaining trees after removing the first tree
It is equivalent to performing a post-root traversal on each tree in sequence.
It is equivalent to performing an in-order traversal of the binary tree (child brother method) in sequence.
Tree, forest and binary tree traversal relationship
Pre-order traversal (forest) - root-first traversal (tree) - pre-order traversal of binary trees
In-order traversal (forest) - post-root traversal (tree) - in-order traversal of binary tree
a tree and forest
A forest is a collection of m disjoint trees.
A tree is a finite set of n nodes and satisfies the annotation conditions
After the root node of a tree is removed, its sub-trees form a forest.
tree storage structure
parent representation
sequential storage
Store node data sequentially (array)
The node stores the subscript of the parent node in the array.
Advantages: It is convenient to find the parent node; Disadvantages: It is inconvenient to find the children (traversing from the beginning)
Basic operations
Add/delete/check/supplement
child representation
sequence chain
Store node data sequentially (array)
The node stores the head pointer of the child list (a linked list composed of all children of the node)
Advantages: Convenient to find children; Disadvantages: Inconvenient to find parent nodes
Representation of children's brothers (frequent test)
Use binary linked list to store tree - left child and right brother
The tree stored in child sibling representation is similar in form to a binary tree from a storage perspective.
The essence of the mutual conversion between trees and binary trees is to store the tree using child sibling representation.
Forest to Binary Tree Conversion
Use binary linked list to store deep forest - left child and right brother
The root nodes of each tree in the forest are considered brothers.
Nature of regular exams
Test point 1
Number of nodes = total degree 1 (root node)
Test point 2
tree of degree m
There is at least one node with degree m
The number of nodes is at least m 1
m-ary tree
The degree of all nodes is ≤ m (there is no node with degree > 2)
Can be an empty tree
The difference between a tree of degree m and an m-ary tree
Test point 3
How many nodes does the i-th level of a tree of degree m have at most (each node has m subtrees)
Test point 4
How many nodes does an m-ary tree with height h have at most (each node has m subtrees)
Test point 5
How many nodes are there with height h and degree m?
What is the minimum number of nodes in an m-ary tree with height h?
Test point 6
What is the minimum height of an m-ary tree with n nodes? (Rounded up)
basic terminology
relationship between nodes
Parent node (parent node), child node
Ancestor nodes, descendant nodes
Brother nodes, cousin nodes (nodes on the same layer/parent nodes on the same layer)
path between nodes
Only from top to bottom
path length
How many edges does the path pass through?
Node and tree properties
Node level (depth) - counting from top to bottom
Height of node - counting from bottom to top
degree of node
The number of branches of the node (the number of children of a node in the tree)
degree of tree
The maximum degree of each node in the tree
Ordered tree V.S unordered tree
Whether the subtrees of the nodes in the tree are ordered and whether their positions are replaceable
forest
A forest consists of m (m≥0) disjoint trees
trees and forests
Delete the root node of the tree and it becomes a forest.
m independent trees plus a node, and these m trees are subtrees of the node (forest->tree)
Easy to make mistakes
Round up/down
Rounded up
Round down
What is the minimum height of an m-ary tree with n nodes? (Rounded up)
The height h of a complete binary tree with n (n>0) nodes <---->The level of the i-th node of the complete binary tree is
Round up (determined by right closing ≥)
Determined by the range of the number of nodes of a full binary tree with a height of h--a height of h-1 (open on the left and closed on the right)
Round down (determined by left closing ≥)
Determine the number of nodes of a complete binary tree with height h (left closed and right open)
Tree Applications
Binary Search Tree (BST, Binary Search Tree)
definition
Left subtree node value < root node value < right subtree node value
By default, two nodes are not allowed to have the same keywords.
Perform in-order traversal to obtain an increasing ordered sequence.
Find operation
Starting from the root node, search to the left if the target value is smaller, and search to the right if the target value is larger.
Algorithm ideas
If the tree is not empty, compare the target value with the root node value
If they are equal, the search is successful.
If it is less than the root node, search on the left subtree, otherwise search on the right subtree.
If the search is successful, the node pointer is returned; if the search fails, NULL is returned.
Code
Recursive implementation
Non-recursive implementation
insert operation
If the original binary sorting tree is empty, insert the node directly
cycle
If the key k is less than the root node, insert it into the left subtree
If the keyword k is greater than the root node, insert it into the right subtree
insert node
When a null pointer is encountered, insert the node (must be the left/right child pointer of the leaf node)
Notice
There are nodes with the same keyword in the tree, and the insertion fails. (BST does not allow two identical nodes)
The incoming pointer is a reference, and the pointer to the insertion position (its parent node pointer) needs to be modified.
Structure of BST
BST construction<--->BST insertion operation
Different keyword sequences can get the same BST or different BSTs.
Delete operation (most difficult)
First search to find the target node
target node
leaf node
Delete directly
branch node
If there is only one left subtree or right subtree, then the subtree of z becomes the subtree of the parent node of z.
There is a left subtree and a right subtree
analysis of idea
Then let the direct successor (or direct predecessor) of z replace z
Delete this direct successor (or direct predecessor) from the BST (change to ① or ②)
direct successor of z
The lower-left node in the right subtree of z (this node must not have a left subtree)
direct predecessor of z
The rightmost node in the left subtree of z (this node must not have a right subtree)
After deleting the node, the BST nature still needs to be maintained (Left subtree node value < root node value < right subtree node value)
Search efficiency analysis
In a search operation, the number of times a keyword needs to be compared is called the search length.
ASL
Search successful
Total search length/number of nodes
Search failed
Total search length/number of empty nodes
Finding empty nodes does not require comparing keywords (The search function has exited the loop when it encounters a null pointer and returns a null pointer)
Depends on the height of the tree, the best is O(log n), the worst is O(n)
Balanced binary tree (AVL tree)
concept
balancing factor
minimally unbalanced subtree
Implement f's downward-right rotation (its left child's left child rotates upward-right)
Achieve f to rotate downward to the left (its right child rotates upward to the left)
definition
The difference between the heights of the left subtree and the right subtree of any node in the tree (the balance factor of the node) does not exceed 1
Notice
The balance factor value of a balanced binary tree node can only be -1, 0, 1
As long as the absolute value of the balance factor of any node is greater than 1-->the tree is not a balanced binary tree
insert operation
Just like the binary sorting tree, find the appropriate position to insert
Newly inserted nodes may cause the balance factors of their ancestors to change, leading to imbalance.
Adjust imbalance PPT5.5_2
Find the minimum unbalanced subtree for adjustment, that is, the root of the minimum unbalanced subtree is A
LL
Inserting into the left subtree of A's left child causes A to be unbalanced
Turn A's left child right up
RR
Inserting into the right subtree of A's right child causes A to be unbalanced
Turn A's right child up-left
LR
Inserting into the right subtree of A's left child causes A to be unbalanced
Rotate the right child of A's left child first to the left and then to the right.
RL
Inserting into the left subtree of A's right child causes A to be unbalanced
Rotate the left child of A's right child first to the right and then to the left.
Search efficiency analysis
The minimum number of nodes nh contained in a balanced tree with depth h - recursive solution
The maximum depth of a balanced binary tree is O(log n) The average search length/time complexity of the search is O(log n)
Huffman tree
concept
Node rights
A numerical value with a specific meaning (such as indicating the importance of the node)
The nodes with authority are all leaf nodes.
The length of the weighted path of the node = the length of the path from the root to the node * the weight of the node
The weighted path length (WPL) of the tree = the sum of the weighted paths of all leaf nodes in the tree
Huffman tree (optimal binary tree)
Among the binary trees containing the given n weighted leaf nodes, the tree with the smallest WPL
Construct Huffman tree
Huffman coding
Binary tree
storage structure
Basic concepts, characteristics, properties
basic concept
definition
Or an empty binary tree
Or it consists of a root node and two disjoint left subtrees and right subtrees called roots.
Features
The left subtree and right subtree cannot be reversed (ordered tree)
The degree of any node ≤ 2
Binary tree V.S ordered tree with degree 2
Ordered tree of degree 2
node order
At least one node has degree = 2
Binary tree
node order
The degree of the node ≤ 2 (the degree of the node can all be < 2)
special binary tree
full binary tree
A binary tree with height h and 2^h-1 nodes
Features
Only the last layer has leaf nodes
There are no nodes with degree 1 (only nodes with degree 0/2)
Numbering starts from 1 in hierarchical order, node i
The left child is 2i
The right child is 2i 1
The parent node is [i/2] (the largest integer not greater than i/2 - rounded down)
complete binary tree
On the basis of a full binary tree, several nodes with higher numbers can be removed
Features
Only the last two layers have leaf nodes
There is at most one node with degree 1
Numbering starts from 1 in hierarchical order, node i
The left child is 2i
The right child is 2i 1
The parent node is ⌊i/2⌋ (the largest integer not greater than i/2 - rounded down)
n≤⌊n/2⌋ is a branch node, i>⌊n/2⌋ (≥⌊n/2⌋ 1) is a leaf node
Binary sorting tree
Left subtree keyword<root node keyword<right subtree keyword
Binary sorting tree can be used for sorting and searching elements
balanced binary tree
The depth difference between the left and right subtrees does not exceed 1
characteristic
Can have higher search efficiency
Nature of regular exams
Binary tree
Test point 1
n0 = n2 1
Test point 2
The i-th level of the binary tree has at most 2^(i-1) nodes.
Test point 3
A binary tree with height h has at most 2^h-1 nodes (full binary tree)
complete binary tree
Test point 1
The height h of a complete binary tree with n (n>0) nodes <---->The level of the i-th node of the complete binary tree is
Determined by the range of the number of nodes of a full binary tree with a height of h--a height of h-1 (open on the left and closed on the right)
Determine the number of nodes of a complete binary tree with height h (left closed and right open)
Test point 2
Number of nodes n--->n0,n1,n2 (complete binary tree)
2k (even number) nodes
n1 = 1; n0 = k; n2 = k-1
2k-1 (odd number) nodes
n1 = 0; n0 = k; n2 = k-1
Binary tree traversal
First/middle/last order traversal
Order rules based on the recursive properties of trees
three methods
Space complexity O(h 1(call function to determine empty tree)) = O(h)
Preorder traversal (root traversal first)
root, left, right
In-order traversal (middle root traversal)
left, root, right
Postorder traversal (post-root traversal)
left, right, root
Traverse an arithmetic expression tree
source
Prefix expression obtained by preorder traversal
Infix expression of inorder traversal (no parentheses - delimiter required)
Postfix expression obtained by postorder traversal
Test point: Find the traversal sequence
Expand branch nodes layer by layer (recursively traverse subtrees in the same way)
traversal route method
Preorder - the node will be output when it is accessed for the first time.
In-order—The node will be output when it is accessed for the second time.
Postorder—the node will be output when it is accessed for the third time.
Leaf nodes should be understood as the left and right subtrees are empty trees
level-order traversal
Algorithmic thinking
Initialize an auxiliary queue
Root node joins the queue
Repeat cycle
I. If the queue is not empty, the head node is dequeued.
access this node
And insert its left and right children into the end of the queue (if any)
II. Repeat I until the queue is empty
Notice
Store pointers instead of nodes
Construct a binary tree from a traversal sequence
Traverse combinations of sequences (must have in-order sequences)
Preorder and inorder traversal of sequence
Post-order and in-order traversal sequence
Level order in-order traversal sequence
Pairwise combinations of preorder, postorder, and hierarchical sequences cannot uniquely determine a binary tree. (No inorder sequence cannot divide left and right subtrees)
Information learned from various traversal sequences
Preorder traversal of sequence
Root node Preorder traversal sequence of the left subtree Preorder traversal sequence of the right subtree
In-order traversal sequence
Preorder traversal sequence of the left subtree Root node Preorder traversal sequence of the right subtree
Postorder traversal of sequence
Preorder traversal sequence of the left subtree Preorder traversal sequence of the right subtree Root node
level order traversal sequence
Root node Root node of the left subtree Root node of the right subtree
Key steps (recursive use)
1. Find the root node of the tree and divide the left and right subtrees according to the inorder sequence
2. Then find the root nodes of the left and right subtrees, and divide the subtrees of the left and right children according to the in-order sequence of the left and right subtrees.
clue binary tree
Problem introduction
Can in-order traversal start from a specified node (cannot - only start from the root node)
How to find the predecessor of the specified node p in the inorder traversal sequence
concept
clue
Pointers to predecessors/successors become clues
Precursor in sequence/Successor in sequence
Specifies the predecessor/successor node of the specified node in the in-order traversal sequence
First-order-precursor/First-order-successor, Later-order-precursor/Later-order-successor
storage structure
Use n 1 empty link domains of the binary tree to connect the predecessor and successor of the node
On the basis of ordinary binary tree nodes, two flag bits ltag and rtag are added.
ltag
ltag==1
Indicates that lhlid points to the precursor
ltag==0
Indicates that lhlid points to the left child
rtag
rtag==1
Indicates that lhlid points to the successor
rtag==0
Indicates that lclid points to the right child
Three clues binary tree
In-order clue binary tree
"Clueing" based on in-order traversal sequence
preorder clue binary tree
"Clueing" based on pre-order traversal sequence
postorder clue binary tree
"Clueing" based on post-order traversal sequence
effect
It is convenient to start from a specified node and find its predecessor and successor.
Facilitates traversal of first/middle/last order traversal sequences
Threading of binary trees
Hand calculation
Determine the clue binary tree type - inorder, preorder or postorder?
According to the corresponding traversal rules, determine the access sequence of each node and write the number
Connect n 1 empty link domains to the predecessor and successor
Code
Algorithm ideas
Transformation of inorder/preorder/postorder traversal algorithm
core
Use a pointer pre to record the predecessor node of the currently accessed node.
When a node is accessed, the clue information connecting the node to the predecessor node
1. Is the right child pointer of the predecessor node null?
2. Is the left child pointer of the current node null?
Easy to make mistakes
1. Processing of rchild and rtag of the last node (fully utilizing the empty link domains of all nodes)
2. In pre-order threading, pay attention to solving the problem of falling into an infinite loop; When itag==0, the left subtree can be clued in order.
Find the predecessor and successor of p in the clue binary tree (cannot be implemented in X-binary linked list)
In-order clue binary tree (left root (p) right (left root right))
Successor
The lower left node in the right subtree of p
precursor
The lower right node in the left subtree of p
Preorder clue binary tree (around root (p))
Successor
If p has a left child, the left child is followed in order (root p left and right - root p (root left and right) right)
If p has no left child, the right child is followed in order (root p right - root p (root left and right))
Precursor (if the parent node of p can be found)
And p is the left child (root (left and right of root p) right), then the parent node of p is its predecessor node
And p is the right child and its left brother is empty, then the parent node of p is its predecessor node.
And p is the right child and its left brother is not empty, then the predecessor of p is the subtree of its left brother. The last node to be traversed in order (p parent left (root left) (root p left))
If p is the root node, then p has no predecessor
postorder clue binary tree
Successor (if the parent node of p can be found)
And p is the right child ((left)(left and right root p)p parent), then the parent node of p is its successor
And p is the left child ((left and right root p)p parent), and the right brother is empty, then the parent node of p is its successor.
And p is the left child and its right brother is not empty, then the successor of p is the subtree of its right brother. The first node traversed in postorder ((left and right roots p) (left and right roots) p parent)
If p is the root node, then p has no precedence.
precursor
If p has a right child, the right child is followed in order (left and right roots p - left and right (left and right roots (p right)) p)
If p has no right child, then the left child is followed in order (left root p-left (left and right roots (p left)) p)
Ideas
Expand branch nodes layer by layer (analysis method)
Special case
Node p is the left child of its parent node, and the right brother is empty
Node p is the left child of its parent node and has a right brother
Node p is the right child of its parent node, and the left brother is empty
Node p is the right child of its parent node and has a left brother