Build basic binary tree data structures using C language

Updated: August 19, 2015 12:19:29 by FinL

This article mainly introduces the use of C language to use C language to build basic binary tree data structures, including the method of building binary trees according to preorder sequence and mid-order sequence, the need of friends can refer to the next

Binary tree structure commonly used some initialization code

#include #include typedef struct Node{ int data; Node *leftchild; Node *rightchild; }Node; /* Initializes a binary tree sort tree. */ void InitBinaryTree(Node**root,int elem) { *root=(Node*)malloc(sizeof(Node)); if(! (*root)) { printf("Memory allocation for root failed.\n"); return; } (*root)->data=elem; (*root)->leftchild=NULL; (*root)->rightchild=NULL; } /* Inserts a node into a binary tree sort tree. */ void InsertNode(Node *root,int elem) { Node *newnode=NULL; Node *p=root,*last_p=NULL; newnode=(Node*)malloc(sizeof(Node)); if(! newnode) { printf("Memory allocation for newnode failed.\n"); return; } newnode->data=elem; newnode->leftchild=NULL; newnode->rightchild=NULL; while(NULL! =p) { last_p=p; if(newnode->datadata) { p=p->leftchild; } else if(newnode->data>p->data) { p=p->rightchild; } else { printf("Node to be inserted has existed.\n"); free(newnode); return; } } p=last_p; if(newnode->datadata) { p->leftchild=newnode; } else { p->rightchild=newnode; }} /* Creates a binary tree sort tree. */ void CreatBinarySearchTree(Node **root,int data[],int num) { int i; for(i=0; i { if(NULL==*root) { InitBinaryTree(root,data[i]); } else { InsertNode(*root,data[i]); }}}

The definition of binary tree function is constructed according to preorder sequence and inorder sequence

 bt rebuildTree(char *pre, char *in, int len);

Parameters: * pre: string array of preorder traversal results * in: string array of mid-order traversal results len: length of the tree Example: preorder traversal result: a b c d e f g h Mid-order traversal result: c b e d f a g h

Algorithmic thought

The idea of recursion is that the terminating condition of recursion is the length len == 0 of the tree
Finds the first character of the preordinal group in an array traversed in mid-order, recording the position index in the mid-ordinal group. If it cannot be found, it indicates that there is a problem with the preorder pass group and the middle order pass group, and an error message is displayed. Exit the program. After finding index, create a new binary tree node t, t->item = *pre, and recursively find t's left child and has children
Recursive left child: void rebuildTree(pre + 1, in, index)
Recursive right child: void rebuildTree(pre + (index + 1), in + (index + 1), len - (index + 1))

Implementation code (c language version)

