Trees and binary trees in data structures are two extremely important concepts in establishing nonlinear data structures. They can not only simulate the complex relationships of various practical problems in life, but are also often used to implement algorithms such as search, sorting, and lookup, and even become infrastructure in some large-scale software and systems.
Whether you are a beginner or an advanced person, this article will provide you with simple, easy-to-understand, practical and feasible knowledge points to help you better grasp the importance of trees and binary trees in data structures and algorithms, thereby improving the ability of algorithms to solve problems. ability. Next, let us embark on a wonderful journey of data structures and algorithms.
Table of Contents
Threading of binary trees
Definition and establishment of heap
trees and forests
Huffman tree
Threading of binary trees
Threaded Binary Tree is a method of transforming binary trees to make binary tree traversal more efficient. In a threaded binary tree, in addition to storing pointers to the left and right child nodes, some additional clue information is also stored to quickly locate the predecessor and successor nodes.
In-order threaded binary tree: Utilize the null pointer field of the binary tree to point to the predecessor node and successor node of the node in the in-order traversal.
Storage of in-order clue binary tree:
Pre-order threaded binary tree: Utilize the null pointer field of the binary tree to point to the predecessor node and successor node of the node in the in-order traversal.
Storage of preorder clue binary tree:
Postorder threaded binary tree: Utilize the null pointer field of the binary tree to point to the predecessor node and successor node of the node in the inorder traversal.
Storage of preorder clue binary tree:
The following is a code example using C language to implement pre-order, mid-order, and subsequent clues:
#include <stdio.h>
#include <stdlib.h>
//Define binary tree node structure
typedef struct Node {
int data;
struct Node* left;
struct Node* right;
int isThreaded; // Flag bit, used for threading
} Node;
//Create new node
Node* createNode(int data) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = data;
newNode->left = NULL;
newNode->right = NULL;
newNode->isThreaded = 0;
return newNode;
}
// Preorder threading
void preorderThreading(Node* root, Node** prev) {
if (root == NULL) {
return;
}
if (*prev != NULL & amp; & amp; (*prev)->right == NULL) {
(*prev)->right = root; // Point the right pointer of the predecessor node to the current node
(*prev)->isThreaded = 1; // Set the clue flag position of the predecessor node to 1
}
if (root->left == NULL) {
root->left = *prev; // Point the left pointer of the current node to the predecessor node
root->isThreaded = 1; // Set the clue flag position of the current node to 1
}
*prev = root;
if (!root->isThreaded) {
preorderThreading(root->left, prev);
}
preorderThreading(root->right, prev);
}
// Intermediate threading
void inorderThreading(Node* root, Node** prev) {
if (root == NULL) {
return;
}
inorderThreading(root->left, prev);
if (*prev != NULL & amp; & amp; (*prev)->right == NULL) {
(*prev)->right = root; // Point the right pointer of the predecessor node to the current node
(*prev)->isThreaded = 1; // Set the clue flag position of the predecessor node to 1
}
if (root->left == NULL) {
root->left = *prev; // Point the left pointer of the current node to the predecessor node
root->isThreaded = 1; // Set the clue flag position of the current node to 1
}
*prev = root;
inorderThreading(root->right, prev);
}
// Follow-up clues
void postorderThreading(Node* root, Node** prev) {
if (root == NULL) {
return;
}
postorderThreading(root->left, prev);
postorderThreading(root->right, prev);
if (*prev != NULL & amp; & amp; (*prev)->right == NULL) {
(*prev)->right = root; // Point the right pointer of the predecessor node to the current node
(*prev)->isThreaded = 1; // Set the clue flag position of the predecessor node to 1
}
if (root->left == NULL) {
root->left = *prev; // Point the left pointer of the current node to the predecessor node
root->isThreaded = 1; // Set the clue flag position of the current node to 1
}
*prev = root;
}
int main() {
//Create a binary tree
Node* root = createNode(1);
root->left = createNode(2);
root->right = createNode(3);
root->left->left = createNode(4);
root->left->right = createNode(5);
// Preorder threading
Node* prev = NULL;
preorderThreading(root, & amp;prev);
// Intermediate threading
prev = NULL;
inorderThreading(root, & amp;prev);
// Follow-up clues
prev = NULL;
postorderThreading(root, & amp;prev);
return 0;
}
Reviewing the key points, the main contents are summarized as follows:
The definition and establishment of heap
The heap is a special complete binary tree with the following two characteristics:
1) The value of any node in the heap must satisfy the properties of the heap: for a large root heap (or maximum heap), the value of each node is greater than or equal to the value of its child node; for a small root heap (or minimum heap), each The value of a node is less than or equal to the value of its child nodes.
2) The binary tree in the heap is always completely filled, that is, except for the last layer, other layers are full, and the last layer is continuous from left to right.
for example:
A heap can be described by a one-dimensional array:
Top-down heap building method: The method is to insert the heap and then filter it upward (compare bottom with top, bottom is larger than top, bottom and top swap positions):
Bottom-up heap building method: The method is to perform downward filtering on each parent node (compare top with bottom, top is larger than bottom, top and bottom swap positions):
Tree and Forest
Storage representation of the tree:
Parental representation (sequential storage): Use a one-dimensional array to store all nodes of the tree, and use another one-dimensional array to store the parent nodes of each node. When using the sequential storage parent representation, you can easily find its parent node by its subscript, or you can quickly find the node’s position in the array based on its parent node number. However, insertion and deletion operations are relatively complex and require movement of elements. Compared with chain storage, additional space is required to store parent node number information.
If we want to add a data node, we only need to write the node in the blank position and record its relationship with the parent node:
If you want to delete a node, you can use the following two methods.
Option 1: Set the parent node of the deleted element to -1, indicating that the position is empty
Option 2: Fill the tail elements to the deleted node:
If you delete a parent node, you need to find all the descendant nodes below it and delete them all. If you have adopted the method 1 before, one more empty data will be traversed, which will slow down the traversal:
Child representation (sequential + chained storage): When using sequential storage child representation, you can directly access its child nodes through the node’s pointer or index, without traversing the entire array. For leaf nodes, you can use a special value (such as -1) to indicate that there are no child nodes. Compared with the parent representation, sequentially storing the child representation saves storage space.
Child sibling representation (chained storage): Child sibling representation is suitable for representing general tree structures, not just binary trees. It saves storage space and provides a compact and efficient way to represent trees. This representation is often used in some tree applications, such as expression trees, directory structures of file systems, etc. At the same time, due to the characteristics of the chain structure, it is relatively easy to insert and delete nodes.
Mutual conversion between trees and binary trees:
Conversion between forest and binary tree:
The way the forest is converted into a binary tree: the left sequence is the parent-child relationship, and the right sequence is the sibling relationship. The specific conversion is as follows:
Reviewing the key points, the main contents are summarized as follows:
Tree and forest traversal:
First root traversal of the tree:
Back root traversal of the tree:
Tree level traversal:
Preorder traversal of the forest:
In-order traversal of the forest:
Huo (Ha) Fuman Tree
Understand concepts
The weight of the node: a numerical value with some practical meaning (such as: indicating the importance of the node, etc.)
The weighted 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:
Give the following examples to illustrate:
Note: In a binary tree containing n weighted leaf nodes, the binary tree with the smallest weighted path length (WPL) is called the Huffman tree, also called the optimal binary tree. Therefore, we can construct a Huffman tree based on this characteristic:
Huffman coding:
Reviewing the key points, the main contents are summarized as follows:
The knowledge points of the article match the official knowledge files, and you can further learn related knowledge. Algorithm skill tree Home page Overview 56311 people are learning the system