Related operations of binary tree

Problem description

Implement the following algorithms ：
1． A binary tree is represented by a binary list , Build a binary tree ;
2． Output binary tree in order traversal results ;
3． Output binary tree preorder traversal results ;
4． Output binary tree after the order traversal results ;
5. Output the sequence traversal result of binary tree .
6. Exchange the left and right children of each node in the binary tree .
7． Use binary tree to calculate the value of expression . Build expression tree , And compute the value of the expression
8. Sequence of trees zigzag Output , The tree traverses in sequence , Odd layers output from left to right , Even layers output from right to left .

---

Tips ： The following is the main body of this article , The following cases can be used for reference

Complete code

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
using namespace std;

typedef struct BTNode *Position;
typedef Position BTree;
struct BTNode
{
    
    char data;
    Position lChild, rChild;
};
// Establish a binary function  
BTree CreateBTree(BTree bt)
{
    
    char ch;
    
    printf(" node : ");

    fflush(stdin);         /*  Clear cache  */
    scanf("%c", &ch);
    fflush(stdin);
    if (ch != '#')// appear # That is, the node has no left （ Right ） children  
    {
    
        
        bt = new BTNode;
        bt->data = ch;  
        bt->lChild = NULL;
        bt->rChild = NULL;
        printf("%c The left child : ", bt->data);
        bt->lChild = CreateBTree(bt->lChild);
        printf("%c The right child : ", bt->data);
        bt->rChild = CreateBTree(bt->rChild);
    }
    return bt;
}
// The first sequence traversal  
void PreOrder(BTree bt)
{
    
    if (bt != NULL)
    {
    
        printf("%c", bt->data);
        PreOrder(bt->lChild);
        PreOrder(bt->rChild);
    }
}
// In the sequence traversal  
void InOrder(BTree bt)
{
    
    if (bt != NULL)
    {
    
        InOrder(bt->lChild);
        printf("%c", bt->data);
        InOrder(bt->rChild);
    }
}
// After the sequence traversal 
void PostOrder(BTree bt)
{
    
    if (bt != NULL)
    {
    
        PostOrder(bt->lChild);
        PostOrder(bt->rChild);
        printf("%c", bt->data);
    }
}
// Sequence traversal  
void CenOrder(BTree bt)
{
    
    BTree temp[100];
    int in=0,out=0;
    temp[in++]=bt;
    while(in>out){
    
    	if(temp[out]){
    
    		printf("%c",temp[out]->data);
    		temp[in++]=temp[out]->lChild;
    		temp[in++]=temp[out]->rChild;
		}
		out++;
	}
}
//zigzag Sequence traversal  
void ZigZagOrder(BTree bt)
{
    
    BTree temp[100];
    int in=0,out=0,k,i,j;
    temp[in++]=bt;
    while(in>out){
    
    	if(temp[out]){
    
    		temp[in++]=temp[out]->lChild;
    		temp[in++]=temp[out]->rChild;
		}
		out++;
	}
	k=ceil(log(in+1)/log(2));
	printf("%c",temp[0]->data);
	for(i=2;i<=k;i++){
    
		if(i%2==1){
    
			for(j=pow(2,i-1);j<=pow(2,i)-1;j++){
    
				if(temp[j-1]!=NULL)
				printf("%c",temp[j-1]->data);
			}
		}
		else{
    
			for(j=pow(2,i)-1;j>=pow(2,i-1);j--){
    
				if(temp[j-1]!=NULL)
				printf("%c",temp[j-1]->data);
			}
		}
	}
}
// Swap the left and right children of each node 
BTree Change(BTree bt)
{
    
	BTree t;
	if(bt->data!='#'){
    
		if(bt->lChild != NULL&&bt->rChild != NULL){
    
			Change(bt->lChild);
	    	Change(bt->rChild);
		}
	    t=bt->lChild;
	    bt->lChild=bt->rChild;
	    bt->rChild=t;
	}
	return bt;
}

int main()
{
    
    int choose=-1;
    printf("1、 Build a binary tree \n");
	printf("2、 The first sequence traversal \n");
	printf("3、 In the sequence traversal \n");
	printf("4、 After the sequence traversal \n");
	printf("5、 Sequence traversal \n");
	printf("6、 Swap the left and right children of each node \n");
	printf("7、zigzag Sequence traversal \n");
	printf("0、 sign out \n\n");
    while(choose!=0){
    
    	printf(" Please select ：");
    	scanf("%d", &choose);
    	switch (choose){
    
    		case 1:
    			BTree bt;
    			bt = CreateBTree(bt);
    			printf(" Successfully established binary tree \n");
    			break;
    		case 2:
    			printf(" The first sequence traversal ：");
    			PreOrder(bt);
    			printf("\n");
    			break;
    		case 3:
    			printf(" In the sequence traversal ：");
    			InOrder(bt);
    			printf("\n");
    			break;
    		case 4:
    			printf(" After the sequence traversal ：");
    			PostOrder(bt);
    			printf("\n");
    			break;
			case 5:
				printf(" Sequence traversal ：");
				CenOrder(bt);
				printf("\n");
				break;
			case 6:
				Change(bt);
				printf(" The exchange was successful ！\n");
				break;
			case 7:
				printf("zigzag Sequence traversal ：");
				ZigZagOrder(bt);
				printf("\n");
				break;
		}
	}
	getchar();
    return 0;
}

experimental result

Build a binary tree