目錄：

• • 代碼：
  • 分析：
  • 匯編：

代碼：

BTree.h

#ifndef _BTREE_H_ #define _BTREE_H_#define BT_LEFT 0 //定義左子節(jié)點標識 #define BT_RIGHT 1 //定義右子節(jié)點標識typedef void BTree;//定義樹類型 typedef unsigned long long BTPos;//定義樹位置類型typedef struct _tag_BTreeNode BTreeNode;//定義樹節(jié)點類型 struct _tag_BTreeNode {BTreeNode* left;BTreeNode* right; };typedef void (BTree_Printf)(BTreeNode*);//定義樹節(jié)點類型指針參數無返回值的函數類型BTree* BTree_Create();//聲明創(chuàng)建樹函數void BTree_Destroy(BTree* tree);//聲明銷毀樹函數void BTree_Clear(BTree* tree);//聲明清空樹函數int BTree_Insert(BTree* tree, BTreeNode* node, BTPos pos, int count, int flag);//聲明插入節(jié)點函數BTreeNode* BTree_Delete(BTree* tree, BTPos pos, int count);//聲明刪除節(jié)點函數BTreeNode* BTree_Get(BTree* tree, BTPos pos, int count);//聲明獲取節(jié)點函數BTreeNode* BTree_Root(BTree* tree);//聲明獲取根節(jié)點函數int BTree_Height(BTree* tree);//聲明獲取樹高度函數int BTree_Count(BTree* tree);//聲明獲取樹節(jié)點數量函數int BTree_Degree(BTree* tree);//聲明獲取樹度數函數void BTree_Display(BTree* tree, BTree_Printf* pFunc, int gap, char div);//聲明用函數處理每個節(jié)點的函數#endif

BTree.c

