【数据结构】二叉树的递归遍历

傷城~ 2022-08-25 13:45 155阅读 0赞

#include <stdio.h>
    #include <stdlib.h>
    
    typedef char ElemType;
    typedef struct BiTree
    {
    	ElemType Elem;
    	BiTree * LChild;
    	BiTree * RChild;
    }BiTree,*PBiTree;
    
    /*建立二叉树*/
    PBiTree CreateBiTree();
    /*先序遍历二叉树*/
    void ProOrderTravel(PBiTree Tree);
    /*中序遍历二叉树*/
    void InOrderTravel(PBiTree Tree);
    /*后序遍历二叉树*/
    void PostOrderTravel(PBiTree Tree);
    
    void main()
    {
    	PBiTree BTree = CreateBiTree();
    
    	printf("先序排列为：\n");
    	ProOrderTravel(BTree);
    	printf("\n中序排列为：\n");
    	InOrderTravel(BTree);
    	printf("\n后序排列为：\n");
    	PostOrderTravel(BTree);
    	printf("\n");
    }
    
    PBiTree CreateBiTree()
    {
    	PBiTree T;
    	ElemType tmp;
    	scanf("%c",&tmp);
    
    	if (tmp == '#')
    	{
    		T = NULL;
    		return NULL;
    	}
    	else
    	{
    		T = (PBiTree)malloc(sizeof(BiTree));
    		T->Elem = tmp;
    		T->LChild = CreateBiTree();
    		T->RChild = CreateBiTree();
    	}
    
    	return T;
    }
    
    void ProOrderTravel(PBiTree Tree)
    {
    	if (Tree != NULL)
    	{
    		printf("%c\t",Tree->Elem);
    		ProOrderTravel(Tree->LChild);
    		ProOrderTravel(Tree->RChild);
    	}
    }
    
    void InOrderTravel(PBiTree Tree)
    {
    	if (Tree != NULL)
    	{
    		/* 如果有左子树，一直向下寻找 */
    		if (Tree->LChild != NULL) 
    		{
    			InOrderTravel(Tree->LChild);
    		}
    
    		printf("%c\t",Tree->Elem);
    
    		InOrderTravel(Tree->RChild);
    	}
    }
    
    void PostOrderTravel(PBiTree Tree)
    {
    	if (Tree != NULL)
    	{
    		/* 如果有左子树，一直向下寻找 */
    		if (Tree->LChild != NULL) 
    		{
    			PostOrderTravel(Tree->LChild);
    		}
    
    		PostOrderTravel(Tree->RChild);
    
    		printf("%c\t",Tree->Elem);
    	}
    }