In computers, trees are opposite to their real-life counterparts. They are an inverted tree~
Course Content#
Trees#
- Composition of a tree: Nodes + Edges
- Nodes 👉 Set, Edges 👉 Relationships
- Root Node: Entire set; Child Nodes: Subsets
- Union of all child nodes of the root node = Entire set
- 【Idea】Abstract big problems as trees, abstract small problems as child nodes
Structure Definition#
【Nodes + Edges】
-
-
A binary tree is a linked list structure, a tree-like structure with only one branch
-
For a ternary tree, the next pointer of the linked list is replaced with an array next[3]
Properties#
-
-
Depth, Height
- The depth and height of a tree are the same value: the maximum number of layers
- The depth and height of a node are different
- Depth: the layer number of the node when counting from the root node downwards
- Height: the layer number of the node when counting from the deepest layer upwards
-
Degree: the number of child children
-
⭐【Important Formula】Number of Nodes = Number of Edges + 1
Binary Trees#
- Binary can be converted to any base, and the same goes for binary trees
- First, it is simple
- And it can represent all tree-like structures
- Method: Left Child, Right Sibling Method, also known as Cross-Linked List Method
-
- From top to bottom, from left to right, the child of a node is placed on the left, and the adjacent sibling of a node is placed on the right
- For an n-ary tree, where n is uncertain, a binary tree is determined
- An n-ary tree can be implemented using a binary tree
- Therefore, using a binary tree can transform non-deterministic problems into deterministic problems that computers can solve
- ⭐【Important Formula】In a binary tree, the number of nodes with a degree of 0 is one more than the number of nodes with a degree of 2
- Using another important formula: Number of Nodes = Number of Edges + 1
- Let ni represent the number of nodes with a degree of i
- Then: [Number of Nodes] n0 + n1 + n2 = n1 + 2 * n2 + 1 [Number of Edges + 1]
- Therefore: n0 = n2 + 1
- Traversal methods: Depends on when the root node is visited [First, Middle, Last]
- Pre-order traversal: Root Left Right
- In-order traversal: Left Root Right
- Post-order traversal: Left Right Root
- The left and right during traversal can represent the left and right subtrees, respectively
- The relative order of left and right is always left first, right second
- Classification of Binary Trees [International Version], refer to Binary tree: Types of binary trees-Wikipedia
-
- Complete Binary Tree: Except for the rightmost nodes in the last layer, all other places are full
- Full Binary Tree: Degree 0 or 2 is sufficient
- Perfect Binary Tree: Degree is 2, all leaf nodes are on the same layer
- PS: The Chinese version only distinguishes between complete binary trees and full binary trees. The definition of full binary trees in the Chinese version is the same as that of perfect binary trees in the international version
-
- Characteristics of Complete Binary Trees [Perfect Binary Trees also satisfy]
- The left and right children of the node with index i are numbered 2 * i and 2 * i + 1, respectively
- It can be stored in continuous space (array), used for algorithm optimization: Record-based👉Calculation-based
- No longer need to store the addresses of child nodes in a structure, the index in the array can be calculated directly
- Generalized List: String representation of a tree
-
- There are many ways to represent it, generally the simpler the better, see the red box in the figure above: Method 1, Method 2
-
- For a binary search tree, the in-order traversal is in order
- The third traversal result can be obtained based on the first two traversals
- The pre-order traversal/post-order traversal can obtain the root node, and the in-order traversal can determine the positions of the left and right children
- 【Must】have the in-order traversal, only it can determine the left and right children
Code Demonstration#
Binary Search Tree#
Structure definition, structure operations, display of traversal results
-
-
-
-
The operations of the tree and nodes are implemented separately and independently encapsulated
-
Insertion operation
- Use a flag to get the insertion status
- Binary search trees do not have duplicate values
-
Traversal operation
- The internal implementation of the three traversals is just to change the order of visiting the root, left, and right
- The in-order traversal of a binary search tree is ordered, sorted from small to large
-
Output: The generalized list form is the second method mentioned above
-
❓The nodes in the structure are defined as pointers. My understanding is
- The node is a structure, and storing the address with a pointer saves space
- Accessing members of a structure pointer is more convenient: ->
- Convenient for freeing nodes
Restoration of Binary Trees from Generalized Lists#
-
-
Problems with complete inclusion relationship, use a stack
-
The stack stores node addresses [Node *]: consider the characters in the generalized list as nodes
-
Conversion process
|(|,|)|Other Characters [Letters]|
|:----:|:----:|:----:|:----:|
|【Push the element into the stack】
The element before the next ',' is the left child|Determine that the next character to be encapsulated is the 【right child】|Record the top of the stack, 【Pop the element from the stack】|①Encapsulate the character as a node pointer type, as an element of the stack
②【Determine the relationship】If the stack is not empty, based on the position of the character relative to ',', it becomes the left child or right child of the top element of the stack|
Code
-
-
-
-
-
-
Structure definition, operation definition: stack, binary tree
-
【Key】Matching rules for conversion
Tips#
- Difference between node and vertex
- A node is an entity with processing capabilities
- A vertex is an intersection, a marker
- In algorithms, points are generally called nodes, and each data element in a data set is represented by a square box with the element value in the middle, which we call a node
- Refer to What is the difference between node and vertex-php.cn
- In the industry, except for red-black trees, other trees are toy-level tree-like structures
-
