数据结构二叉树的构造与遍历-创新互联

实验目的

本文主要是给c语言初学者或数据结构初学者展示二叉树的构造与遍历,可以作为简单的参考。除了代码外,本文有部分博主自己对代码的简单分析,可以通过下面的链接免费下载。

成都网站建设哪家好,找成都创新互联公司!专注于网页设计、重庆网站建设、微信开发、小程序制作、集团企业网站制作等服务项目。核心团队均拥有互联网行业多年经验,服务众多知名企业客户;涵盖的客户类型包括:成都塔吊租赁等众多领域,积累了大量丰富的经验,同时也获得了客户的一致赞扬!
代码
#include "stdafx.h"

// 各种引用
#include#include#include#include#define NULL 0 

int m_nNumOfLeaf=0;   // 叶子结点数量

typedef char ElemType;   //定义二叉树结点中保存的数据的数据类型

typedef struct BinaryNode  //定义二叉树结点的数据类型
{ElemType data;  //存放二叉树结点数据
    struct BinaryNode *lchild, *rchild;  //存放二叉树结点左右子树的指针(指向的数据类型是本身)
} BTNode; 


BTNode * m_root= NULL; // 二叉树指针(指向二叉树的根结点)

BTNode * CreatebBinaryTree()  
{BTNode *T; 
    ElemType x; 
    scanf("%c",&x);  // 获取结点数据
    if(x=='#') // 空结点
        T=NULL; 
    else  // 非空结点
    {T=(BTNode*)malloc(sizeof(BTNode));  // 申请空间存储结点
        T->data=x;  // 存储数据
        T->lchild=CreatebBinaryTree();    // 建立以本结点为根的左子树
        T->rchild=CreatebBinaryTree(); 	  // 建立以本结点为根的右子树
    } 

    return(T); // 返回根结点
} 

void PreOrderPrint(BTNode *t) 
{if(t!=NULL)   // 根结点不为空
    {printf("%c\t",t->data);    // 输出根结点
        PreOrderPrint(t->lchild);  // 前序遍历以本结点为根的左子树
        PreOrderPrint(t->rchild);  // 前序遍历以本结点为根的右子树
    } 
} 

void InOrderPrint(BTNode *t) 
{if(t!=NULL) // 根结点不为空
    {InOrderPrint(t->lchild);  // 中序遍历以本结点为根的左子树
        printf("%c\t",t->data);   // 输出根结点      
        InOrderPrint(t->rchild);  // 中序遍历以本结点为根的右子树
    } 
}

void PostOrderPrint(BTNode *t) 
{if(t!=NULL) // 根结点不为空
    { 
        PostOrderPrint(t->lchild); // 后序遍历以本结点为根的左子树
        PostOrderPrint(t->rchild); // 后序遍历以本结点为根的右子树
		printf("%c\t",t->data);    // 输出根结点
    } 
}

void CalNumOfLeaf(BTNode *t)
{if(t!=NULL)  // 根结点不为空
	{if((t->lchild!=NULL)||(t->rchild!=NULL))  // 判断该结点是否有左右子树		
		{	CalNumOfLeaf(t->lchild);     // 计算该结点左子树的叶子结点数     
		    CalNumOfLeaf(t->rchild);     // 计算该结点右子树的叶子结点数   
		}
        else m_nNumOfLeaf++;  // 是叶子结点,则叶子结点数加1
	}
}

int main(int argc, char* argv[]) // 主函数
{printf("              ***************************************\n");
	printf("                            二叉树操作\n");
	printf("              ***************************************\n");
	

	int flag = 1;
	while(flag)
	{printf("\n\n\t\t 1--建立\n");
		printf("\t\t 2--前序遍历\n");
		printf("\t\t 3--中序遍历\n");
		printf("\t\t 4--后序遍历\n");
		printf("\t\t 5--叶子的数量\n");
		printf("\t\t 0--退出程序\n");

		printf("\t\t 程序编写人<姓名:%s ; 学号:%s>\n","张三","123456789"); // 显示 姓名和学号

		scanf("%d",&flag);
		switch(flag)
		{	case 1:  // 建立二叉树
			{	getchar(); // 获取输入的回车
				printf("请输入二叉树各结点(前序顺序,#代表空结点),形式如(AB###,ABC#####):\n"); // 输出字符串
				m_root = CreatebBinaryTree();  // 构建二叉树(前序)
				printf("建立二叉树完毕:\n");  // 输出字符串
			}				
				break;				
			case 2:  // 前序遍历
			{		if(m_root == NULL)  // 出错判断
				{printf("\n还没有建立二叉树,无法进行此操作!\n"); // 输出字符串
				}
				else
				{printf("\n二叉树前序遍历的顺序为:\n"); // 输出字符串

					PreOrderPrint(m_root); // 前序遍历输出

					printf("\n二叉树前序遍历结束:\n"); // 输出字符串
				}

			}
				break;
			case 3:  // 中序遍历
			{	
				if(m_root == NULL)  // 出错判断
				{printf("\n还没有建立二叉树,无法进行此操作!\n"); // 输出字符串
				}
				else
				{printf("\n二叉树中序遍历的顺序为:\n"); // 输出字符串

					InOrderPrint(m_root); // 中序遍历输出

					printf("\n二叉树中序遍历结束:\n"); // 输出字符串
				}
			}
				break;

			case 4:  // 后序遍历
			{	
				if(m_root == NULL)  // 出错判断
				{printf("\n还没有建立二叉树,无法进行此操作!\n"); // 输出字符串
				}
				else
				{printf("\n二叉树后序遍历的顺序为:\n"); // 输出字符串

					PostOrderPrint(m_root); // 后序遍历输出

					printf("\n二叉树后序遍历结束:\n"); // 输出字符串
				}

			}
				break;
			case 5:  // 计算叶子结点的数目
			{		if(m_root == NULL)  // 出错判断
				{printf("\n还没有建立二叉树,无法进行此操作!\n"); // 输出字符串
				}
				else
				{m_nNumOfLeaf=0;   // 叶子结点数量初始化
					CalNumOfLeaf(m_root);   // 计算叶子结点数量

					printf("\n当前二叉树中叶子数量为:%d\n",m_nNumOfLeaf); // 输出字符串
				}
			}
				break;
			case 0:  // 退出程序
				break;

			default: // 输入错误
				printf("请输入正确的数字!!!\n");
				break;
		}

	}
	return 0;

}
运行结果

运行结果

免费下载代码解析

下载

你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧

当前名称:数据结构二叉树的构造与遍历-创新互联
地址分享:https://www.cdcxhl.com/article10/dgeido.html

成都网站建设公司_创新互联,为您提供品牌网站设计全网营销推广静态网站搜索引擎优化小程序开发响应式网站

广告

声明:本网站发布的内容(图片、视频和文字)以用户投稿、用户转载内容为主,如果涉及侵权请尽快告知,我们将会在第一时间删除。文章观点不代表本网站立场,如需处理请联系客服。电话:028-86922220;邮箱:631063699@qq.com。内容未经允许不得转载,或转载时需注明来源: 创新互联

手机网站建设