多叉树的设计、建立、层次优先遍历和深度优先遍历

《多叉树的设计、建立、层次优先遍历和深度优先遍历》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、多叉树的设计、建立、层次优先遍历和深度优先遍历早起曾实现过一个简单的多叉树《实现一个多叉树》。其实现原理是多叉树中的节点有两个域，分别表示节点名以及一个数组，该数组存储其子节点的地址。实现了一个多叉树建立函数，用于输入格式为AB。A表示节点的名字，B表示节点的子节点个数。建立函数根据用户的输入，首先建立一个新的节点，然后根据B的值进行深度递归调用。用户输入节点的顺序就是按照深度递归的顺序。另外，我们实现了一个层次优先遍历函数。该函数用一个队列实现该多叉树的层次优先遍历。首先将根节点入队列，然后检测队列是否为空，如果不为空，将队列出队列，访问出队列的节点，然后将该节

2、点的子节点指针入队列，依次循环下去，直至队列为空，终止循环，从而完成整个多叉树的层次优先遍历。本文我们将还是介绍一个多叉树，其内容和之前的实现差不多。首先，用户的多叉树数据存储在一个文件中，格式如下：每行的第一个元素指定一个节点，其中第一行指定了该多叉树的根节点。第二个元素表示该节点有几个子节点，紧接着后面跟了几个子节点。根据以上数据文件，其对应的多叉树应该是如下：我们想得到结果是将书中的节点按深度进行输出，比如先输出深度最深的节点：xej，然后输出深度为2的节点：dfi，之后再输出深度为1的节点：gcCzbBbB，最后输出根节点：aA。按照深度将节点输出，很显然

3、是用层次优先遍历的方法解决。层次优先遍历的实现原理就是从根节点开始，利用队列实现。另外，我们想得到从根节点开始到叶子节点直接所有节点名字加起来最长的一个路径，比如上面的树中存在以下几条路径：aAgdxaAgdeaAgdjaAcCaAzfaAziaAbBbB显然，在这些路径中，aAbBbB是所有路径上节点名字加起来最长的一个路径。求解从根节点到叶子节点上的所有路径，利用深度优先遍历更为合适。下面我们讨论一下多叉树节点应该如何建立。首先多叉树的节点应该如何定义，节点除了有自身的名字外，还要记录其子节点有多少个，每个子节点在哪里，所以我们需要增加一个记录子节点个数的域，

4、还要增加一个数组，用来记录子节点的指针。另外，还要记录多叉树中每个节点的深度值。在读取数据文件的过程中，我们顺序扫描整个文件，根据第一个名字，建立新的节点，或者从多叉树中找到已经有的节点地址，将后续的子节点生成，并归属于该父节点，直至扫描完整个数据文件。读取完整个文件后，也就建立了多叉树，之后，我们利用队列对多叉树进行广度优先遍历，记录各个节点的深度值。并将其按照深度进行输出。获取从根节点到子节点路径上所有节点名字最长的路径，我们利用深度优先遍历，递归调用深度优先遍历函数，找到最长的那个路径。初次之外，还需定义队列结构体，这里使用的队列是循环队列，实现相关的队列操

5、作函数。还有定义栈的结构体，实现栈的相关操作函数。另外对几个内存分配函数、字符串拷贝函数、文件打开函数进行了封装。需要注意的一点就是当操作完成后，需要对已经建立的任何东西都要销毁掉，比如中途建立的队列、栈、多叉树等，其中还包含各个结构体中的指针域。另外，函数测试是用户在命令行模式下输入程序名字后面紧跟数据文件的形式。该程序的主要部分有如下几点：1.多叉树节点的定义和生成一个新节点2.数据文件的读取以及多叉树的建立3.根据节点名字在多叉树中查找节点的位置4.多叉树的层次优先遍历5.多叉树的深度优先遍历6.队列的定义以及相关操作函数实现7.栈的定义以及相关操作函数实现

6、8.消毁相关已经建立好的队列、栈、多叉树等9.测试模块下面我们给出相关的程序实现，具体细节可以查看代码和注释说明。//多叉树的建立、层次遍历、深度遍历#include#include#include#defineM100+1//宏定义，定义最大名字字母长度//定义多叉树的节点结构体typedefstructnode_t{char*name;//节点名intn_children;//子节点个数intlevel;//记录该节点在多叉树中的层数structnode_t**children;//指向其自身的子节点，

7、children一个数组，该数组中的元素时node_t*指针}NODE;//对结构体重命名//实现一个栈，用于后续操作typedefstructstack_t{NODE**array;//array是个数组，其元素为NODE*型指针intindex;//指示栈顶元素intsize;//栈的大小}STACK;//重命名//实现一个队列，用于后续操作typedefstructqueue_t{NODE**array;//array是个数组，其内部元素为NODE*型指针inthead;//队列的头inttail;//队列的尾intnum;//队列中元素的个数intsize

8、;//队列