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?