typedef struct node_t{char*name; // 节点名int n_children; // 子节点个数int level;// 记录该节点在多叉树中的层数structnode_t** children; // 指向其自身的子节点，children一个数组，该数组中的元素时node_t*指针} NODE; // 对结构体重命名

typedef struct stack_t{NODE**array; // array是个数组，其元素为NODE*型指针intindex; // 指示栈顶元素intsize; // 栈的大小} STACK; // 重命名

typedef struct queue_t{NODE**array; // array是个数组，其内部元素为NODE*型指针inthead; // 队列的头inttail; // 队列的尾intnum;// 队列中元素的个数intsize; // 队列的大小} QUEUE;

函数名称

功能说明

void* util_malloc(int size)

内存分配函数。

char* util_strdup(char* src)

字符串赋值函数。

FILE* util_fopen(char* name, char* access)

打开文件函数。

STACK* STACKinit(int size)

栈的初始化。

int STACKempty(STACK* sp)

判断栈是否为空。

int STACKpush(STACK* sp, NODE* data)

压栈操作。

int STACKpop(STACK* sp, NODE** data_ptr)

弹栈操作。

void STACKdestroy(STACK* sp)

栈的销毁。

QUEUE* QUEUEinit(int size)

队列初始化。

int QUEUEenqueue(QUEUE* qp, NODE* data)

入队操作。

int QUEUEdequeue(QUEUE* qp, NODE** data_ptr)

出队操作

int QUEUEempty(QUEUE* qp)

判断队列是否为空。

void QUEUEdestroy(QUEUE* qp)

队列的销毁。

NODE* create_node()

生成多叉树节点。

NODE* search_node_r(char name[M], NODE* head)

按照节点名字查找。

void read_file(NODE** head, char* filename)

从文件中读取多叉树，并建立多叉树。

void f1(NODE* head)

层次遍历。

void free_tree_r(NODE* head)

销毁树。

void f2(NODE* head, char* str, char** strBest, int level)

深度遍历。

void Welcome()

显示界面

void Create()

输入节点数据。

int main(int argc, char* argv[])

主界面。

while(1){ system("cls"); // 清屏 Welcome();//重新显示界面 int i, cho; scanf("%d",&i); if(1 == i)Create();//if(2 == i)Delete();//if(3 == i)Search();//if(4 == i)Alter(); if(5 == i)Traversal1(); if(6 == i)Traversal2(); if(7 == i){printf("\n欢迎您再次使用本系统\n\n");break;}printf("\n返回请输入0\n"); begin: //goto 标志位 scanf("%d",&cho); if(0 == cho){ continue; } else{ printf("您的输入有误，请重新输入\n"); goto begin;//goto 到指定标志位 begin }}

NODE*search_node_r(char name[M], NODE* head){NODE* temp = NULL;int i = 0; if (head != NULL){if (strcmp(name, head->name) == 0)// 如果名字匹配{temp = head;}else // 如果不匹配，则查找其子节点{for (i = 0; i n_children && temp == NULL/*如果temp不为空，则结束查找*/; ++i){temp = search_node_r(name,head->children[i]); // 递归查找子节点}}} return temp; // 将查找到的节点指针返回，也有可能没有找到，此时temp为NULL}

voidf1(NODE* head){NODE* p = NULL;QUEUE* q = NULL; // 定义一个队列STACK* s = NULL; // 定义一个栈int i = 0; q = QUEUEinit(100); // 将队列初始化大小为100s = STACKinit(100); // 将栈初始化大小为100head->level = 0; // 根节点的深度为0// 将根节点入队列QUEUEenqueue(q, head); // 对多叉树中的节点的深度值level进行赋值// 采用层次优先遍历方法，借助于队列while (QUEUEempty(q) == 0) // 如果队列q不为空{QUEUEdequeue(q, &p); // 出队列for (i = 0; i n_children;++i){p->children[i]->level =p->level + 1; // 对子节点深度进行赋值：父节点深度加1QUEUEenqueue(q,p->children[i]);// 将子节点入队列}STACKpush(s, p); // 将p入栈} while (STACKempty(s) == 0) // 不为空{STACKpop(s, &p); // 弹栈fprintf(stdout, "第%d层 目录名为：%s\n",p->level, p->name);} QUEUEdestroy(q); // 消毁队列STACKdestroy(s); // 消毁栈}