/** * Description: Build binary trees from preorder and midorder */ bt rebuildTree(char *pre, char *in, int len) {bt t; if(len <= 0) {// recursive termination t = NULL; }else {// recursive body int index = 0; while(index < len && *(pre) ! = *(in + index)) { index ++; } if(index >= len) {printf(" There is a problem with preorder or mid-order traversal groups! \n"); exit(-1); } t = (struct bintree *)malloc(sizeof(struct bintree)); t->item = *pre; t->lchild = rebuildTree(pre + 1, in, index); t->rchild = rebuildTree(pre + (index + 1), in + (index + 1), len - (index + 1)); } return t; }

The definition of binary tree function is constructed according to the middle order sequence and the post order sequence

/** * In-order and post-order sequences build binary trees */ btree* rebuildTree(char *order, char *post, int len);

The sequence in the algorithm idea: C, B, E, D, F, A, H, G, J, I

Postsequence: C, E, F, D, B, H, J, I, G, A

Recursive thinking:

According to the characteristics of post-order traversal, we know that the last node of post-order traversal is the root node, that is, A
In order traversal, CBEDF on the left side of A is the left subtree node of A, and HGJI on the rear side of A is the right subtree node of A
Then recursively build the left subtree and the back subtree of A

Implementation code (c code)

/** * According to the middle order and post order sequence to build a binary tree * (ps: Last night to participate in the Ali written test, wait until the final said that you can skip the written test direct interview, today is estimated to be according to the school screening, haha, in order to this * also have to participate in the Ali written test, Can't let their own school be despised) */ #include <stdio.h> #include <stdlib.h> #include <string.h> int n; typedef struct btree { struct btree *lchild; struct btree *rchild; char data; } btree; /** * In-order and post-order sequences build binary trees */ btree* rebuildTree(char *order, char *post, int len) {btree* t; if (len <= 0) { return NULL; } else { int index = 0; while (index < len && *(post + len - 1) ! = *(order + index)) { index ++; } t = (btree *)malloc(sizeof(btree)); t->data = *(order + index); t->lchild = rebuildTree(order, post, index); t->rchild = rebuildTree(order + index + 1, post + index, len - (index + 1)); } return t; } /** * Preorder traversal of binary tree */ void preTraverse(btree *t) {if (t) {printf("%c ", t->data); preTraverse(t->lchild); preTraverse(t->rchild); } } int main(void) { int i; char *post, *order; btree *t; while (scanf("%d", &n) ! = EOF) { post = (char *)malloc(n); order = (char *)malloc(n); getchar(); for (i = 0; i < n; i ++) scanf("%c", order + i); getchar(); for (i = 0; i < n; i ++) scanf("%c", post + i); t = rebuildTree(order, post, n); preTraverse(t); printf("\n"); free(post); free(order); } return 0; }

Articles you may be interested in:

C++ with two standard containers stack, to achieve a queue method detailed explanation

This article is a detailed analysis of C++ using two standard containers stack, to achieve a queue method, the need for a friend's reference
2013-05-05
Use OpenGL to create a window example detailed

OpenGL, or Open Graphics Library. It is mainly used for us to render 2D, 3D vector graphics a cross-language, cross-platform application programming interface, this article mainly introduces the use of OpenGL to create Windows, need friends can refer to the next
2022-04-04
A brief discussion on C++ statement syntax and forced data type conversion

This article mainly introduces C++ sentence syntax and forced data type conversion, is the basic knowledge of C++ learning, need friends can refer to the next
2015-09-09
Use Matlab to draw a dedicated progress bar

MATLAB's own progress bar is very simple, such progress bar seems cold. Therefore, this article will use Matlab to DIY a special progress bar, interested partners can understand
2022-02-02
C++ string commonly used to intercept string methods

This article mainly introduces the C++ string commonly used to intercept the string method, the article through the example code is very detailed, for everyone's study or work has a certain reference learning value, the need of friends below with the small series to learn it
2019-05-05
QT uses QComBox and QLineEdit to implement fuzzy queries

Fuzzy query means that according to the text input by the user, the options in the drop-down box are fuzzy matched, and the matched options are displayed dynamically. This article will use QComBox and QLineEdit to achieve fuzzy query function. If necessary, you can refer to the following
2023-11-11
Use of map and set in C++ with examples

map and set are part of the STL container. This article mainly introduces the summary of the use of map and set in C++. The article introduces it in detail through the example code, which has certain reference and learning value for everyone's study or work
2024-01-01
C++/C palindromic string example details

This article mainly introduces the C++ palindromic string example detailed explanation of the relevant information, the need for friends can refer to the next
2017-07-07
C++ std::count function introduction and usage scenarios

std::count function is a very practical algorithm, it can help us quickly count the number of occurrence of a given value within a specified range, this article mainly introduces the std::count function in C++ introduction and use scenarios, interested in you can understand
2024-02-02
C++ implementation screen capture (full screen capture)

Screenshots have become a must-have module of all IM instant messaging software and one of the most frequently used functions in daily office work. Today, from the perspective of C++ development, we will take a look at how the main function points of screen shots are realized
2021-11-11