#include <stdio.h> #include <malloc.h> #include "BTree.h"typedef struct _tag_BTree TBTree;//定義實際使用樹類型 struct _tag_BTree {int count;//節(jié)點數量BTreeNode* root;//根節(jié)點 };static void recursive_display(BTreeNode* node, BTree_Printf* pFunc, int format, int gap, char div) // 定義遞歸處理節(jié)點函數 {int i = 0;if( (node != NULL) && (pFunc != NULL) )//如果節(jié)點與函數指針不為空{for(i=0; i<format; i++)//輸出占位符{printf("%c", div);}pFunc(node);//對節(jié)點進行函數處理printf("\n");if( (node->left != NULL) || (node->right != NULL) )//如果左子節(jié)點或右子節(jié)點不為空{recursive_display(node->left, pFunc, format + gap, gap, div);//處理左子節(jié)點，占位符數量以gap遞增recursive_display(node->right, pFunc, format + gap, gap, div);//處理右子節(jié)點，占位符數量以gap遞增}}else//如果節(jié)點或函數指針為空 只輸出占位符{for(i=0; i<format; i++)//輸出占位符{printf("%c", div);}printf("\n");} }static int recursive_count(BTreeNode* root) // 遞歸調用計算以一個節(jié)點開始下面所有子節(jié)點數量（包括第一次的節(jié)點本身）函數 {int ret = 0;if( root != NULL ){//遞歸調用每次調用只要不是空節(jié)點都會加1 數量ret = recursive_count(root->left) + 1 + recursive_count(root->right);}return ret; }static int recursive_height(BTreeNode* root) // 定義遞歸計算樹高度的函數 {int ret = 0;if( root != NULL ){int lh = recursive_height(root->left);int rh = recursive_height(root->right);ret = ((lh > rh) ? lh : rh) + 1;//取左右兩邊節(jié)點較多的再加上本身節(jié)點}return ret;//返回高度 }static int recursive_degree(BTreeNode* root) //定義遞歸計算度數函數 { //最大度數只會是2int ret = 0;if( root != NULL ){if( root->left != NULL ){ret++;}if( root->right != NULL ){ret++;}//如果是根節(jié)點是1，表示還不是最大度數，繼續(xù)往子節(jié)點尋找有沒有最大度數存在if( ret == 1 ){int ld = recursive_degree(root->left);int rd = recursive_degree(root->right);if( ret < ld )//如果該節(jié)點的左子節(jié)點中有度數比該節(jié)點大{ret = ld;//取左子節(jié)點返回的度數}if( ret < rd )//如果右子節(jié)點中有度數比現在度數{ret = rd;//取右子節(jié)點返回的度數}}}return ret;//返回最終度數 }BTree* BTree_Create()//定義創(chuàng)建樹函數 {TBTree* ret = (TBTree*)malloc(sizeof(TBTree));//申請使用的樹空間if( ret != NULL )//申請成功{ret->count = 0;//數量為0ret->root = NULL;//根節(jié)點為空}return ret;//返回創(chuàng)建樹 }void BTree_Destroy(BTree* tree) // 定義銷毀樹函數 {free(tree); }void BTree_Clear(BTree* tree) // 定義清空樹函數 {TBTree* btree = (TBTree*)tree;if( btree != NULL ){btree->count = 0;btree->root = NULL;} } /* count 表示插入節(jié)點的上面有多少層節(jié)點flag 表示原來該位置的節(jié)點位于插入節(jié)點的方向 */ int BTree_Insert(BTree* tree, BTreeNode* node, BTPos pos, int count, int flag) // 定義插入節(jié)點函數 {TBTree* btree = (TBTree*)tree;//轉換成使用樹類型//判斷樹與插入節(jié)點不為空，和flag標識是左邊或右邊int ret = (btree != NULL) && (node != NULL) && ((flag == BT_LEFT) || (flag == BT_RIGHT));int bit = 0;if( ret ){BTreeNode* parent = NULL;BTreeNode* current = btree->root;node->left = NULL;//將插入節(jié)點的左子節(jié)點設空node->right = NULL;//將插入節(jié)點的右子節(jié)點設空while( (count > 0) && (current != NULL) )//找到插入的位置{bit = pos & 1;//判斷pos是奇數還是偶數 （奇數往右偶數往左）pos = pos >> 1;parent = current;//父節(jié)點賦值if( bit == BT_LEFT )//如果是左邊{current = current->left;//取得節(jié)點左子節(jié)點指向}else if( bit == BT_RIGHT )//如果是右邊{current = current->right;//取得節(jié)點右子節(jié)點指向}count--;}if( flag == BT_LEFT )//如插入位置是左子節(jié)點{node->left = current;//將本來在該位置的節(jié)點設為新插入節(jié)點的左子節(jié)點}else if( flag == BT_RIGHT )//如果插入位置是右子節(jié)點{node->right = current;//將本來在該位置的節(jié)點設為新插入節(jié)點的右子節(jié)點}if( parent != NULL )//如果父節(jié)點不為空{if( bit == BT_LEFT ){parent->left = node;//父節(jié)點的左子節(jié)點指向新插入節(jié)點 }else if( bit == BT_RIGHT ){parent->right = node;//父節(jié)點的右子節(jié)點指向新插入節(jié)點}}else//父節(jié)點為表示是{btree->root = node;//將新插入節(jié)點當作根節(jié)點}btree->count++;//樹節(jié)點數量增加}return ret; }BTreeNode* BTree_Delete(BTree* tree, BTPos pos, int count) // 定義刪除節(jié)點函數 {/*注意：刪除節(jié)點后面，刪除的節(jié)點與其子節(jié)點都不在樹中，而且刪除的節(jié)點和其子節(jié)點的left和right 沒置空，還保持著對應關系 */TBTree* btree = (TBTree*)tree;//取得樹BTreeNode* ret = NULL; int bit = 0;if( btree != NULL )//樹不為空{BTreeNode* parent = NULL;BTreeNode* current = btree->root;//取得根節(jié)點while( (count > 0) && (current != NULL) )//取得刪除節(jié)點{bit = pos & 1;pos = pos >> 1;parent = current;if( bit == BT_LEFT ){current = current->left;}else if( bit == BT_RIGHT ){current = current->right;}count--;}if( parent != NULL )//如果父節(jié)點不為空{if( bit == BT_LEFT )//如果刪除節(jié)點是父節(jié)點的左邊{parent->left = NULL;//將父節(jié)點的左子節(jié)點置空不指向刪除節(jié)點了}else if( bit == BT_RIGHT )//如果刪除節(jié)點是父節(jié)點的右邊{parent->right = NULL;//將父節(jié)點的右子節(jié)點置空不指向刪除節(jié)點了}}else//如果父節(jié)點為空{btree->root = NULL;//直接將根節(jié)點置空}ret = current;//取得刪除節(jié)點//調用遞歸計算以刪除節(jié)點開始和其子節(jié)點數量，再總數減少得刪除該節(jié)點后樹的節(jié)點數btree->count = btree->count - recursive_count(ret);}return ret;//返回刪除節(jié)點 }BTreeNode* BTree_Get(BTree* tree, BTPos pos, int count) // 定義獲取節(jié)點函數 {TBTree* btree = (TBTree*)tree;//取得樹BTreeNode* ret = NULL; int bit = 0;if( btree != NULL )//樹不為空{BTreeNode* current = btree->root;//取得根節(jié)點while( (count > 0) && (current != NULL) )//找到要獲取的節(jié)點{bit = pos & 1;pos = pos >> 1;if( bit == BT_LEFT ){current = current->left;}else if( bit == BT_RIGHT ){current = current->right;}count--;}ret = current;//取得獲取節(jié)點}return ret;//返回獲取節(jié)點 }BTreeNode* BTree_Root(BTree* tree) // 定義獲取根節(jié)點函數 {TBTree* btree = (TBTree*)tree;//取得樹BTreeNode* ret = NULL;if( btree != NULL )//如果樹不為空{ret = btree->root;//取得根節(jié)點}return ret;//獲取根節(jié)點 }int BTree_Height(BTree* tree) // 定義獲取樹高度函數 {TBTree* btree = (TBTree*)tree;int ret = 0;if( btree != NULL )//如果查{ret = recursive_height(btree->root);//用根節(jié)點調用遞歸計算高度函數計算高度}return ret;//返回高度 }int BTree_Count(BTree* tree) // 定義獲取節(jié)點數量函數 {TBTree* btree = (TBTree*)tree;//取得樹int ret = 0;if( btree != NULL ){ret = btree->count;//取得樹節(jié)點數量}return ret;//返回數量 }int BTree_Degree(BTree* tree) // 定義獲取樹度數函數 {TBTree* btree = (TBTree*)tree;//取得樹int ret = 0;if( btree != NULL ){ret = recursive_degree(btree->root);//用根節(jié)點調用遞歸計算度數函數}return ret;//返回度數 }void BTree_Display(BTree* tree, BTree_Printf* pFunc, int gap, char div) //定義使用函數統(tǒng)一處理節(jié)點信息函數 {TBTree* btree = (TBTree*)tree;//取得樹if( btree != NULL ){recursive_display(btree->root, pFunc, 0, gap, div);//調用遞歸處理函數} }

