代碼：

BTree.h
BTree.c
二叉樹（多路平衡搜索樹）

LinkQueue.h

#ifndef _LINKQUEUE_H_
#define _LINKQUEUE_H_typedef void LinkQueue;//定義隊列類型LinkQueue* LinkQueue_Create();//聲明創建隊列函數void LinkQueue_Destroy(LinkQueue* queue);//聲明銷毀隊列函數void LinkQueue_Clear(LinkQueue* queue);//聲明清空隊列函數int LinkQueue_Append(LinkQueue* queue, void* item);//聲明添加進隊函數void* LinkQueue_Retrieve(LinkQueue* queue);//聲明出隊函數void* LinkQueue_Header(LinkQueue* queue);//聲明獲取頭元素函數int LinkQueue_Length(LinkQueue* queue);//聲明獲取長度函數#endif

LinkQueue.c

#include <malloc.h>
#include <stdio.h>
#include "LinkQueue.h"typedef struct _tag_LinkQueueNode TLinkQueueNode;//定義隊列節點類型
struct _tag_LinkQueueNode
{TLinkQueueNode* next;//下節點指針void* item;//節點存儲數據指針
};typedef struct _tag_LinkQueue//定義實際使用隊列類型
{TLinkQueueNode* front;//前節點（頭節點）一直指向第一個節點用于出隊列TLinkQueueNode* rear;//后節點int length;//長度
} TLinkQueue;LinkQueue* LinkQueue_Create() // 定義創建隊列函數
{TLinkQueue* ret = (TLinkQueue*)malloc(sizeof(TLinkQueue));if( ret != NULL )//創建成功{ret->front = NULL;//前節點指向空ret->rear = NULL;//后節點指向空ret->length = 0;//長度設空}return ret;//返回創建隊列
}void LinkQueue_Destroy(LinkQueue* queue) //定義銷毀隊列函數
{LinkQueue_Clear(queue);//先清空隊列free(queue);//釋放隊列空間
}void LinkQueue_Clear(LinkQueue* queue) // 定義清空隊列函數
{while( LinkQueue_Length(queue) > 0 )//將所有節點出隊列操作{LinkQueue_Retrieve(queue);}
}int LinkQueue_Append(LinkQueue* queue, void* item) //定義添加進隊列函數
{TLinkQueue* sQueue = (TLinkQueue*)queue;//取得隊列TLinkQueueNode* node = (TLinkQueueNode*)malloc(sizeof(TLinkQueueNode));//創建節點int ret = (sQueue != NULL ) && (item != NULL) && (node != NULL);//如果隊列與數據不為空和創建節點成功if( ret ){node->item = item;//給新建節點賦值存儲數據if( sQueue->length > 0 )//如果隊列當前長度大于0{sQueue->rear->next = node;//樹的后節點的下一個節點指向新建節點sQueue->rear = node;//將新建節點設為樹的后節點，實現每次添加都往連接node->next = NULL;//新建節點的下一個節點設空}else//否則是第一個節點{sQueue->front = node;//樹的前節點指向新建節點sQueue->rear = node;//樹的后節點指向新建節點node->next = NULL;//新節點的下一個節點為空}sQueue->length++;//長度增加}if( !ret )//如果條件不成功{free(node);//釋放新建節點空間}return ret;
}void* LinkQueue_Retrieve(LinkQueue* queue) //定義出隊列函數
{TLinkQueue* sQueue = (TLinkQueue*)queue;//取得隊列TLinkQueueNode* node = NULL;void* ret = NULL;if( (sQueue != NULL) && (sQueue->length > 0) )//如果隊列不為空與長度大于0{node = sQueue->front;//取得出隊列節點 sQueue->front = node->next;//將前節點指向出隊列節點的下一個節點ret = node->item;//取得節點存儲數據free(node);//釋放該節點sQueue->length--;//長度減少if( sQueue->length == 0 )//如果是最后一個節點，將隊列重置都為空{sQueue->front = NULL;sQueue->rear = NULL;}}return ret;//返回節點數據
}void* LinkQueue_Header(LinkQueue* queue) // 定義獲取頭節點函數
{TLinkQueue* sQueue = (TLinkQueue*)queue;//取得隊列void* ret = NULL;if( (sQueue != NULL) && (sQueue->length > 0) )//如果隊列不為空與長度大于0{ret = sQueue->front->item;//取得第一個節點存儲數據}return ret;//返回數據
}int LinkQueue_Length(LinkQueue* queue) // 定義獲取長度函數
{TLinkQueue* sQueue = (TLinkQueue*)queue;//取得樹int ret = -1;if( sQueue != NULL ){ret = sQueue->length;//取得長度}return ret;//返回長度
}

