Data structure (3) tree and binary tree

4. Trees and binary trees

4.1 Basic Concepts of trees

Node number of the tree: N>=0,N=0 is an empty tree

Trees are good for representing hierarchical data.

​ N nodesThe tree isN – 1 the edge:

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

Points with degree >0 are called branch nodes, and points with degree =0 are called leaf nodes (terminal nodes).

Node hierarchy: the root node is 1

The height (depth) of a tree is the maximum number of layers of nodes in the tree

Ordered tree: The subtrees of nodes are ordered from left to right, or unordered

The path of two nodes is made up of the sequence of nodes that pass between them

The path length is the number of edges along the path

The path length of a tree is the sum of the path lengths from the root to each node (different from the number of edges)

Related properties in trees (degree m) :

​ The ith layer:As much asA node

(key points) Numbered from top to bottom, each layer numbered from left to right:

Is:Number of nodes at layer I:

Nodes of the IKTH childNumbers for:(The former I-1 node has m children, plus itself)

Nodes of the IParents numberTo:

M tree	At least,	As much as
Height H -> node N
Node N -> height H

Note: Number of nodes = edges +1

In any treeA leaf nodeNumber is:

​ N nodesStructure of theDifferent treesThe number of:

4.2 Concept of binary tree

4.2.1 Definition and main features of binary tree

The degree of a binary tree is greater than or equal to 2. A binary tree can be empty. A binary tree is an ordered tree

Ordered tree with contrast of 2:

An ordered tree of degree 2 cannot be considered empty, and the minimum number of nodes is 3

The order of nodes in a binary tree is not deterministic relative to another node

​ Full binary tree:

​

The root is I: the left child is 2i and the right child is 2i+1

Complete binary tree:

​

​ or

Complete binary tree	At least,	As much as
Height H -> node N
The first layer K leaves -> node N

Properties of binary tree:

​

​ The k layer is at most

​ N nodesStructure of theDifferent binary treesThe number of:

Binary tree	At least,	As much as
Height H -> node N
Node N -> height H	or

A binary tree of n nodes has n+1 empty chain fields

4.2.2 Binary tree Storage Structure

Sequential storage structure: The node element numbered I is stored in the subscript i-1 component of the array

Complete and full binary trees are suitable for storage.

Chain storage structure: divided into data domain, left pointer domain and right pointer domain.

4.3 Traversal and clue binary tree

4.3.1 Binary tree traversal

Traversal: order traversal first, middle order traversal, order traversal after

The time complexity of the three traversal modes is O(n), and the space complexity is O(n).

In the three traversal methods, the traversal sequence of leaf nodes is fixed.

You can use a back-order traversal to find the ancestral path

The relationship between the pre-ordered sequence and the middle-ordered sequence is that the pre-ordered sequence is the push order and the middle-ordered sequence is the push order (Cattelan number)

form	The same	On the contrary
First order, then order	Only the root
First order, middle order
Middle order, posterior order
Order, hierarchy		Only roots or empty trees
Middle order, hierarchy
Posterior order, hierarchy

Nonrecursive traversal of SSR binary trees (see exercises).

Hierarchical traversal of a binary tree (traversal of a graph’s breadth) requires the aid of queues.

Constructing binary trees from traversal sequences :(see exercises)

1. Preordered sequence + middle-ordered sequence

2. Post-ordered sequence + middle-ordered sequence

3. Hierarchical sequence + middle sequence

