#include "stdio.h"
#include "stdlib.h"
#include "string.h"
#include "malloc.h"
typedef char DataType;
/*读入二叉树的中序和后序遍历,输出此二叉树的前序遍历和叶子节点个数
测试数据
DGBAECHF
GDBEHFCA
前序遍历:ABDGCF
*/
/*定义二叉树结构体*/
typedef struct tree
{
DataType d;
struct tree *lchild,*rchild;
}Tree,*PTree;
/*in表示中序字符串 post 表示后序字符串 ins ine分别表示中序字符串的起始长度 posts poste 分别表示后序字符串的起始长度*/
void makeTree(PTree *p,char *in,int ins,int ine,char *post,int posts,int poste)
{
int preIndex=0;//定义中序字符串中 中间数的位置
if(poste<posts||ine<ins) *p=NULL;
else
{
*p=(PTree)malloc(sizeof(Tree));
(*p)->d=post[poste];
//(*p)->lchild=NULL;
//(*p)->rchild=NULL;
for(preIndex=ins;preIndex<=ine;preIndex++)
{
if(post[poste]==in[preIndex])
{
makeTree(&(*p)->lchild,in,ins,preIndex-1,post,posts,preIndex-ins-1);
makeTree(&(*p)->rchild,in,preIndex+1,ine,post,preIndex-ins,poste-1);
break;
}
}
/*该函数每次从0开始
while(9)
{
if(in[preIndex]==post[poste])break;
preIndex++;
}*/
}
}
/*前序遍历二叉树*/
void preOrder(PTree p)
{
if(p)
{
printf("%c",p->d);
preOrder(p->lchild);
preOrder(p->rchild);
}
}
/*求叶子节点数*/
int leafNum(PTree p)
{
if(p==NULL)
return 0;
else
if(p->lchild==NULL&&p->rchild==NULL)
return 1;
else
return leafNum(p->lchild)+leafNum(p->rchild);
}
void main()
{
char in[100],post[100];
int il,pl;
PTree p;
printf("输入中序\n");
gets(in);
printf("输入后序\n");
gets(post);
il=strlen(in);
pl=strlen(in);
makeTree(&p,in,0,strlen(in)-1,post,0,strlen(post)-1);
printf("前序遍历:");
preOrder(p);
printf("\n叶子节点数为%d\n",leafNum(p));
}
分享到:
相关推荐
2. 请分别按照前序、中序、后序输出这棵树。 选做部分 背景 在影视剧中,我们经常会看到二战期间情报人员使用电报哒哒哒地发送信息,发送电报所使用的编码叫做摩尔斯电码(或者叫做摩斯密码)。甚至在现代,SOS仍然...
编程实现二叉树的建立,先序、中序、后序、层序遍历(递归和非递归方法),二叉树的高度、繁茂度,交换左右子树,统计叶子节点的数目,判断是否为完全二叉树,按树的形态在屏幕上打印输出; [基本要求] (1) 从...
任务 :编程实现二叉树的建立,先序(递归和非递归方法)、中序、后序、层次遍历,求二叉树的高度; 要求:从文件中读入建树信息,树的节点数目不小于20个,树的高度不小于4; 3、Hash表应用 问题描述:设计散列表...
中序遍历二叉树也采用递归函数的方式,先访问左子树2i,然后访问根结点i,最后访问右子树2i+1.先向左走到底再层层返回,直至所有的结点都被访问完毕。 1.2.4 平均查找长度 计算二叉排序树的平均查找长度时,采用类似...
2、通过二叉树遍历操作了解递归的本质和方法; 内容及步骤: 1、 试建立一个二叉搜索树,并实现以下成员函数: a. 默认构造函数和带数据域、左子树指针、右子树指针的构造函数; b. 按照二叉搜索树...
在计算机科学中,二叉树...这次要利用二叉树去实现读入一个文件的单词,然后建立一棵二叉搜索树,然后输出二叉搜索树的高度、叶子树等信息,以及实现其中序遍历。利用二叉搜索树,能将大量单词很快地排好序,性能很高。
易语言节点基本操作源码,节点基本操作,读入XML数据
文本读入能够分离出单词,过滤数字和标点符号,把字母大小写转为小写,按英文字母的顺序高招二叉树,遍历但不递归;用单链表存储结构,对两个集合的内容进行并,交,差集运算
输出该二叉树的中序遍历关键字访问次序。 3. 从空树起连续插入以下20个关键字构建m=4的B-树。 50, 15, 09, 18, 03, 85, 33, 72, 48, 22, 91, 88, 11, 99, 06, 56, 68, 77, 43, 36。 4. 16个关键字组成的5阶B-树如下...
第一章 1.1数据结构课程设计要求。...其中二叉树节点由1个表示关键 字的key表示,还有指向该左孩子和右孩子的指针,通过key<p- >key的if语句来判断,其中p表示二叉排序树。 2.2.1系统功能的设计。 本程序设置了5个
任务 :编程实现二叉树的建立,层次遍历,(递归和非递归方法)先序、中序、后序,二叉树的高度、宽度。二叉排序树的建立、插入、删除; 基本要求:从文件中读入建树信息,树的节点数目不小于20个,树的高度不小于5...
右侧上方为算法文本,在算法中有4个形式参量,其中值参 n 为圆盘个数,x、y、和 z 分别表示3个塔座;右侧下方为递归工作栈,栈中每个记录包含调用语句行号 adr 及值参 n 和 x、y、z;左侧上方显示汉诺塔图形及移动...
图示窗口显示生成的赫夫曼树的逻辑结构和每个叶子结点的编码。 21. 图的深度优先搜索 图示窗口的上半部分显示图的逻辑结构,初始状态用青色圆圈表示顶点,结点间的黑色连线表示边或弧(连线上画有箭头)。演示...