[Data structure] Binary tree sequence structure, realization of chain structure, traversal of binary tree (preorder, inorder, postorder, layer order)

Article directory

  • 1. Binary tree structure implementation
    • 1.1 Realization of sequence structure
    • 1.2 Realization of chain structure
  • 2. The concept and introduction of the heap
  • 3. Binary tree traversal
    • 3.1 Preorder traversal
    • 3.2 Inorder traversal
    • 3.3 Post-order traversal
    • 3.4 Layer order traversal

1. Implementation of binary tree structure

1.1 Realization of sequence structure

In the previous article, we have a certain understanding of the binary tree, here we will add some content to the binary tree.

Ordinary binary trees are not suitable for storage in arrays, because there may be a lot of space waste. The complete binary tree is more suitable for sequential structure storage.
In reality, we usually store the heap (a binary tree) in an array of sequential structures. It should be noted that the heap here is different from the heap in the virtual process address space of the operating system. One is a data structure, and the other is a It is an area segment in the operating system that manages memory.

?
Define a simple sequential binary tree in C language:

// Sequential storage structure binary tree
typedef struct {<!-- -->
    int data[MAX_TREE_SIZE + 1]; // array storage structure
    int size; // the size of the current binary tree
} SeqBinaryTree;

//heap
typedef int HPDataType;
typedef struct Heap
{<!-- -->
HPDataType* _a;
int_size;
int _capacity;
}Heap;

?
Although in the case of an incomplete binary tree structure, sufficient space needs to be reserved, which may waste part of the storage space. However, in practical applications, the sequential structure binary tree is still widely used. The storage and operation of a complete binary tree is used for heap Implementation of sorting, Huffman coding and other algorithms.
The following are the advantages of sequential structure binary tree:

(1) Easy to implement: It is implemented using an array, which does not require dynamic memory allocation, nor does it require pointer operations with complex linked list structures, and is easy to implement.

(2) Convenient storage: The complete binary tree can be stored in order, and there is no need to store pointer information for each node, saving space.

(3) Stable storage structure: Since the entire binary tree is in a continuous memory, the stability of the sequential storage structure is better than that of the chained storage structure, and it is not easy to have problems such as memory leaks or memory fragments.

(4) High access efficiency: Since the sequential structure binary tree is stored continuously, any node can be quickly accessed through the subscript, and the access efficiency is high.

(5) High space utilization rate: In the case of a complete binary tree, the space utilization rate of the sequential structure binary tree is very high, and the position of each node is meaningful, and there is no need to waste additional space.
?

Implementation of sequential structure binary tree (reference)

#include <stdio.h>
#include <stdlib.h>

#define MAX_TREE_SIZE 100

// Sequential storage structure binary tree
typedef struct {<!-- -->
    int data[MAX_TREE_SIZE + 1]; // array storage structure, subscript starts from 1
    int size; // the size of the current binary tree
} SeqBinaryTree;

// Initialize the binary tree
void init(SeqBinaryTree *tree) {<!-- -->
    tree->size = 0;
}

// Check if the binary tree is empty
int is_empty(SeqBinaryTree *tree) {<!-- -->
    return tree->size == 0;
}

// returns the number of elements in the binary tree
int size(SeqBinaryTree *tree) {<!-- -->
    return tree->size;
}

