Using C language to build the basic binary tree data structure

Binomial tree structure is commonly used for some initialization code

#include
#include

typedef struct Node{
 int data;
 Node *leftchild;
 Node *rightchild;
}Node;



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;
}


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;
 }
}


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 binary tree is constructed according to preorder sequence and middle order sequence
The function definitions

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

Parameters:
* pre: preorder traversal of the resulting array of strings
* in: in order traverses the resulting array of strings
Len: the length of the tree
Such as:
Preorder traversal result: a, b, c, d, e, f, g, h
C, b, e, d, f, a, g, h

Algorithm thought

      The idea of recursion, the end of recursion is the length of the tree, len == 0       The first character of the previous ordinal group is found in the array traversed by the middle sequence, and the position index is recorded in the middle sequence group. Find index, create a new binary tree node t, t- > Item = *pre, and then recursively find the left child of t and the left child of t       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)

   

  
 bt rebuildTree(char *pre, char *in, int len) 
 { 
  bt t; 
  if(len <= 0) 
  { 
   //The recursion terminates
   t = NULL; 
  }else 
  { 
   //Recursive subject
   int index = 0; 
    
   while(index < len && *(pre) != *(in + index)) 
   { 
    index ++; 
   } 
    
   if(index >= len) 
   { 
    printf(" There is a problem with preorder traversal or middle 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 binary tree is constructed according to the middle sequence and the post sequence
The function definitions

  
 btree* rebuildTree(char *order, char *post, int len); 

Algorithm thought
Middle sequence: C, B, E, D, F, A, H, G, J, I

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

Recursive thinking:

      According to the characteristics of sequential traversal, we know that the last node of sequential traversal is the root node, that is, A       In the order traversal of observation, CBEDF to the left of A is the left subtree node of A, and HGJI to the rear of A is the right subtree node of A       And then recursively build the left subtree and the back subtree of A

Implementation code (c code)

  
  
 #include <stdio.h> 
 #include <stdlib.h> 
 #include <string.h> 
  
 int n; 
  
 typedef struct btree { 
  struct btree *lchild; 
  struct btree *rchild; 
  char data; 
 } btree; 
  
  
 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; 
 } 
  
  
 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; 
 }