In computers, trees are the opposite of their real-world forms; they are upside-down trees~
Course Content#
Tree#
- Composition of a tree: Node + Edge
- Node 👉 Set, Edge 👉 Relation
- Root Node: Universal Set; Child Node: Subset
- The union of all child nodes of the root node = Universal Set
- 【Concept】Abstract big problems as trees, abstract small problems as child nodes
Structure Definition#
【Node + Edge】
-
-
A unary tree is a linked list structure, a tree structure with only one branch
-
For a ternary tree, simply change the next pointer of the linked list to a next[3] array
Properties and Characteristics#
-
-
Depth and Height
- The depth and height of a tree are the same value: maximum level
- The depth and height of a node are different
- Depth: Counted from the root node downwards, which level the node is on
- Height: Counted from the deepest level upwards, which level the node is on
-
Degree: Number of child nodes
-
⭐【Important Formula】Number of Nodes = Number of Edges + 1
Binary Tree#
- Binary can be converted to any base, and similarly for binary trees
- First, it is simple
- And it can represent all tree structures
- Method: Left Child, Right Sibling method, also known as Cross Linked List method
-
- From top to bottom, from left to right, the node's children are placed on the left, and the node's adjacent siblings are placed on the right
- For n-ary trees, n is uncertain, while binary trees are definite
- n-ary trees can be implemented using binary trees
- Therefore, using binary trees can convert non-deterministic problems → deterministic problems that computers can solve
- ⭐【Important Formula】In a binary tree, the number of nodes with degree 0 is one more than the number of nodes with degree 2
- Using another important formula: Number of Nodes = Number of Edges + 1
- Let ni represent the number of nodes with degree i
- Then: [Number of Nodes] n0 + n1 + n2 = n1 + 2 * n2 + 1 [Number of Edges + 1]
- Result: n0 = n2 + 1
- Traversal methods: Depends on when [first, middle, last] the root node is accessed
- 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 after
- Classification of Binary Trees [International Version], reference Binary tree: Types of binary trees-Wikipedia
-
- Complete Binary Tree: Except for the last layer where the rightmost nodes can be missing several consecutive nodes, all other places are fully filled
- Full Binary Tree: Degree 0 or 2 is sufficient
- Perfect Binary Tree: All degrees are 2, all leaf nodes are on the same level
- PS: The Chinese version only divides into complete binary trees and full binary trees, with the definition of full binary trees being 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 numbered i are numbered 2 * i and 2 * i + 1 respectively
- Can be stored in contiguous space (array) for algorithm optimization: record type 👉 calculation type
- No longer need to use structures to store the addresses of child nodes; the index in the array can be calculated directly using the formula
- Generalized List: String representation of a tree
-
-
- There are many representation methods, generally as simple as possible, see the red box in the above image: Method One, Method Two
-
- For binary search trees, in-order traversal is ordered
- Based on two traversals, a third traversal result can be obtained
- Pre-order/Post-order traversal can obtain the root node, in-order traversal can obtain the positions of the left and right children
- 【Must】have in-order traversal, only it can determine the left and right of the children
Code Demonstration#
Binary Search Tree#
Structure definition, structure operation, traversal result display
-
-
-
-
The operations on trees and nodes are implemented separately, independently encapsulated
-
Insertion operation
- Use flag to get insertion status
- Binary search trees do not have duplicate values
-
Traversal operation
- The internal implementation of the three traversals just swaps the order of accessing left, right, and root
- The in-order traversal of binary search trees is ordered, sorted from smallest to largest
-
Output: The generalized list form is the aforementioned second method
-
❓ Nodes in the structure are all defined as pointer types; my understanding is
- A node is a structure, using pointers to store addresses saves space
- Structure pointers call members more conveniently: ->
- Convenient to free nodes
Generalized List Restoring Binary Tree#
-
-
Problems with complete containment relationships use a stack
-
The stack stores node addresses [Node *]: Treat the characters in the generalized list as nodes
-
Conversion process
|(|,|)|Other Characters【Letters】|
|:----:|:----:|:----:|:----:|
|【Push element onto stack】
The element before the next ',' is the left child|Determine the next character's encapsulated element as【Right Child】|Record the top of the stack,【Pop element from stack】|① Encapsulate the character as a node pointer type, as an element of the stack
②【Relationship Determined】If the stack is not empty, then 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 node
- A node is an entity that has processing capability
- A node is an intersection point, a marker
- Points in algorithms are generally referred to as nodes, and each data element in a data set is represented by a box marked with the element value, which we call a node
- Reference What is the difference between node and node-PHP Chinese Network
- In the industry, except for red-black trees, other trees are toy-level tree structures
-