main.c

#include <stdio.h> #include <stdlib.h> #include "BTree.h"struct Node {BTreeNode header;char v; };void printf_data(BTreeNode* node) {if( node != NULL ){printf("%c", ((struct Node*)node)->v);} }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("Height: %d\n", BTree_Height(tree));printf("Degree: %d\n", BTree_Degree(tree));printf("Count: %d\n", BTree_Count(tree));printf("Position At (0x02, 2): %c\n", ((struct Node*)BTree_Get(tree, 0x02, 2))->v);printf("Full Tree: \n");BTree_Display(tree, printf_data, 4, '-');BTree_Delete(tree, 0x00, 1);printf("After Delete B: \n");printf("Height: %d\n", BTree_Height(tree));printf("Degree: %d\n", BTree_Degree(tree));printf("Count: %d\n", BTree_Count(tree));printf("Full Tree: \n");BTree_Display(tree, printf_data, 4, '-');BTree_Clear(tree);printf("After Clear: \n");printf("Height: %d\n", BTree_Height(tree));printf("Degree: %d\n", BTree_Degree(tree));printf("Count: %d\n", BTree_Count(tree));BTree_Display(tree, printf_data, 4, '-');BTree_Destroy(tree);getchar();return 0; }

分析：

匯編：

總結

以上是生活随笔為你收集整理的二叉树（多路平衡搜索树）-（代码、分析、汇编）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。