Tags:
Algorithms & Data Structure Content List
- ComputerScience
#ComputerScience#SWE
This note mainly covers data structures (trees). The note avoids overly strict and dry mathematical language, with intuitive understanding as the primary goal.
Basic Concepts
Generally, trees are divided into free trees and rooted trees. A free tree is a connected acyclic undirected graph, while a rooted tree is not only a connected acyclic undirected graph, but also has one vertex that differs from the others—it is called the root of the tree.
In the following notes, unless otherwise specified, we assume all trees are rooted trees.
Rooted Tree Data Structure
In a rooted tree, vertices are also called nodes. A tree has branches; a node x may be a child of another node y, in which case we also say node y is the parent of node x. In a tree, a node may have several children, but it can only have one parent. Two nodes that share the same parent are called siblings.
Based on these concepts, we can easily write the TreeNode data structure; here we use struct directly.
At this point, we can use a TreeNode *head to represent a pointer to the root node of the rooted tree. Due to connectivity, the root node can directly represent the entire tree.
Binary Tree Data Structure
Specifically, a Binary Tree is a structure defined on a finite set of nodes: it either contains no nodes, or contains three disjoint sets of nodes—a root node, a left subtree (also a binary tree), and a right subtree (also a binary tree). A binary tree with no nodes is an empty tree. If a node has neither a left nor right subtree (or both subtrees are empty trees), the node is called a leaf node.
We can simply modify the TreeNode data structure to use it exclusively as a binary tree node.
Specifically, a Complete Binary Tree is one where nodes at each level are filled as much as possible; except for the last level (leaf nodes), all levels have the maximum number of nodes. If the last level is not full, the nodes are arranged contiguously from left to right, with possible gaps on the right but no gaps in the middle.
Complete binary trees have the following properties:
- For a complete binary tree of depth d, the maximum number of nodes is 2^d - 1.
- Among all trees with n nodes, the complete binary tree has the minimum height (the height of a tree is the length of the longest path from root to any leaf).
A Full Binary Tree is one where every node has either 0 or 2 children, and all leaves are at the same level. A full binary tree is a special case of a complete binary tree.
Basic Algorithms
Rooted Tree Traversal
Among all algorithms for rooted trees, traversal is a relatively simple and fundamental algorithm. Using the properties of trees, we can often write intuitive algorithms using recursion or stacks and queues.
Using binary trees as an example, we introduce four traversal orders: preorder, level order, inorder, and postorder. Assume we want to store the traversal result in a vector and output it.
Preorder Traversal
The preorder traversal order is root → left → right. It is very simple.
Note: During recursion, we try to pass the result array by reference to avoid using vector::insert(), which may cause extra copying and efficiency issues.
Inorder Traversal
The inorder traversal order is left → root → right. The recursive approach is almost the same as above.
Postorder Traversal
The postorder traversal order is left → right → root. The recursive approach is almost the same as above.
Level Order Traversal
Level order traversal requires visiting level by level, and each level from left to right. Here, we no longer use recursion for traversal, but instead use a queue. Queues follow first-in-first-out, so for each level we enqueue the left subtree first and the right subtree second, then pop nodes from the queue in order for traversal.
Rooted Trees with Unbounded Branching
If each node has a finite constant number of children, we can use the initial method to represent a tree. We also have a clever method to represent trees with arbitrary numbers of children using only O(n) storage space—this is called the left-child, right-sibling representation.