【数据结构案例】二叉树创建、输出、遍历和查找叶子结点数

╰+哭是因爲堅強的太久メ 2024-03-31 14:05 27阅读 0赞

**案例介绍：**

1.创建一棵二叉树，然后输出每个结点，并给定二叉树的所有叶子结点个数。

2.实现二叉树的递归遍历算法，依次输出二叉树的先序、中序和后序遍历序列。

![c59e0ff1355d4823bca6fceff534a5b6.png][]

**运行结果：**

![af31c36a3f4f41388aefef41aaa091fb.png][]

**完整代码：**

#include <iostream>
    #include <stdio.h>
     
    typedef struct node
    {
    	char data;//数据元素 
    	struct node*lchild;//指向左孩子结点 
    	struct node*rchild;//指向右孩子结点 
    }BTNode,*BTree;
    
    //创建二叉树
    void CreateBTtree(BTree *b) 
    {
    	int i=0;
    	char ch;
    	scanf("%c",&ch);
    	if(ch=='#')//#表示子树为空 
    	{
    		*b=NULL;
    	}
    	else
    	{
    		*b=new BTNode;
    		(*b)->data=ch;
    		i++;
    		CreateBTtree(&(*b)->lchild);//递归创建左子树 
    		CreateBTtree(&(*b)->rchild);//递归创建右子树 
    	} 
    }
    //输出二叉树 
    void DispBTree(BTree b)
    {
    	if(b!=NULL)
    	{
    		printf("%c",b->data);
    		if(b->lchild!=NULL||b->rchild!=NULL)
    		{
    			printf("(");//有孩子结点时才输出 "(" 
    			DispBTree(b->lchild);//递归输出左子树 
    			if(b->rchild!=NULL) 
    			{
    				printf(",");//有右孩子结点时才输出 ","
    			}
    			DispBTree(b->rchild);//递归输出右子树 
    			printf(")");//有孩子结点时才输出 "）" 
    		}
    	}
    }
    //计算叶子结点数 
    int m=0;//全局变量：叶子结点数 
    void countLeaf(BTree b)
     {
     	
     	if(b!=NULL)
     	{
     		if(b->lchild==NULL&&b->rchild==NULL)
     		{
     			m++; 
    		} 
    		countLeaf(b->lchild);//递归输出右子树叶子结点 
    		countLeaf(b->rchild);//递归输出左子树叶子结点
    	}
     }
    //先序遍历递归算法 
    void PreOrder(BTree b)
    {
    	if(b!=NULL)
    	{
    		printf("%c ",b->data);//访问根结点 
    		PreOrder(b->lchild);//先序遍历左子树 
    		PreOrder(b->rchild);//先序遍历右子树
    	}
    }
    //中序遍历递归算法
    void InOrder(BTree b)
    {
    	if(b!=NULL)
    	{
    		InOrder(b->lchild);//中序遍历左子树
    		printf("%c ",b->data);//访问根结点 
    		InOrder(b->rchild);//中序遍历右子树
    	}
     } 
     //后序遍历递归算法
    void PostOrder(BTree b)
    {
    	if(b!=NULL)
    	{
    		PostOrder(b->lchild);//后序遍历左子树
    		PostOrder(b->rchild);//后序遍历右子树
    		printf("%c ",b->data);//访问根结点 
    	}
    }
      
    int main()
    {
    	BTree b=NULL; 
    	printf("创建二叉树："); 
    	CreateBTtree(&b);
    	printf("输出二叉树："); 
    	DispBTree(b);
    	printf("\n");
    	printf("该二叉树的叶子结点个数为：");
    	countLeaf(b);
    	printf("%d",m);
    	printf("\n\n----------递归遍历----------\n");
    	printf("先序遍历为："); 
    	PreOrder(b);
    	printf("\n"); 
    	printf("中序遍历为："); 
    	InOrder(b);
    	printf("\n");
    	printf("后序遍历为："); 
    	PostOrder(b);
    	printf("\n");
    	return 0;
     }

[c59e0ff1355d4823bca6fceff534a5b6.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/2858c22378a24204912f754ebe4ff92f.png
[af31c36a3f4f41388aefef41aaa091fb.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/51197af861da415c92cf0d04b2c224d4.png