Wondershare EdrawMind
MindMap Gallery Data Structure Chapter 5-Tree and Binary Tree
- 79
Data Structure Chapter 5-Tree and Binary Tree
Chapter 5 of "Data Structure" - sorting out the knowledge of trees and binary trees, including the basic concepts of trees, the concept of binary trees, binary tree traversal and clue binary trees, etc.
Edited at 2022-11-23 16:07:00
Data Structure Chapter 5-Tree and Binary Tree
- Recommended to you
- Outline
Numbers and Binary Trees
Basic concepts of trees
definition
A tree is a finite set of n nodes. A non-empty tree should satisfy:
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.
basic terminology
ancestors, descendants, parents, children, brothers
Degree: the number of children of the node
The maximum degree of a node is called the degree of the tree
Leaf nodes (terminal nodes), branch nodes (non-terminal nodes)
The sum of the node degrees of the tree = the sum of the number of branches = the number of nodes - 1
Depth: starting from the root node and accumulating layer by layer from top to bottom.
Height: starting from the leaf node and accumulating layer by layer from bottom to top.
Ordered tree, unordered tree
path, path length
Forest: a collection of m disjoint trees
nature
The number of nodes in the tree = the sum of the degrees of all nodes 1
There are at most m^(i-1) nodes on the i-th level of a tree of degree m.
An m-ary tree with height h has at most (m^h-1)/(m-1) nodes.
The minimum height of an m-ary tree with n nodes is:
Binary tree concept
Definition and characteristics
Definition: Each node has at most two subtrees, and the subtrees can be divided into left and right subtrees.
special binary tree
full binary tree
The height is h and the number of nodes is 2^h-1
For the node numbered i
parents:
Left child: 2i
Right child: 2i 1
complete binary tree
The number of each node corresponds to a full binary tree (that is, only the leaf node on the right is empty)
nature
①If i≤Ln/2", then node i is a branch node, otherwise it is a leaf node.
②Leaf nodes can only appear on the two largest levels. The leaf nodes in the largest level are arranged in sequence at the leftmost position of the level.
③If there is a node with degree 1, there can only be one, and the node has only left children but no right children.
④After numbering in hierarchical order, once a node (numbered i) appears as a leaf node or has only a left child, the number is greater than i The nodes are all leaf nodes.
⑤ If n is an odd number, then each branch node has a left child and a right child; if r is an even number, the branch node with the largest number (numbered n/2) has only a left child and no right child, and the other branch nodes have There are children who click left and right.
⑥The height of a complete binary tree with n nodes is:
Binary sorting tree
Left subtree keyword<root node<right subtree
The left and right subtrees are each a binary sorting tree.
balanced binary tree
The depth difference between the left subtree and the right subtree of any node in the tree does not exceed 1
Properties of binary trees
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.
Binary tree storage structure
sequential storage structure
chain storage structure
Binary tree traversal and clue binary trees
Binary tree traversal
Preorder traversal (NLR)
In-order traversal (LNR)
Postorder traversal (LRN)
Recursive algorithm → non-recursive (with the help of stack)
Non-recursive algorithm for in-order traversal
Level traversal (with the help of queues)
Construct a binary tree from a traversal sequence
A binary tree can be uniquely determined by its preorder (or postorder) sequence and inorder sequence.
The first node of the preorder sequence must be the root node, and the root node divides the inorder sequence into two sequences: the left and right subtrees.
Find the left and right subtrees in the preorder according to the left and right subtrees in the inorder, and repeat the above steps recursively.
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)
clue binary tree
concept
Construct in-order clue binary tree
Clue binary tree with leading node
Traversal of binary trees with inorder clues
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
Pre-order clue binary tree and post-order clue binary tree
Find node successor in preorder clue binary tree
If there is a left child, he will be his successor
If there is no left child but there is a right child, the second child will be the successor.
Otherwise, the right chain domain points to the successor
Finding the successor of a node in a binary tree using postorder clues
If x is the root of a binary tree, then the successor is empty
If x is the right child of both parents, or the left child of both parents and the parents have no descendants, then the successor is his parents
If x is the left child of the parent, and the parent has a right child, the successor is the first node listed in the descending order traversal on the right subtree of the parent.
Applications of trees and binary trees
Huffman trees and Huffman coding
definition
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.
The structure of Huffman tree
construction process
Given n nodes with weights w1, w2,...,wn, the algorithm for constructing a Huffman tree is described as follows:
1) Treat these n nodes as n binary trees containing only one node to form a forest F.
2) Construct a new node, select the two trees with the smallest root node weights from F as the left and right subtrees of the new node, and set the weights of the new node to the roots of the left and right subtrees. The sum of the node weights.
3) Delete the two trees just selected from F and add the newly obtained trees to F.
4) Repeat steps 2) and 3) until there is only one tree left in F.
Features
1) Each initial node eventually becomes a leaf node, and the smaller the weight, the greater the path length from the node to the root node.
2) A total of n-1 new nodes (double-branch nodes) are created during the construction process, so the total number of nodes of the Huffman tree is 2n-1.
3) Each construction selects 2 trees as the children of the new node, so there is no node with degree 1 in the Huffman tree.
Huffman coding
variable length encoding
Different characters are represented by binary bits of unequal length; low-frequency characters are assigned longer codes, and high-frequency characters are assigned shorter codes.
prefix encoding
No encoding is a prefix of another, so decoding is very simple
Huffman coding is a data compression coding designed using variable length and prefix coding.
Huffman tree→Huffman coding
1) Treat each appearing character as an independent node, its weight is equal to the frequency of occurrence (number of times), and construct the corresponding Huffman tree
2) Interpret the encoding of a character as a sequence of edge markers on the path from the root to the character; where an edge marker of 0 means "turn to the left child", and an edge mark of 1 means "turn to the right child"
And search the collection
Basic idea
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.
operate
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.
tree, forest
tree storage structure
parent representation
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.
child representation
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
Child brother representation (binary tree representation)
Using a binary linked list as the storage structure of the tree
Node
node value
Pointer to the first child of the node
Pointer to the node's next sibling node
It is easy to find children, but it is more troublesome to find parent nodes (parent pointer can be added)
Conversion of trees, forests and binary trees
tree ↔ binary tree
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"
Root-first traversal sequence: ABEFCDG
Post-root traversal sequence: EFBCGDA
Forest ↔ Binary tree
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.
Preorder traversal of sequence: ABCDEFGHI
In-order traversal sequence: BCDAFEHIG
Tree and forest traversal
tree traversal
Root traversal first
First visit the root node, then visit each subtree in turn
The traversal sequence is the same as the preorder sequence of the corresponding binary tree
back root traversal
First visit each subtree in turn, then visit the root node
The traversal sequence is the same as the in-order sequence of the corresponding binary tree
Level traversal
Traveling through the forest
preorder traversal
Visit the root node of the first tree in the forest
Pre-order traverse the subtree forest of the root node in the first tree
Preorder traverse the remaining forest after removing the first tree
inorder traversal
In-order traversal traverses the subtree forest of the root node of the first tree in the forest.
Visit the root node of the first tree
In-order traversal of the forest consisting of the remaining trees after removing the first tree