There is only one root node

When n>1, the remaining nodes can be divided into m disjoint finite sets Ti, each set is a subtree of the root.

The maximum degree of a node is called the degree of the tree

The sum of the node degrees of the tree = the sum of the number of branches = the number of nodes - 1

full binary tree

complete binary tree

Binary sorting tree

balanced binary tree

The number of leaf nodes on a non-empty binary tree = the number of nodes with degree 2 1, that is, n0=n2 1

There are at most 2^(k-1) nodes on the k-th level of a non-empty binary tree.

A binary tree of height h has at most 2^h-1 nodes.

A binary tree can be uniquely determined by its preorder (or postorder) sequence and inorder sequence.

A binary tree can be uniquely determined by its hierarchical sequence and in-order sequence.

According to the pre-order and post-order sequences of the binary tree, the ancestral relationship of some nodes can be determined: if the pre-order is aX and the post-order is Xa, then the nodes in the set If they are brothers, the order should be consistent, that is, the left brother comes first)

Find the first node under the inorder sequence in the inorder clue binary tree

Find the successor of node p in the in-order clue binary tree under the in-order sequence

In-order traversal algorithm for in-order clued binary trees without head node

Find node successor in preorder clue binary tree

Finding the successor of a node in a binary tree using postorder clues

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

The weighted path length of the tree: the sum of the weighted path lengths of all leaf nodes in the tree

Huffman tree: Among the binary trees containing n weighted leaf nodes, the binary tree with the smallest weighted path length (WPL) is also called the optimal binary tree.

construction process

Features

Huffman coding

Usually the parent representation of a tree (forest) is used as the storage structure of the union-find set, and each sub-set is represented by a tree. All trees representing sub-sets form a forest representing the entire set and are stored in the parent representation array. Usually, the subscript of the array element is used to represent the element name, and the subscript of the root node is used to represent the sub-collection name. The parent node of the root node is a negative number.

1) Initial(S): Initialize each element in the set s to a subset with only a single element.

2) Union(S, Root1, Root2): Merge the sub-set Root2 in the set S into the sub-set Root1. Require Root1 and Root2 are disjoint with each other, otherwise the merge will not be performed.

3) Find(S,x): Find the subset where the single element x is located in the set s, and return the root node of the subset.

A set of continuous spaces is used to store nodes; at the same time, a pseudo pointer is added to each node to indicate the location of the parents.

You can quickly get the parent nodes of a node, but you need to traverse the array to find the children of the node.

Connect the child nodes of each node with a single linked list, n nodes correspond to n linked lists

Finding children is simple, but finding parents requires traversing n linked lists

Using a binary linked list as the storage structure of the tree

It is easy to find children, but it is more troublesome to find parent nodes (parent pointer can be added)

Using a binary linked list as a medium, there is a unique binary tree corresponding to each tree (and vice versa)

Conversion rule: "Left child, right brother"

Similar to the above conversion, each tree is first converted into a binary tree, and then the root of the n-th tree is regarded as the right sibling of the root of the n-th tree.

Root traversal first

back root traversal

Level traversal

preorder traversal

inorder traversal