没有合适的资源?快使用搜索试试~ 我知道了~
多叉树的设计、建立、层次优先遍历和深度优先遍历
需积分: 50 40 下载量 184 浏览量
2015-09-22
23:15:55
上传
评论
收藏 356KB PDF 举报
温馨提示
现了一个多叉树建立函数,建立函数根据用户的输入,首先建立一个新的节点,然后根据B的值进行深度递归调用。用户输入节点的顺序就是按照深度递归的顺序。另外,我们实现了一个层次优先遍历函数。该函数用一个队列实现该多叉树的层次优先遍历。首先将根节点入队列,然后检测队列是否为空,如果不为空,将队列出队列,访问出队列的节点,然后将该节点的子节点指针入队列,依次循环下去,直至队列为空,终止循环,从而完成整个多叉树的层次优先遍历。
资源推荐
资源详情
资源评论
多叉树的设计、建立、层次优先遍历和深度优先遍历
早起曾实现过一个简单的多叉树《实现一个多叉树》。其实现原理是多叉树中的节点有两个域,分
别表示节点名以及一个数组,该数组存储其子节点的地址。实现了一个多叉树建立函数,用于输入格式为A
B。A表示节点的名字,B表示节点的子节点个数。建立函数根据用户的输入,首先建立一个新的节点,然
后根据B的值进行深度递归调用。用户输入节点的顺序就是按照深度递归的顺序。另外,我们实现了一个层
次优先遍历函数。该函数用一个队列实现该多叉树的层次优先遍历。首先将根节点入队列,然后检测队列
是否为空,如果不为空,将队列出队列,访问出队列的节点,然后将该节点的子节点指针入队列,依次循
环下去,直至队列为空,终止循环,从而完成整个多叉树的层次优先遍历。
本文我们将还是介绍一个多叉树,其内容和之前的实现差不多。
首先,用户的多叉树数据存储在一个文件中,格式如下:
每行的第一个元素指定一个节点,其中第一行指定了该多叉树的根节点。第二个元素表示该节点有
几个子节点,紧接着后面跟了几个子节点。
根据以上数据文件,其对应的多叉树应该是如下:
我们想得到结果是将书中的节点按深度进行输出,比如先输出深度最深的节点:x e j,然后输出深
度为2的节点:d f i,之后再输出深度为1的节点:g cC z bBbB,最后输出根节点:aA。
按照深度将节点输出,很显然是用层次优先遍历的方法解决。层次优先遍历的实现原理就是从根节
点开始,利用队列实现。
另外,我们想得到从根节点开始到叶子节点直接所有节点名字加起来最长的一个路径,比如上面的
树中存在以下几条路径:
aA g d x
aA g d e
aA g d j
aA cC
aA z f
aA z i
aA bBbB
显然,在这些路径中,aA bBbB是所有路径上节点名字加起来最长的一个路径。求解从根节点到叶子
节点上的所有路径,利用深度优先遍历更为合适。
下面我们讨论一下多叉树节点应该如何建立。首先多叉树的节点应该如何定义,节点除了有自身的
名字外,还要记录其子节点有多少个,每个子节点在哪里,所以我们需要增加一个记录子节点个数的域,
还要增加一个数组,用来记录子节点的指针。另外,还要记录多叉树中每个节点的深度值。
在读取数据文件的过程中,我们顺序扫描整个文件,根据第一个名字,建立新的节点,或者从多叉
树中找到已经有的节点地址,将后续的子节点生成,并归属于该父节点,直至扫描完整个数据文件。
读取完整个文件后,也就建立了多叉树,之后,我们利用队列对多叉树进行广度优先遍历,记录各
个节点的深度值。并将其按照深度进行输出。
获取从根节点到子节点路径上所有节点名字最长的路径,我们利用深度优先遍历,递归调用深度优
先遍历函数,找到最长的那个路径。
初次之外,还需定义队列结构体,这里使用的队列是循环队列,实现相关的队列操作函数。还有定
义栈的结构体,实现栈的相关操作函数。另外对几个内存分配函数、字符串拷贝函数、文件打开函数进行
了封装。需要注意的一点就是当操作完成后,需要对已经建立的任何东西都要销毁掉,比如中途建立的队
列、栈、多叉树等,其中还包含各个结构体中的指针域。
另外,函数测试是用户在命令行模式下输入程序名字后面紧跟数据文件的形式。
该程序的主要部分有如下几点:
1.多叉树节点的定义和生成一个新节点
2.数据文件的读取以及多叉树的建立
3.根据节点名字在多叉树中查找节点的位置
4.多叉树的层次优先遍历
5.多叉树的深度优先遍历
6.队列的定义以及相关操作函数实现
7.栈的定义以及相关操作函数实现
8.消毁相关已经建立好的队列、栈、多叉树等
9.测试模块
下面我们给出相关的程序实现,具体细节可以查看代码和注释说明。
// 多叉树的建立、层次遍历、深度遍历
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
剩余9页未读,继续阅读
资源评论
racoonlove06
- 粉丝: 1
- 资源: 41
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
最新资源
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功