The pre-sequence and post-sequence cannot uniquely determine the binary tree, but can determine the ancestor relationship of nodes. When the pre-sequence is XY and the post-sequence is YX (they are adjacent! X is the ancestor of Y.

4.3.2 Cue binary tree

1. The concept

The clue binary tree is a physical structure

The essence is to linearize a nonlinear structure

Each clue binary tree has n+1 clue (each tree has n+1 null pointer)

The empty chain domain after cueing is:

Number of empty chain fields after cueing	1	2
The first orderClues to the tree	The left subtree of the root is not empty	The left subtree of the root is empty
In the sequenceClues to the tree	There is no	=
After the orderClues to the tree	The right subtree of the root is not empty	The right subtree of the root is empty

Cue binary trees are introduced to speed up the search for node precursors and successors.

Binary tree cueing: If there is no left subtree (ltag=1), let lchild point to the precursor node.

If there is no right subtree (rtag=1), make rChild point to the precursor node.

Clue binary tree of leading node:

The empty chain domain after cueing is 0

The left child of the head node is the root node, and the right child is the last accessed node

The left child of the first node of the sequence and the right child of the last node point to the head node

The sequence of middle order cue trees is easy to find (left-most child, right-most child).

The successor of the sequential clue tree is easy to find, but the precursor must know the parent (stack access), and the traversal of the sequential clue tree does not need stack support.

The successor of the sequential clue tree cannot be calculated, the parents must be known (stack access), and the traversal of the sequential clue tree requires stack support (general).

Note: Not all subsequent-cue tree traversals need stacks. For example, any subsequent-cue tree with at most left subtrees does not need stacks.

Not every node can find its precursor and successor through the clue. The precursor of the sequential clue tree must know both parents, and the successor of the sequential clue tree must know both parents.

4.4 Trees, forests

4.4.1 Storage Structure of a tree

1. Parental representation

A set of contiguous Spaces is used to store each node (class array) with a pseudo-pointer field of **-1 (no parent) or subscript ** pointing to both parents.

You can quickly get the parent of each node, but you have to walk through the entire structure to get the child.

2. Children’s representation (hand drawing)

I’m going to link the children of each node in a single linked list.

Finding a child is straightforward, as finding a parent requires traversing N child lists that are pointed to by the pointer field of the child list at N nodes.

3. Children’s brother representation (hand-painted)

Also known as binary tree representation

Binary storage structure list as | pointer to the first child node value | | nodes under a sibling node pointer

Convenient realization of tree to binary tree operation, easy to find children.

Note: if there are N nodes and B sides in the forest, there are n-B trees in the forest.

4.4.2 Conversion of tree, forest and binary tree

Children left and brothers right.

Forest F-> binary tree B:

* Number of nodes without right children in B = number of non-leaf nodes in F +1

* number of middle nodes in F = number of left child nodes in B

4.4.3 Tree and forest traversal

Tree traversal:

Root-first traversal: Visits the root node first and then traverses the subtree in turn.

Back-root traversal: Sequential back-root traversal of the subtree before accessing the root node.

Forest traversal:

1. Access the root node of the first tree in the forest

2. Traverse the subtree forest of the root node in the first tree in sequence

3. Walk through the forest of remaining trees after removing the first tree

1. The subtree forest of the root node of the first tree in the forest is traversed by the middle order

2. Access the root node of the first tree

3. The sequence traverses the forest formed by the remaining trees after removing the first tree

The tree	The forest	Binary tree
The first root traversal	The first sequence traversal	The first sequence traversal
After traversal	In the sequence traversal	In the sequence traversal

F	Binary tree B

Among them.Represents the number of nodes only in the left subtree,Represents the number of nodes with only the right subtree.

4.5 Tree Application

4.5.1 Binary sort tree

Properties: left subtree value < root value < right subtree value (recursive definition)

Increasing ordered sequence can be obtained by middle order traversal of binary sorting tree

Insert: The node inserted must be a leaf node.

Delete: 1. If a leaf node is deleted, it is directly deleted without changing its nature.

2. If the node has only one subtree, mount the subtree to the parent node of the node and delete the node.

3. If the node Z has two subtrees, the direct successor (or precursor) of Z is replaced by Z, and then the direct successor (precursor) is deleted from the binary sorting tree. This process is carried out recursively.

Time complexity: When the binary sorting tree has only one branch tree, the time complexity is O(n).

​ Average time complexityIs O(logn) (the binary sort tree depth is)

Binary sort tree search sequence: the last found is X, the preceding sequence element is less than X increment, decreases than X.

4.5.2 Balancing binary trees

Balance factor: left subtree height – right subtree height

Balanced binary tree: binary sorting tree with absolute value of balance factor less than 2 for each node.

Minimum node (maximum depth) (all non-leaf nodes are balanced by 1) :

​

Insert: Insert directly without causing imbalance

Rotation if unbalance (the nearest unbalance point to insertion point is A)

LL balanced rotation (right single rotation) : due to insertion in the left subtree of A’s left child

Replace A with the left subtree B of A, and A becomes the right subtree of B, and the right subtree of B becomes the left subtree of A.

RR balanced rotation (left single rotation) : Due to insertion in the right subtree of the right child of A

Replace A with the right subtree B of A, and A becomes the left subtree of B, and the left subtree of B becomes the right subtree of A

LR balanced rotation (first left then right double rotation) : due to insertion in the right subtree of the left child of A

First RR balanced rotation is performed on the left child of A, and then LL rotation is performed on A.

RL balanced rotation (right then left double rotation) : due to insertion in the left subtree of the right child of A

First perform LL balance rotation on A’s right child, then perform RR rotation on A.

​ Average search length:

4.5.3 Huffman tree Huffman coding

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

Huffman tree: WPL’s smallest binary tree

Characteristics of Huffman trees

The node with larger weight is closer to the root node

There are no nodes of degree 1 in the tree

Each value becomes a leaf node (the number of leaf nodes is the number of prefix codes)

Leaf node number N, non-leaf node n-1, sum up number 2n-1

Huffman coding

If no code is a prefix of another code, it is called a prefix code

The root path to any leaf node cannot be a subpath to any other leaf node path

0 means turning to the left, 1 means turning to the right

Huffman tree construction

1) Construct a new node, pick out the two components with the lowest weights, and set the values of the new node as and

2) Repeat until there is only one

Huffman trees are not unique

Huffman N fork tree

The construction method is similar to binary tree

In Huffman tree with degree M, the number of leaf nodes is N, and the number of non-leaf nodes is