main.c

#include <stdio.h>
#include <stdlib.h>
#include "BTree.h"
#include "LinkQueue.h"struct Node//定義節點
{BTreeNode header;char v;
};void printf_data(BTreeNode* node)//將節點內容輸出函數
{if( node != NULL ){printf("%c", ((struct Node*)node)->v);}
}void pre_order_traversal(BTreeNode* root)//
{if( root != NULL ){printf("%c, ", ((struct Node*)root)->v);pre_order_traversal(root->left);pre_order_traversal(root->right);}
}void middle_order_traversal(BTreeNode* root)
{if( root != NULL ){middle_order_traversal(root->left);printf("%c, ", ((struct Node*)root)->v);middle_order_traversal(root->right);}
}void post_order_traversal(BTreeNode* root)
{if( root != NULL ){post_order_traversal(root->left);post_order_traversal(root->right);printf("%c, ", ((struct Node*)root)->v);}
}void level_order_traversal(BTreeNode* root)
{printf("==%c\n", ((struct Node*)root)->v);if( root != NULL ){LinkQueue* queue = LinkQueue_Create();//創建隊列if( queue != NULL )//創建成功{LinkQueue_Append(queue, root);//將節點進隊列while( LinkQueue_Length(queue) > 0 ){struct Node* node = (struct Node*)LinkQueue_Retrieve(queue);//出隊列printf("%c, ", node->v);//輸出節點存儲的數據LinkQueue_Append(queue, node->header.left);//將左子節點進隊列LinkQueue_Append(queue, node->header.right);//將右子節點進隊列}}LinkQueue_Destroy(queue);}
}int main(int argc, char *argv[])
{BTree* tree = BTree_Create();struct Node n1 = {{NULL, NULL}, 'A'};struct Node n2 = {{NULL, NULL}, 'B'};struct Node n3 = {{NULL, NULL}, 'C'};struct Node n4 = {{NULL, NULL}, 'D'};struct Node n5 = {{NULL, NULL}, 'E'};struct Node n6 = {{NULL, NULL}, 'F'};BTree_Insert(tree, (BTreeNode*)&n1, 0, 0, 0);BTree_Insert(tree, (BTreeNode*)&n2, 0x00, 1, 0);BTree_Insert(tree, (BTreeNode*)&n3, 0x01, 1, 0);BTree_Insert(tree, (BTreeNode*)&n4, 0x00, 2, 0);BTree_Insert(tree, (BTreeNode*)&n5, 0x02, 2, 0);BTree_Insert(tree, (BTreeNode*)&n6, 0x02, 3, 0);printf("Full Tree: \n");BTree_Display(tree, printf_data, 4, '-');printf("Pre Order Traversal:\n");pre_order_traversal(BTree_Root(tree));//輸出：ABDEFCprintf("\n");printf("Middle Order Traversal:\n");middle_order_traversal(BTree_Root(tree));//輸出：DBFEACprintf("\n");printf("Post Order Traversal:\n");post_order_traversal(BTree_Root(tree));//輸出：DFEBCAprintf("\n");printf("Level Order Traversal:\n");level_order_traversal(BTree_Root(tree));//輸出：ABCDEFprintf("\n");BTree_Destroy(tree);getchar();return 0;
}

分析：

LinkQueue ：

main中的調用函數過程：

匯編：