数据结构树二叉树的建立及遍历 C语言版

ゝ一纸荒年。 2022-06-09 04:24 164阅读 0赞

//二叉树的建立以及先序、中序、后序遍历算法 以及统计二叉树的叶子结点数目算法
    #include <stdio.h>
    #include <stdlib.h>
    typedef char DataType;
    typedef struct Node
    {
    	DataType data;
    	struct Node *LChild;
    	struct Node *RChild;
    } BiTNode,*BiTree;   //定义二叉树
    
    void CreateBiTree(BiTree *bt)  //用先序遍历创建二叉树
    {
    	char ch;
    	ch=getchar();
    	if(ch=='.') (*bt)=NULL;
    	else
    	{
    		*bt=(BiTree)malloc(sizeof(BiTNode));
    		(*bt)->data=ch;
    		CreateBiTree(&((*bt)->LChild));
    		CreateBiTree(&((*bt)->RChild));
    	}
    }
    
    void PreOrder(BiTree root) //先序遍历二叉树
    {
    	if(root!=NULL)
    	{
    		printf("%c",root->data);
    		PreOrder(root->LChild);
    		PreOrder(root->RChild);
    	}
    
    }
    
    void InOrder(BiTree root)  //中序遍历二叉树
    {
    	if(root!=NULL)
    	{
    		InOrder(root->LChild);
    		printf("%c",root->data);
    		InOrder(root->RChild);
    	}
    }
    
    void PostOrder(BiTree root) //后序遍历二叉树
    {
    	if(root!=NULL)
    	{
    		PostOrder(root->LChild);
    		PostOrder(root->RChild);
    		printf("%c",root->data);
    	}
    }
    
    int LeafCount=0;
    void leaf(BiTree root)  //求出叶子结点的数目
    {
    	if(root!=NULL)
    	{
    		leaf(root->LChild);
    		leaf(root->RChild);
    		if(root->LChild==NULL && root->RChild==NULL)
    		LeafCount++;
    	}
    }
    
    int main()
    {
    	BiTree bt;
    	printf("用先序遍历创建二叉树 请输入树的内容 形式如AB..CD...的格式\n") ;
    	CreateBiTree(&bt);
    
    	PreOrder(bt);
    	printf("\n");
    	InOrder(bt);
    	printf("\n");
    	PostOrder(bt);
    	printf("\n");
    
    	printf("这棵树的叶子结点数目为：\n");
    	leaf(bt);
    	printf("%d\n",LeafCount);
    
    	return 0;
    }