Degree of tree: the number of children that a tree has the largest number of child nodes

Node height: counting from bottom to top

Node level, depth: counting from top to bottom

Degree of node: How many children does a node have?

A tree with degree m: the degree of each node is <=m, and at least one node has degree m. It must be a non-empty tree with at least m 1 nodes.

m-ary tree: the degree of any node <=m, the degree of all nodes is allowed <m, it can be an empty tree

Features: Each node has at most two subtrees, and the left and right subtrees cannot be reversed.

full binary tree

complete binary tree

Binary sorting tree

balanced binary tree

n0=n2 1

The rest is the same as above

The height of a complete binary tree with n nodes is log2(n 1) rounded up and (log2n) 1 rounded down.

According to the number of nodes being n, we can deduce the number of nodes with degrees 0, 1, and 2.

Create a static array to store the tree in order from top to bottom, from left to right. The tree structure contains two variables, one is the value of the data, and the other is the bool value to determine whether the node is empty. During initialization, a loop is required to set each node to be empty (bool value is true)

operate

In the sequential storage of binary trees, the node numbers of the binary tree must be matched with the complete binary tree, so that the logical relationships between the nodes can be reflected by the sequentially stored numbers. It only makes sense for complete binary trees to be stored sequentially.

In the worst case, a single tree with only the right child requires at least 2^h-1 sequential storage units

The structure has three variables, one is the value, and the other two are the left and right child pointer variables.

A binary tree linked list with n nodes has a total of n 1 empty link fields.

The advantage is that it is very convenient to find the left and right children of a node, but the disadvantage is that finding the parent node requires traversing from the beginning. The method is to set one more parent node pointer in the structure.

Around the root

left root right

left and right roots

Initialize an auxiliary queue

Let the root node join the queue

If the queue is not empty, let the root node dequeue and let the left and right children of the root node join the queue (the left and right children exist)

Repeat step 3 until the queue is empty

The principle is that the root node can be determined based on the front and rear levels, and then the left and right subtrees are divided according to the middle order.

Idea: There are n 1 empty link domains for n nodes. We use the empty link domain of this node to store the predecessor and successor of this node in each sequence traversal. Set rtag, ltag indicates whether it points to child rag=1 or clue rag=0.

Precursor clue: served by the pointer of the left child

Successor clue: served by the pointer of the right child

In-order predecessor: points to the predecessor of the node in the in-order traversal

Modification of the three traversal algorithms. When visiting a node, the clue information connecting the node and the predecessor node is

Use a pointer pre to record the predecessor node of the currently accessed node.

Processing of rchild and rtag of the last node

Preorder clues to pay attention to the magic circle problem of love. When ltag=0, the left subtree can be clued in preorder.

Looking for a successor

Find a pioneer

Find a pioneer

Looking for a successor

Find a pioneer

Looking for a successor

How to define

operate

Advantages and Disadvantages: The advantage is that it is easy to find the parent node, but finding the child node requires traversing from the beginning.

How to define

There are two pointers in the structure, one pointing to the left child and the other pointing to the right brother of the left child.

Advantages: You can use binary tree operations to directly process trees

Present the structure of a binary tree in physical logic

tree root traversal

Back root traversal of tree

Tree level traversal

Preorder traversal of the forest

inorder traversal

The weight of the node: a value with some practical meaning (such as the importance of the node)

The full path length of a node: the product of the path length (number of edges passed) from the root of the tree to the node and the weight of the node

The full path length of the tree

In a binary tree containing n weighted leaf nodes, the binary tree with the smallest total path length is called a Huffman tree, also known as the optimal binary tree.

The structure of Huffman tree

nature

Fixed length encoding: each character is represented by equal length of binary bits

Variable length encoding: allows different characters to be represented by unequal lengths of binary bits

Prefix encoding: If no encoding is the prefix of another encoding, then such encoding is called prefix encoding.

Huffman coding is obtained by using a Huffman tree. Each character in the character set is used as a leaf node, and the frequency of each character is used as the weight of the node to construct a Huffman tree.

Application: Telegraph and compressed data

Union-find set is a logical structure, a specific implementation of a set. It only performs two operations: union and search. A forest is used to represent a set, and each tree is a disjoint subset.

operate

Storage structure: Parental representation of a tree.

Code

Further optimization of union lookup