# The C language data structure binary tree is simple to use

• 2020-05-19 05:27:13
• OfStack

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