The C language data structure binary tree is simple to use

C language data structure 2 fork tree simple application

In computer science, a two-fork tree is a tree structure with at most two subtrees per node. Usually the subtree is called the left subtree (left subtree) and the right subtree (right subtree). Here I will introduce you to the simple use of 2 fork trees in the algorithm:

So we're going to do a total of

(1) creation of a two-fork tree

(2) recursive traversal of the middle and post-order of the two-fork tree

(3) counted the total number of leaf nodes

(4) find the height of the tree

(5) reverse the two-fork tree

(6) output the path from each leaf node to the root node

(7) output the path from root node to each leaf node.

Defines a structure of type 2 fork tree nodes

typedef struct node{ 
  char data; 
  struct node *Lchild; 
  struct node *Rchild; 
}BiTNode,*BiTree; 
int cnt=0;// Count the number of leaf nodes  

Creation of a two-fork tree

BiTNode *Create(){ //2 The first order of the fork tree is established   
  char ch; 
  BiTNode *s; 
  ch=getchar(); 
  if(ch=='#')erchashu  
    return NULL; 
  s=(BiTNode *)malloc(sizeof(BiTNode)); 
  s->data=ch; 
  s->Lchild=Create(); 
  s->Rchild=Create(); 
  return s; 
} 

The first, middle and last order recursive traversal of 2 fork trees

void PreOrder(BiTree root){   // The former sequence traversal   
  if(root){ 
    printf("%c ",root->data); 
    PreOrder(root->Lchild); 
    PreOrder(root->Rchild); 
  } 
} 
 
void InOrder(BiTree root){   // In the sequence traversal   
  if(root){ 
    InOrder(root->Lchild); 
    printf("%c ",root->data); 
    InOrder(root->Rchild); 
  } 
} 
 
void PostOrder(BiTree root){    // After the sequence traversal   
  if(root){ 
    PostOrder(root->Lchild); 
    PostOrder(root->Rchild); 
    printf("%c ",root->data); 
  } 
} 

Count the number of leaf nodes:

void LeafCountNode(BiTree root){  // Count the number of leaf nodes   
  if(root){ 
    if(!root->Lchild && !root->Rchild) 
      cnt++; 
    LeafCountNode(root->Lchild); 
    LeafCountNode(root->Rchild); 
  } 
}  

Output the values of each leaf node:

void IInOrder(BiTree root){ // Output the values of each leaf node   
  if(root){ 
    IInOrder(root->Lchild); 
    if(!root->Lchild && !root->Rchild)  
      printf("%c ",root->data); 
    IInOrder(root->Rchild); 
  } 
} 

Find the height of the tree:

int PostTreeDepth(BiTree root){       // Find the height of the tree   
  int h1,h2,h; 
  if(root==NULL){ 
    return 0; 
  } 
  else{ 
    h1=PostTreeDepth(root->Lchild); 
    h2=PostTreeDepth(root->Rchild); 
    h=(h1>h2?h1:h2)+1; 
    return h; 
  } 
} 

Reverse 2 fork tree:

void MirrorTree(BiTree root){        //2 A fork tree mirrors a tree   
  BiTree t; 
  if(root==NULL) 
    return; 
  else{ 
    t=root->Lchild; 
    root->Lchild=root->Rchild; 
    root->Rchild=t; 
    MirrorTree(root->Lchild); 
    MirrorTree(root->Rchild); 
  } 
} 

Output the path from each leaf node to the root node:

void OutPutPath(BiTree root,char path[],int len){      // Output the path from each leaf node to the root node   
  if(root){ 
    if(!root->Lchild && !root->Rchild){ 
      printf("%c ",root->data); 
      for(int i=len-1;i>=0;i--) 
        printf("%c ",path[i]); 
      printf("\n");   
    } 
    path[len]=root->data; 
    OutPutPath(root->Lchild,path,len+1); 
    OutPutPath(root->Rchild,path,len+1); 
  } 
} 

The path from the output root to each leaf node:

void PrintPath(BiTree root,char path[],int l){     // Output the path from the root to each leaf node  
  int len=l-1; 
  if(root){ 
    if(root->Lchild==NULL && root->Rchild==NULL){ 
      path[len]=root->data; 
      for(int i=9;i>=len;i--) 
        printf("%c ",path[i]); 
      printf("\n"); 
    } 
    path[len]=root->data; 
    PrintPath(root->Lchild,path,len); 
    PrintPath(root->Rchild,path,len); 
  }  
}  

Test code:

int main(void){ 
  int h,len; 
  char path[20]; 
  BiTree root; 
  root=Create(); 
// PreOrder(root); 
// printf("\n"); 
// InOrder(root); 
// printf("\n"); 
// PostOrder(root); 
// printf("\n"); 
// LeafCountNode(root); 
// printf(" The number of leaves is zero :%d\n",cnt); 
// IInOrder(root);  
  h=PostTreeDepth(root); 
  printf(" The height of the tree is zero :High=%d\n",h); 
// PrintTree(root,0); 
// MirrorTree(root);  
// PrintTree(root,0); 
// OutPutPath(root,path,0); 
// PrintPath(root,path,10);  
  return 0; 
} 

Thank you for reading, I hope to help you, thank you for your support of this site!