/*  

*Copyright (c)2017, School of computer and control engineering, Yantai University

*All rights reservrd.            

*Author: Li Xinhao

*Completion time: November 2, 2017

*Version number: v1.0

*Problem Description: binary tree algorithm verification

Run and repeat the algorithm involved in the teaching content. The significance of changing the test data for repeated test is that we can understand the algorithm from more angles to reach the degree of gradually grasping the algorithm. Use your test data, display the test results, and observe the running results to understand the algorithm.  

1, Verification of hierarchical traversal algorithm

The algorithm of binary tree traversal is implemented, and the binary tree created by "a (b (D, e (H (J, K (L, m (, n))))), C (F, G (, I))" is tested.  

Based on binary tree algorithm library, the header file btree.h is established

#ifndef BTREE_H_INCLUDED
#define BTREE_H_INCLUDED

#define MaxSize 100
typedef char ElemType;
typedef struct node
{
    ElemType data;              //data elements
    struct node *lchild;        //Point to the left child
    struct node *rchild;        //Point to the right child
} BTNode;
void CreateBTNode(BTNode *&b,char *str);        //Creating a binary chain from a str string
BTNode *FindNode(BTNode *b,ElemType x);     //Return node pointer with data field x
BTNode *LchildNode(BTNode *p);  //Returns the left child node pointer of the * p node
BTNode *RchildNode(BTNode *p);  //Returns the right child node pointer of the * p node
int BTNodeDepth(BTNode *b); //Finding the depth of binary tree b
void DispBTNode(BTNode *b); //Output binary tree in parenthesis
void DestroyBTNode(BTNode *&b);  //Destroy binary tree
void LevelOrder(BTNode *b);  //Hierarchical traversal algorithm of binary tree

#endif // BTREE_H_INCLUDED

Implement each function in the source file btree.cpp

#include <stdio.h>
#include <malloc.h>
#include "btree.h"

void CreateBTNode(BTNode *&b,char *str)     //Creating a binary chain from a str string
{
    BTNode *St[MaxSize],*p=NULL;
    int top=-1,k,j=0;
    char ch;
    b=NULL;             //The binary tree is initially empty
    ch=str[j];
    while (ch!='\0')    //Cycle when str is not finished scanning
    {
        switch(ch)
        {
        case '(':
            top++;
            St[top]=p;
            k=1;
            break;      //Left node
        case ')':
            top--;
            break;
        case ',':
            k=2;
            break;                          //Right node
        default:
            p=(BTNode *)malloc(sizeof(BTNode));
            p->data=ch;
            p->lchild=p->rchild=NULL;
            if (b==NULL)                    //p points to the root node of a two tree
                b=p;
            else                            //Binary tree root node established
            {
                switch(k)
                {
                case 1:
                    St[top]->lchild=p;
                    break;
                case 2:
                    St[top]->rchild=p;
                    break;
                }
            }
        }
        j++;
        ch=str[j];
    }
}
BTNode *FindNode(BTNode *b,ElemType x)  //Return node pointer with data field x
{
    BTNode *p;
    if (b==NULL)
        return NULL;
    else if (b->data==x)
        return b;
    else
    {
        p=FindNode(b->lchild,x);
        if (p!=NULL)
            return p;
        else
            return FindNode(b->rchild,x);
    }
}
BTNode *LchildNode(BTNode *p)   //Returns the left child node pointer of the * p node
{
    return p->lchild;
}
BTNode *RchildNode(BTNode *p)   //Returns the right child node pointer of the * p node
{
    return p->rchild;
}
int BTNodeDepth(BTNode *b)  //Finding the depth of binary tree b
{
    int lchilddep,rchilddep;
    if (b==NULL)
        return(0);                          //The height of the empty tree is 0
    else
    {
        lchilddep=BTNodeDepth(b->lchild);   //Find the height of left subtree lchilddep
        rchilddep=BTNodeDepth(b->rchild);   //Find the height of right subtree as rchilddep
        return (lchilddep>rchilddep)? (lchilddep+1):(rchilddep+1);
    }
}
void DispBTNode(BTNode *b)  //Output binary tree in parenthesis
{
    if (b!=NULL)
    {
        printf("%c",b->data);
        if (b->lchild!=NULL || b->rchild!=NULL)
        {
            printf("(");
            DispBTNode(b->lchild);
            if (b->rchild!=NULL) printf(",");
            DispBTNode(b->rchild);
            printf(")");
        }
    }
}
void DestroyBTNode(BTNode *&b)   //Destroy binary tree
{
    if (b!=NULL)
    {
        DestroyBTNode(b->lchild);
        DestroyBTNode(b->rchild);
        free(b);
    }
}
void LevelOrder(BTNode *b)
{
    BTNode *p;
    BTNode *qu[MaxSize];    //Define a circular queue to hold node pointers
    int front,rear; //Define team head and tail pointers
    front=rear=-1;      //Make queue empty
    rear++;
    qu[rear]=b;     //Root node pointer into queue
    while (front!=rear) //Queue is not empty
    {
        front=(front+1)%MaxSize;
        p=qu[front];        //Out of line
        printf("%c ",p->data);  //Access node
        if (p->lchild!=NULL)    //Team up with left child
        {
            rear=(rear+1)%MaxSize;
            qu[rear]=p->lchild;
        }
        if (p->rchild!=NULL)    //Join the team when you have a right child
        {
            rear=(rear+1)%MaxSize;
            qu[rear]=p->rchild;
        }
    }
}

Implementation in main.cpp Verification of hierarchical traversal algorithm

#include <stdio.h>
#include "btree.h"

int main()
{
    BTNode *b;
    CreateBTNode(b,"A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))");
    printf("Two fork tree b: ");
    DispBTNode(b);
    printf("\n");
    printf("Hierarchical ergodic sequence:\n");
    LevelOrder(b);
    DestroyBTNode(b);
    return 0;
}

Two. Verification of binary tree construction algorithm

Functions are required in addition to those in btree.h

BTNode *CreateBT1(char *pre,char *in,int n)
{
    BTNode *s;
    char *p;
    int k;
    if (n<=0) return NULL;
    s=(BTNode *)malloc(sizeof(BTNode));     //Create a binary tree node * s
    s->data=*pre;
    for (p=in; p<in+n; p++)                 //Find the position k equal to * ppos in the middle order sequence
        if (*p==*pre)                       //pre points to the root node
            break;                          //Exit loop when found in
    k=p-in;                                 //Determine the position of root node in
    s->lchild=CreateBT1(pre+1,in,k);        //Recursive construction of left subtree
    s->rchild=CreateBT1(pre+k+1,p+1,n-k-1); //Recursively constructing right subtree
    return s;
}

The main function is as follows:

int main()
{
    ElemType pre[]="ABDGCEF",in[]="DGBAECF";
    BTNode *b1;
    b1=CreateBT1(pre,in,7);
    printf("b1:");
    DispBTNode(b1);
    printf("\n");
    return 0;
}