typedef struct node_t
{
    char*  name;               // 節(jié)點(diǎn)名
    int   n_children;         // 子節(jié)點(diǎn)個(gè)數(shù)
    int   level;              // 記錄該節(jié)點(diǎn)在多叉樹中的層數(shù)
    struct  node_t** children; // 指向其自身的子節(jié)點(diǎn)，children一個(gè)數(shù)組，該數(shù)組中的元素時(shí)node_t*指針
} NODE; // 對(duì)結(jié)構(gòu)體重命名

typedef struct stack_t
{
    NODE**  array; // array是個(gè)數(shù)組，其元素為NODE*型指針
    int    index; // 指示棧頂元素
    int    size;   // 棧的大小
} STACK; // 重命名

typedef struct queue_t
{
    NODE**  array; // array是個(gè)數(shù)組，其內(nèi)部元素為NODE*型指針
    int    head;   // 隊(duì)列的頭
    int    tail;     // 隊(duì)列的尾
    int    num;    // 隊(duì)列中元素的個(gè)數(shù)
    int    size;   // 隊(duì)列的大小
} QUEUE;

函數(shù)名稱

功能說明

void* util_malloc(int size)

內(nèi)存分配函數(shù)。

char* util_strdup(char* src)

字符串賦值函數(shù)。

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

打開文件函數(shù)。

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)

隊(duì)列初始化。

int QUEUEenqueue(QUEUE* qp, NODE* data)

入隊(duì)操作。

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

出隊(duì)操作

int QUEUEempty(QUEUE* qp)

判斷隊(duì)列是否為空。

void QUEUEdestroy(QUEUE* qp)

隊(duì)列的銷毀。

NODE* create_node()

生成多叉樹節(jié)點(diǎn)。

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

按照節(jié)點(diǎn)名字查找。

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()

輸入節(jié)點(diǎn)數(shù)據(jù)。

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歡迎您再次使用本系統(tǒng)\n\n");
                                                  break;
                                          } 
                 printf("\n返回請(qǐng)輸入0\n");
                 begin:                                                                 //  goto 標(biāo)志位
                         scanf("%d",  &cho);
                 if(0 == cho){
                         continue;
                 }
                 else{
                         printf("您的輸入有誤，請(qǐng)重新輸入\n");
                         goto begin;                                                //  goto 到指定標(biāo)志位 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 // 如果不匹配，則查找其子節(jié)點(diǎn)
        {
            for (i = 0; i <  head->n_children && temp == NULL/*如果temp不為空，則結(jié)束查找*/; ++i)
            {
                temp = search_node_r(name,  head->children[i]); // 遞歸查找子節(jié)點(diǎn)
            }
        }
    }
 
    return temp; // 將查找到的節(jié)點(diǎn)指針返回，也有可能沒有找到，此時(shí)temp為NULL
}

void  f1(NODE* head)
{
    NODE* p = NULL;
    QUEUE* q = NULL; // 定義一個(gè)隊(duì)列
    STACK* s = NULL; // 定義一個(gè)棧
    int i = 0;
 
    q = QUEUEinit(100); // 將隊(duì)列初始化大小為100
    s = STACKinit(100); // 將棧初始化大小為100
    
    head->level = 0; // 根節(jié)點(diǎn)的深度為0
    
    // 將根節(jié)點(diǎn)入隊(duì)列
    QUEUEenqueue(q, head);
 
    // 對(duì)多叉樹中的節(jié)點(diǎn)的深度值level進(jìn)行賦值
    // 采用層次優(yōu)先遍歷方法，借助于隊(duì)列
    while (QUEUEempty(q) == 0) // 如果隊(duì)列q不為空
    {
        QUEUEdequeue(q, &p); // 出隊(duì)列
        for (i = 0; i < p->n_children;  ++i)
        {
            p->children[i]->level =  p->level + 1; // 對(duì)子節(jié)點(diǎn)深度進(jìn)行賦值：父節(jié)點(diǎn)深度加1
            QUEUEenqueue(q,  p->children[i]);      // 將子節(jié)點(diǎn)入隊(duì)列
        }
        STACKpush(s, p); // 將p入棧
    }
 
    while (STACKempty(s) == 0) // 不為空
    {
        STACKpop(s, &p); // 彈棧
        fprintf(stdout, "第%d層 目錄名為：%s\n",p->level, p->name);
    }
 
    QUEUEdestroy(q); // 消毀隊(duì)列
    STACKdestroy(s); // 消毀棧
}