Assume that a binary tree has n weighted leaf nodes, then the sum of the path length from the root node to each leaf node and the product of the corresponding node weight is called the weighted path length WPL (weighted Path Length) of the binary tree. .

The same leaf nodes construct different binary trees

The binary tree with the minimum weighted path length is called the Huffman tree (also called the optimal tree).

in principle

process

Huffman coding (prefix coding)

left<root<right

An improved version of the binary sorting tree (a special binary sorting tree), try to keep the tree as short as possible!

How to tell if a tree is growing normally?

Binary sorting tree with balance factor <= 1

Balance the maximum depth and minimum number of nodes of a binary tree

insert

prologue

mid-order

Afterword

Traverse line by line

Require

For questions with few nodes

The core steps of the Prime algorithm are: in a weighted connected graph, V is a set containing all vertices. U is already a node in the minimum spanning tree, starting from any vertex v in the graph. At this time, the set U={v}, Repeat the following operations: find an edge with the smallest weight among all edges (u,w)∈E of all u∈U,w∈V-U, and add the edge (u,w) to the set of found edges. And add point w to the set U. When U=V, the minimum spanning tree is found.

First determine the nodes and select the ones with the shortest paths in order.

For questions with a small number of sides

Basic idea: edge-led. In a weighted connected graph, U is the set of all edges, N is the number of vertices, and let SU be the set of edges that are already on the minimum spanning tree. Repeat the following operations: each time select an edge e∈U-SU with the smallest weight and an edge that does not form a cycle with the edges in SU, and add it to SU. When the number of edges in SU is equal to N-1, the minimum spanning tree is found.

The number of nodes without a right pointer is: root node number of non-leaf nodes

Exclude symmetrical ones, count the number, and make sure it is always less on the left and more on the right or more on the left and less on the right.

The root node is unique

There is no limit to the number of subtrees, but they do not intersect with each other.

nature

full binary tree

complete binary tree

Must be a complete binary tree

dagendui

small root pile

Heap storage

Upper filter

Filter down

How to convert an unordered array into a heap?

two operations

Can be implemented using a small root heap

Complexity: O(NlogN)