# Week 10 [item 1 - binary tree algorithm verification]

/*

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

Published 45 Original Articles· Zan Zan 2. Visits 4924

Added by netcoord99 on Fri, 03 Apr 2020 08:07:17 +0300