Establishment and traversal of binary tree (implemented in C language)

Binary tree

Definition of binary tree structure

typedef struct BiTNode {
    
	TElemType data;
	struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;

The establishment of binary tree

Expand the binary tree input according to the previous order

void CreatBiTree(BiTree* T) 
{
    
	TElemType ch;
	scanf("%c",&ch);
	if(ch == '#')
	{
    
		*T = NULL;	// If the input is # Set the address of the node to NULL 
	}
	else
	{
    
		*T = (BiTree) malloc(sizeof(BiTNode));
		if(!T)
		{
    
			exit(OVERFLOW);
		}
		(*T)->data = ch;
		CreatBiTree(&(*T)->lchild);
		CreatBiTree(&(*T)->rchild);
	}
}

When typing this code , I have always had a doubt , Is to ask why it needs to pass a double pointer in this place , So when I wrote it, I changed it to use pointer variables , Instead of double pointers , After writing , An error occurred while outputting , The found value is not passed into the binary tree , Then it was changed to the original version , Use double pointers , Just make mistakes , This should be the problem of formal parameters and arguments , A little confused , I still need to read more books ……

Another problem is that when you create input, you can't input characters one by one , Instead, you can only lose all at once , He will jump out of the cycle , Now I don't know the reason ……

Traversal of binary tree （ Recursive implementation ）

The former sequence traversal

void PreOrderTraverse(BiTree T)
{
    
	if(!T)
	{
    
		return;
	}
	printf("%c",T->data);
	PreOrderTraverse(T->lchild);
	PreOrderTraverse(T->rchild);
}

In the sequence traversal

void InOrderTraverse(BiTree T)
{
    
	if(!T)
	{
    
		return;
	}
	InOrderTraverse(T->lchild);
	printf("%c",T->data);
	InOrderTraverse(T->rchild);
}

After the sequence traversal

void PostOrderTraverse(BiTree T)
{
    
	if(!T)
	{
    
		return;
	}
	PostOrderTraverse(T->lchild);
	PostOrderTraverse(T->rchild);
	printf("%c",T->data);
}

experimental result

Complete code

/* Binary tree */

#include <stdio.h>
#include <stdlib.h>

#define OVERFLOW 0
typedef char TElemType;

// Define the structure of the nodes of the tree ,BiTree Pointer variable of node  
typedef struct BiTNode {
    
	TElemType data;
	struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;

void CreatBiTree(BiTree* T) 
{
    
	TElemType ch;
	scanf("%c",&ch);
	if(ch == '#')
	{
    
		*T = NULL;	// If the input is # Set the address of the node to NULL 
	}
	else
	{
    
		*T = (BiTree) malloc(sizeof(BiTNode));
		if(!T)
		{
    
			exit(OVERFLOW);
		}
		(*T)->data = ch;
		CreatBiTree(&(*T)->lchild);
		CreatBiTree(&(*T)->rchild);
	}
}

// Recursive implementation of preorder traversal  
void PreOrderTraverse(BiTree T)
{
    
	if(!T)
	{
    
		return;
	}
	printf("%c",T->data);
	PreOrderTraverse(T->lchild);
	PreOrderTraverse(T->rchild);
}

// Recursive implementation of middle order traversal  
void InOrderTraverse(BiTree T)
{
    
	if(!T)
	{
    
		return;
	}
	InOrderTraverse(T->lchild);
	printf("%c",T->data);
	InOrderTraverse(T->rchild);
}

// Recursive implementation of subsequent traversal  
void PostOrderTraverse(BiTree T)
{
    
	if(!T)
	{
    
		return;
	}
	PostOrderTraverse(T->lchild);
	PostOrderTraverse(T->rchild);
	printf("%c",T->data);
}

int main()
{
    
	printf(" Please expand the binary tree in the previous order to enter ："); 
	BiTree t;
	CreatBiTree(&t);
	printf(" The binary tree was established successfully ！！！\n");
	printf(" The former sequence traversal ："); 
	PreOrderTraverse(t);
	printf("\n");
	printf(" In the sequence traversal ："); 
	InOrderTraverse(t);
	printf("\n");
	printf(" After the sequence traversal ："); 
	PostOrderTraverse(t);
	printf("\n");
	
	return 0;
}