详细了解C语言二叉树的建立与遍历
作者:LuckyLazyPig 发布时间:2021-08-17 10:24:01
标签:C语言,二叉树,遍历
这里给一个样例树:
代码:
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
/* 二叉树的二叉链表结点结构定义 */
typedef struct BiTNode
{
char data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
BiTree T=NULL;
/* 先序遍历建立一个二叉树 */
void Create (BiTree *T) // 二级指针改变地址的地址
{
char ch;
scanf("%c",&ch);
if(ch=='#')
*T=NULL;
else
{
*T=(BiTree)malloc(sizeof(BiTNode));
if(!*T)
return ;
else
{
(*T)->data=ch;
Create(&(*T)->lchild);
Create(&(*T)->rchild);
}
}
}
/* 二叉树的前序递归遍历算法 */
void PreOrderTraverse(BiTree T)
{
if(T==NULL)
return ;
printf("%c ",T->data);
PreOrderTraverse(T->lchild);
PreOrderTraverse(T->rchild);
}
/* 二叉树的中序递归遍历算法 */
void InOrderTraverse(BiTree T)
{
if(T==NULL)
return ;
InOrderTraverse(T->lchild);
printf("%c ",T->data);
InOrderTraverse(T->rchild);
}
/* 二叉树的后序递归遍历算法 */
void PostOrderTraverse(BiTree T)
{
if(T==NULL)
return ;
PostOrderTraverse(T->lchild);
PostOrderTraverse(T->rchild);
printf("%c ",T->data);
}
int main()
{
printf("请按先序遍历的结果输入树,例如:ABDH#K###E##CFI###G#J##\n");
Create(&T);
printf("先序遍历的结果为:\n");
PreOrderTraverse(T);
printf("\n");
printf("中序遍历的结果为:\n");
InOrderTraverse(T);
printf("\n");
printf("后序遍历的结果为:\n");
PostOrderTraverse(T);
printf("\n");
return 0;
}
输出结果如下
PS:下面是一个用C++里面的取引用代替了二级指针
#include<bits/stdc++.h>
using namespace std;
/* 二叉树的二叉链表结点结构定义 */
typedef struct BiTNode
{
char data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
BiTree T=NULL;
/* 先序遍历建立一个二叉树 */
void Create (BiTree &T) // C++取引用
{
char ch;
scanf("%c",&ch);
if(ch=='#')
T=NULL;
else
{
T=(BiTree)malloc(sizeof(BiTNode));
if(!T)
return ;
else
{
T->data=ch;
Create(T->lchild);
Create(T->rchild);
}
}
}
/* 二叉树的前序递归遍历算法 */
void PreOrderTraverse(BiTree T)
{
if(T==NULL)
return ;
printf("%c ",T->data);
PreOrderTraverse(T->lchild);
PreOrderTraverse(T->rchild);
}
/* 二叉树的中序递归遍历算法 */
void InOrderTraverse(BiTree T)
{
if(T==NULL)
return ;
InOrderTraverse(T->lchild);
printf("%c ",T->data);
InOrderTraverse(T->rchild);
}
/* 二叉树的后序递归遍历算法 */
void PostOrderTraverse(BiTree T)
{
if(T==NULL)
return ;
PostOrderTraverse(T->lchild);
PostOrderTraverse(T->rchild);
printf("%c ",T->data);
}
int main()
{
printf("请按先序遍历的结果输入树,例如:ABDH#K###E##CFI###G#J##\n");
Create(T);
printf("先序遍历的结果为:\n");
PreOrderTraverse(T);
printf("\n");
printf("中序遍历的结果为:\n");
InOrderTraverse(T);
printf("\n");
printf("后序遍历的结果为:\n");
PostOrderTraverse(T);
printf("\n");
return 0;
}
PS:遍历的PLus版,想要的自取。
#include <iostream>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
using namespace std;
const int cmax=1e2+5;
typedef struct BiTNode
{
char data;
struct BiTNode *lchild ,*rchild;
}BiTNode,*BiTree;
void CreateBiTree (BiTree &T)
{
char ch;
scanf("%c",&ch);
if(ch=='#')
T=NULL;
else
{
T=(BiTNode *)malloc(sizeof(BiTNode));
T->data=ch;
CreateBiTree(T->lchild);
CreateBiTree(T->rchild);
}
return ;
}
void PreOrder(BiTree T)
{
if(T)
{
printf("%c",T->data);
PreOrder(T->lchild);
PreOrder(T->rchild);
}
}
void InOrder(BiTree T)
{
if(T)
{
InOrder(T->lchild);
printf("%c",T->data);
InOrder(T->rchild);
}
}
void PostOrder(BiTree T)
{
if(T)
{
PostOrder(T->lchild);
PostOrder(T->rchild);
printf("%c",T->data);
}
}
// 非递归中序遍历
void InOrderTraverse(BiTree T)
{
stack<BiTree> S;
BiTree p;
S.push(T);
while(!S.empty())
{
p=new BiTNode;
while((p=S.top())&&p)
S.push(p->lchild);
S.pop();
if(!S.empty())
{
p=S.top();
S.pop();
cout<<p->data<<" ";
S.push(p->rchild);
}
}
}
// 先序非递归遍历
void PreOrder_Nonrecursive(BiTree T)
{
stack<BiTree> S;
BiTree p;
S.push(T);
while(!S.empty())
{
while((p=S.top())&&p)
{
cout<<p->data<<" ";
S.push(p->lchild);
}
S.pop();
if(!S.empty())
{
p=S.top();
S.pop();
S.push(p->rchild);
}
}
}
int visit(BiTree T)
{
if(T)
{
printf("%c ",T->data);
return 1;
}
else
return 0;
}
// 非递归层次遍历
void LeverTraverse(BiTree T)
{
queue <BiTree> Q;
BiTree p;
p=T;
if(visit(p)==1)
Q.push(p);
while(!Q.empty())
{
p=Q.front();
Q.pop();
if(visit(p->lchild)==1)
Q.push(p->lchild);
if(visit(p->rchild)==1)
Q.push(p->rchild);
}
}
//主函数
int main()
{
BiTree T;
char j;
int flag=1;
printf("本程序实现二叉树的操作。\n");
printf("叶子结点以#表示。\n");
printf("可以进行建立二叉树,递归先序、中序、后序遍历,非递归先序、中序遍历及非递归层序遍历等操作。\n");
printf("请建立二叉树。\n");
printf("建树将以三个空格后回车结束。\n");
printf("例如:1 2 3 4 5 6 (回车)\n\n");
CreateBiTree(T); //初始化队列
getchar();
printf("\n");
printf("请选择: \n");
printf("1.递归先序遍历\n");
printf("2.递归中序遍历\n");
printf("3.递归后序遍历\n");
printf("4.非递归中序遍历\n");
printf("5.非递归先序遍历\n");
printf("6.非递归层序遍历\n");
printf("0.退出程序\n");
while(flag)
{
scanf(" %c",&j);
switch(j)
{
case '1':if(T)
{
printf("递归先序遍历二叉树:");
PreOrder(T);
printf("\n");
}
else printf("二叉树为空!\n");
break;
case '2':if(T)
{
printf("递归中序遍历二叉树:");
InOrder(T);
printf("\n");
}
else printf("二叉树为空!\n");
break;
case '3':if(T)
{
printf("递归后序遍历二叉树:");
PostOrder(T);
printf("\n");
}
else printf("二叉树为空!\n");
break;
case '4':if(T)
{
printf("非递归中序遍历二叉树:");
InOrderTraverse(T);
printf("\n");
}
else printf("二叉树为空!\n");
break;
case '5':if(T)
{
printf("非递归先序遍历二叉树:");
PreOrder_Nonrecursive(T);
printf("\n");
}
else printf("二叉树为空!\n");
break;
case '6':if(T)
{
printf("非递归层序遍历二叉树:");
LeverTraverse(T);
printf("\n");
}
else printf("二叉树为空!\n");
break;
default:flag=0;printf("程序运行结束,按任意键退出!\n");
}
}
}
来源:https://blog.csdn.net/weixin_45882303/article/details/107941789
0
投稿
猜你喜欢
- 1、分布式锁简介分布式锁是控制分布式系统不同进程共同访问共享资源的一种锁的实现。如果不同的系统或同一个系统的不同主机之间共享了某个临界资源,
- Spring Security中的内置过滤器顺序是怎么维护的?我想很多开发者都对这个问题感兴趣。本篇我和大家一起探讨下这个问题。HttpSe
- springboot加载yml文件获不到值今天使用spring boot读取yml文件,这种多层嵌套的竟然无法读取到(value注解spri
- 使用@Async异步调用方法Async简介异步方法调用使用场景:处理日志、发送邮件、短信......spring中提供了@Async来实现异
- 1. 引入静态资源:th:href或th:scr+@{/从static目录开始}<html lang="en" x
- Java GC 机制与内存分配策略详解收集算法是内存回收的方 * ,垃圾收集器是内存回收的具体实现自动内存管理解决的是:给对象分配内存 以及
- java String的深入理解一、Java内存模型 按照官方的说法:Java 虚拟机具有一个堆,堆是运行时数据区域,所有类实例和
- 这篇文章写的非常好,深入浅出,关键还是一位大三学生自己剖析的心得。这是我喜欢此文的原因。下面请看正文:作为一个大三的预备程序员,我学习and
- 本文实例讲述了winform实现创建最前端窗体的方法。分享给大家供大家参考。具体实现方法如下:一、需求:1).需要这个窗体始终处于前端而且可
- 欢迎访问我的GitHub这里分类和汇总了欣宸的全部原创(含配套源码):https://github.com/zq2599/blog_demo
- C#反射技术主要基于System.Type类和System.Reflection.Assemble类,通过Type类可以访问关于任何数据类型
- ForkJoin简介Fork/Join框架是Java 7提供的一种用于并行执行任务的框架,它将大任务分解为若干个小任务,并行执行这些小任务,
- 本文实例讲述了Android编程实现仿优酷旋转菜单效果。分享给大家供大家参考,具体如下:首先,看下效果:不好意思,不会制作动态图片,只好上传
- 基本数据类型变量就是用来储存值而保留的内存位置。这就意味着当你创建一个变量时就会在内存中占用一定的空间。基于变量的数据类型,操作系统会进行内
- 本文纯干货,贴上PDF文档操作类C#代码,需要添加iTextSharp.dll引用才可以正常通过编译。废话不多说了,直接给大家贴代码了。代码
- 一、讲个事故接口安全老生常谈了过年之前做了过一款飞机大战的H5小游戏,里面无限模式-需要保存用户的积分,因为使用的Body传参,参数是可见的
- 通常来说,多线程的并发及条件断点的debug是很难完成的,或许本篇文章会给你提供一个友好的调试方法。让你在多线程开发过程中的调试更加的有的放
- 配置文件context-path的坑context-path: /manage 这个配置加入后会导致访问spring的页面都需要加这个/ma
- 在我们编程过程中如果需要执行一些简单的定时任务,无须做复杂的控制,我们可以考虑使用JDK中的Timer定时任务来实现。下面LZ就其原理、实例
- 导入maven项目各个注解均报错所遇问题导入maven项目各个注解均报错了思考1:这个项目使用了springboot;spring是个”大容