// Get the root node of the binary tree
int get_root(SeqBinaryTree *tree) {<!-- -->
    if (is_empty(tree)) {<!-- -->
        printf("Binary tree is empty.\\
");
        exit(0);
    }
    return tree->data[1];
}

// Get the parent node of the specified node
int get_parent(SeqBinaryTree *tree, int index) {<!-- -->
    if (is_empty(tree)) {<!-- -->
        printf("Binary tree is empty.\\
");
        exit(0);
    } else if (index == 1) {<!-- -->
        printf("This node is root, no parent node.\\
");
        exit(0);
    }
    return tree->data[index / 2];
}

// Get the left child node of the specified node
int get_left_child(SeqBinaryTree *tree, int index) {<!-- -->
    if (is_empty(tree)) {<!-- -->
        printf("Binary tree is empty.\\
");
        exit(0);
    } else if (index * 2 > tree->size) {<!-- -->
        printf("This node does not have a left child.\\
");
        exit(0);
    }
    return tree->data[index * 2];
}

// Get the right child node of the specified node
int get_right_child(SeqBinaryTree *tree, int index) {<!-- -->
    if (is_empty(tree)) {<!-- -->
        printf("Binary tree is empty.\\
");
        exit(0);
    } else if (index * 2 + 1 > tree->size) {<!-- -->
        printf("This node does not have a right child.\\
");
        exit(0);
    }
    return tree->data[index * 2 + 1];
}

// insert node
void insert(SeqBinaryTree *tree, int data) {<!-- -->
    if (tree->size >= MAX_TREE_SIZE) {<!-- -->
        printf("Binary tree is full.\\
");
        exit(0);
    }
    tree->size + + ;
    tree->data[tree->size] = data;
}

// destroy the binary tree
void destroy(SeqBinaryTree *tree) {<!-- -->
    tree->size = 0;
    printf("Binary tree has been destroyed.\\
");
}

?

1.2 Realization of chain structure

Simply define a chained binary tree in C language

typedef int BTDataType;
typedef struct BinaryTreeNode
{<!-- -->
 BTDataType_data;
 struct BinaryTreeNode* _left;
 struct BinaryTreeNode* _right;
}BTNode;

?

The binary tree with chain structure has the following advantages:

(1) Flexible structure: The structure of the chained binary tree is relatively flexible and can be dynamically adjusted according to the actual situation, without pre-determining the capacity.

(2) High space utilization rate: When the nodes of the chained binary tree are irregular, it can avoid wasting a large amount of storage space like the sequential structure binary tree, and the space utilization rate is high.

(3) High insertion and deletion efficiency: When inserting and deleting nodes, the chain structure binary tree does not need to move a large number of nodes like the sequential structure binary tree, so its insertion and deletion efficiency is higher .

(4) Flexible in actual use: In practical applications, chained binary trees can easily implement friendly APIs (such as implementing templated binary trees with C++), or inside containers As an auxiliary data structure to complete various complex functions.

The chain structure binary tree is generally suitable for the situation of non-full binary tree/irregular binary tree. When the number of nodes and the depth of the tree change frequently, the chained binary tree can better reflect its advantages. Especially for data structures such as binary search trees, chained binary trees are more convenient and practical to use.
?

Implementation of chain structure binary tree (reference)

#include<stdio.h>
#include <stdlib.h>

struct node {<!-- -->
    int data; //value of the node
    struct node *left; //Pointer to the left child node
    struct node *right; //Pointer to the left child node
};

// Function to insert a node
struct node* insert(struct node* root, int data) {<!-- -->
    //If the root node is empty, create a new node and use it as the root node
    if (root == NULL) {<!-- -->
        root = (struct node*)malloc(sizeof(struct node));
        root->data = data;
        root->left = NULL;
        root->right = NULL;
    }
    //If the node is not empty, compare it with the value of the current node, and decide to insert left or right
    else {<!-- -->
        if (data < root->data) {<!-- -->
            root->left = insert(root->left, data);
        } else if (data > root->data) {<!-- -->
            root->right = insert(root->right, data);
        }
    }
    return root;
}

//Inorder traversal function
void inorder(struct node *root) {<!-- -->
    if (root == NULL) {<!-- -->
        return;
    }
    inorder(root->left);
    printf("%d ", root->data);
    inorder(root->right);
}

int main() {<!-- -->
    struct node *root = NULL;
    root = insert(root, 9);
    insert(root, 6);
    insert(root, 15);
    insert(root, 3);
    insert(root, 8);
    insert(root, 12);
    insert(root, 18);
    printf("Inorder traversal result:");
    inorder(root);
    printf("\\
");
    return 0;
}

?

2. The concept and introduction of heap

The heap is a sequential structure binary tree.

If there is a set of key codes K = {K0, K1, K2, K3…, Kn-1}, store all its elements in a one-dimensional array in the order of a complete binary tree, and satisfy:< strong>Ki<=K2i + 1 and Ki<= K2i + 2 (Ki >=K2i + 1 and Ki>=K2i + 2 ) i = 0, 1, 2…, it is called a small heap (or a large heap). The heap with the largest root node is called the largest heap or large root heap, and the heap with the smallest root node is called the smallest heap or small root heap.

A heap has the following properties:
? (1) The value of a certain node in the heap is always not greater than or not less than the value of its parent node;
? (2) The heap is always a complete binary tree.

?
Simple implementation of heap in C language (reference)

#include <stdio.h>

#define MAX_HEAP_SIZE 100

typedef struct {<!-- -->
    int data[MAX_HEAP_SIZE];
    int size;
} MaxHeap;

// insert element
void insert(MaxHeap *heap, int value) {<!-- -->
    int i = + + (heap->size);
    while (i != 1 & amp; & amp; value > heap->data[i/2]) {<!-- -->
        heap->data[i] = heap->data[i/2];
        i = i/2;
    }
    heap->data[i] = value;
}

// delete the top element
int delete(MaxHeap *heap) {<!-- -->
    if (heap->size == 0) {<!-- -->
        printf("The heap is empty and cannot be deleted!\\
");
        return -1;
    }

    int max = heap->data[1];
    int last = heap->data[heap->size--];
    int i = 1, child;
    while (i*2 <= heap->size) {<!-- -->
        child = i*2;
        if (child + 1 <= heap->size & amp; & amp; heap->data[child + 1] > heap->data[child])
            child ++ ;
        if (last < heap->data[child])
            heap->data[i] = heap->data[child];
        else
            break;
        i = child;
    }
    heap->data[i] = last;
    return max;
}

// Find the top element of the heap
int find_max(MaxHeap heap) {<!-- -->
    if (heap. size == 0) {<!-- -->
        printf("heap is empty!\\
");
        return -1;
    }

    return heap. data[1];
}

// heap sort
void heap_sort(MaxHeap *heap) {<!-- -->
    while (heap->size != 0) {<!-- -->
        printf("%d ", delete(heap));
    }
}

int main() {<!-- -->
    MaxHeap heap = {<!-- -->{<!-- -->0}, 0};
    insert( & heap, 6);
    insert( & heap, 12);
    insert( & heap, 8);
    insert( & heap, 15);
    insert( & heap, 5);
    insert( & heap, 10);

    printf("Heap sort result:");
    heap_sort( & heap);
    printf("\\
");

    return 0;
}

?

3. Binary tree traversal

The so-called binary tree traversal (Traversal) is to perform corresponding operations on the nodes in the binary tree in turn according to certain specific rules, and each node is only operated once. The operations performed by the access nodes depend on the specific application problem. Traversal is one of the most important operations on a binary tree, and it is also the basis for other operations on a binary tree.

According to the rules, the traversal of the binary tree includes: Preorder/Inorder/Postorder recursive structure traversal:

(1) Preorder Traversal (also known as preorder traversal)–The operation of visiting the root node occurs before traversing its left and right subtrees.
(2) Inorder Traversal (Inorder Traversal)–The operation of visiting the root node occurs in traversing its left and right subtrees (middle).
(3) Postorder Traversal–The operation of visiting the root node occurs after traversing its left and right subtrees.

3.1 Preorder traversal

The pre-order traversal of a binary tree refers to traversing the entire tree according to the traversal order of ?root node-left subtree-right subtree?. Preorder traversal can be implemented using recursive or iterative algorithms.
?
C language recursively implements preorder traversal:

struct TreeNode {<!-- -->
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

void preorderTraversal(struct TreeNode* root){<!-- -->
    if(root == NULL){<!-- -->
        return;
    }
    printf("%d ", root->val); // visit the root node
    preorderTraversal(root->left); // recursive left subtree
    preorderTraversal(root->right); // recursive right subtree
}

The C language iterative algorithm is implemented using a stack:

void preorderTraversal(struct TreeNode* root){<!-- -->
    if(root == NULL){<!-- -->
        return;
    }

    struct TreeNode *stack[1000]; // define a stack
    int top = 0;
    stack[top + + ] = root; // push the root node onto the stack

    while(top > 0){<!-- -->
        struct TreeNode *p = stack[--top]; // Pop the top element of the stack
        printf("%d ", p->val); // visit the root node

        if(p->right){<!-- --> // Push the right subtree node into the stack first
            stack[top + +] = p->right;
        }
        if(p->left){<!-- --> // push the left subtree node onto the stack
            stack[top + +] = p->left;
        }
    }
}

?

3.2 Inorder traversal

The preorder traversal of a binary tree refers to traversing the entire tree in accordance with the traversal order of ?left node-root subtree-right subtree?. Preorder traversal can be implemented using recursive or iterative algorithms.
?
C language recursively implements inorder traversal:

struct TreeNode {<!-- -->
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

void inorderTraversal(struct TreeNode* root){<!-- -->
    if(root == NULL){<!-- -->
        return;
    }
    inorderTraversal(root->left); // recursive left subtree
    printf("%d ", root->val); // visit the root node
    inorderTraversal(root->right); // recursive right subtree
}

The C language iterative algorithm is implemented using a stack:

void inorderTraversal(struct TreeNode* root){<!-- -->
    if(root == NULL){<!-- -->
        return;
    }

    struct TreeNode *stack[1000]; // define a stack
    int top = 0;
    struct TreeNode *p = root;

    while(p != NULL || top > 0){<!-- -->
        while(p != NULL){<!-- --> // Push the left subtree node onto the stack
            stack[top++] = p;
            p = p->left;
        }

        if(top > 0){<!-- --> // Pop the top element of the stack
            p = stack[--top];
            printf("%d ", p->val); // visit the root node
            p = p->right; // Push the right subtree node onto the stack
        }
    }
}

?

3.3 Post-order traversal

The pre-order traversal of a binary tree refers to traversing the entire tree according to the traversal order of ?left node-right subtree-root subtree?. Preorder traversal can be implemented using recursive or iterative algorithms.
?
C language recursively implements post-order traversal:

struct TreeNode {<!-- -->
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

void postorderTraversal(struct TreeNode* root){<!-- -->
    if(root == NULL){<!-- -->
        return;
    }
    postorderTraversal(root->left); // recursive left subtree
    postorderTraversal(root->right); // recursive right subtree
    printf("%d ", root->val); // visit the root node
}

The C language iterative algorithm is implemented using a stack:

void postorderTraversal(struct TreeNode* root){<!-- -->
    if(root == NULL){<!-- -->
        return;
    }

    struct TreeNode *stack1[1000]; // define two stacks
    struct TreeNode *stack2[1000];
    int top1 = 0, top2 = -1;
    struct TreeNode *p = root;

    while(p != NULL || top1 > 0){<!-- --> // traverse all nodes
        while(p != NULL){<!-- --> // First push the left subtree into the stack 1
            stack1[top1++] = p;
            stack2[ + + top2] = 0; // mark the current node in stack 2 as unvisited
            p = p->left;
        }

        while(top1 > 0 & amp; & amp; stack2[top2] == 1){<!-- --> // When stack 1 is not empty and the top node in stack 2 has been marked, pop the node and access
            p = stack1[--top1];
            printf("%d ", p->val);
            top2--;
        }

        if(top1 > 0){<!-- --> // Push the right child node of the top node into stack 1, and mark it as unvisited in stack 2
            p = stack1[top1-1]->right;
            stack2[top2] = 1;
        }
        else{<!-- --> // If stack 1 is empty, the traversal ends
            break;
        }
    }
}

?

3.4 Layer sequence traversal

The level order traversal of the binary tree refers to traversing layer by layer according to the level of the tree?order?That is, from top to bottom, from left to right to traverse all nodes of each layer . The level-order traversal of the binary tree can be realized through the queue.

C language queue implements hierarchical order traversal:

struct TreeNode {<!-- -->
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

void levelOrderTraversal(struct TreeNode* root){<!-- -->
    if(root == NULL){<!-- -->
        return;
    }

    struct TreeNode *queue[1000]; // define a queue
    int front = 0, rear = 0;
    queue[rear + + ] = root; // enqueue the root node

    while(front < rear){<!-- --> // loop while the queue is not empty
        struct TreeNode *p = queue[front + + ]; // Take out the head node of the queue and visit
        printf("%d ", p->val);

        if(p->left){<!-- --> // Enqueue the left child node
            queue[rear + +] = p->left;
        }
        if(p->right){<!-- --> // Enqueue the right child node
            queue[rear + + ] = p->right;
        }
    }
}

That’s it for a brief introduction to binary tree implementation and traversal in data structures
If there are any mistakes? I hope to correct them. Finally, I wish you all progress in your studies? Happy every day?