full binary tree

complete binary tree

Binary sorting tree

balanced binary tree

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.

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

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

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.

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.

This method is also called binary tree representation, which can easily convert a tree into a binary tree (left child, right brother)

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

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)

(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.

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

Root traversal first

back root traversal

Level traversal

Preorder traversal of the forest

Traversing the forest in sequence