This is the 18th day of my participation in Gwen Challenge

Trees, forest

The storage structure of a tree

  • Parent representation method

#define MAX_TREE_SIZE 100 // Maximum number of nodes in the tree
typedef struct{
    ElemType data;
    int parent;
}PTNode;
typedef struct{
    PTNode nodes[MAX_TREE_SIZE];
    int n;
}PTree;
Copy the code
  • Child notation
  • Child brother notation
typedef struct CSNode{
    ElemType data;
    struct CSNode *firstchild, *nextsibling; // First child pointer, right brother pointer
}CSNode,*CSTree
Copy the code

Tree, forest, binary tree conversion

Traversal of trees and forests

Tree traversal

  • Root-first traversal: If the tree is not empty, the root node is accessed first, and each subtree of the root node is traversed from left to right
  • Back-root traversal: If the tree is not empty, each subtree of the root node is traversed from left to right before the root node is accessed

Traversal of the forest

  • Traverse the forest in order
    • Access the root node of the first tree in the forest
    • A forest of subtrees of the root node in the first tree is traversed in order
    • The forest is traversed by the remaining trees after the first tree has been removed
  • The middle sequence traverses the forest
    • A subtree forest that traverses the root of the first tree in the forest
    • Access the root of the first tree
    • The sequence traverses the forest of remaining trees after removing the first tree

Tree application – and lookup set

Lookup sets support three operations

Union(S,Root1,Root2);// merge subset Root2 from set s into subset Root1. Root1 and Root2 do not intersect, otherwise no merge is performed
Find(S,x);// Find the name of the subset of the element x in set S.
Initial(S); // Initialize each element in set S as a single element subset
#define SIZE 100
int UFSets[SIZE];
void Initial(int S[]){
    for(int i=0; i<size; i++){ S[i]=- 1; }}int Find(int S[],int x){
    while(S[x]>=0){
        x = S[x];
    }
    return x;
}
void Union(int S[],int Root1,int Root2){
    S[Root2] = Root1;
}
Copy the code

Application of tree and binary tree

Binary sort tree (BST)

Left subtree value > root value > right subtree value

A non-recursive search algorithm for binary sorting trees

BSTNode *BST_Search(BiTree T,ElemType key,BSTNode &p){
    p=NULL;
    while(T! =NULL&&key! =T->data){ p=T;if(key<T->data) T=T->lchild;
        else T=T->rchild;
    }
    return T;
}
Copy the code

Insertion of a binary sort tree

int BST_Insert(BiTree &T,KeyType k){
    if(T == NULL) {// The original tree is empty. The new node is the root node
        T = (BiTree)malloc(sizeof(BSTNode));
        T->key = k;
        T-lchild = T->rchild = NULL;
        return 1;
    }else if(k == T->key)return 0;
    else if(k<T->key)
        return BST_Insert(T->lchild,k);
    else 
        return BST_Insert(T->rchild,k);
}
Copy the code

Construction of binary sorting tree

void Creat_BST(BiTree &T,KeyType str[],int n){
    T=NULL;
    int i=0;
    while(i<n){ BST_Insert(T,str[i]); i++; }}Copy the code

Delete binary sort tree

Balanced binary tree (AVL)

Balance factor: Defines the height difference between the left and right subtrees of a node as the balance factor of the node

Balanced binary tree insertion

  • LL equilibrium rotation

Because we’re inserting A new node into the left subtree of the left child of node A

  • RR balanced rotation

Because we’re inserting A new node into the right subtree of the right child of node A

  • LR balanced rotation

Because we’re inserting A new node into the right subtree of the left child of node A

  • RL equilibrium rotation

Because we’re inserting A new node into the left subtree of the right child of node A

Huffman tree and Huffman coding

In many practical applications, a node in a tree is often given a value representing some meaning, called the weight of the node. The product of the path length from the root node to any node (the number of edges passed) and the weight on the node is called the weighted path length of the node. The sum of the weighted path length of all leaf nodes in the tree is called the weighted path length of the tree. Write WPL=∑ I =1nwiliWPL = \sum_{I =1}^nw_il_iWPL=∑ I = 1Nwili

In a binary tree with n full-leaf nodes, the one with the least weight path length is called Huffman tree, also called optimal binary tree.

The construction of Huffman tree

  • N nodes are respectively regarded as n binary trees containing only one node to form forest F
  • Construct a new node, select two trees with the lowest 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 sum of the root node weights of the left and right subtrees.
  • Delete the two trees just selected from F and add the new tree to F.
  • Repeat 23 until F has the last tree left

Huffman coding