?
?
头文件binary.h代码：
?
?
复制代码
?1 #ifndef BINARY_H
?2 #define BINARY_H
?3?
?4 typedef int TYPE;
?5 typedef int BOOL;
?6?
?7 typedef struct _BTNode{
?8 ? ? TYPE data;
?9 ? ? int height; ? ? ? ??
10 ? ? struct _BTNode *lchild;
11 ? ? struct _BTNode *rchild;
12 }BTNode;
13?
14 typedef struct _BTree{
15 ? ? BTNode *phead; ? ?
16?
17 ? ? void(*init)(struct _BTree *BT, TYPE head_value);
18 ? ? void(*exit)(struct _BTree *BT);
19 ? ? void(*print)(struct _BTree *BT, BTNode *phead);
20?
21 ? ? BOOL(*add)(struct _BTree *BT, BTNode *phead, TYPE value);
22 ? ? BOOL(*del)(struct _BTree *BT, BTNode **phead, TYPE value);
23 ? ? BOOL(*del_tree)(struct _BTree *BT, BTNode **phead);
24 ? ? BOOL(*alter)(struct _BTree *BT, BTNode *phead, TYPE value, TYPE new_value);
25 ? ? BTNode *(*search)(struct _BTree *BT, BTNode *phead, TYPE value);
26?
27 ? ? BTNode *(*search_min)(struct _BTree *BT, BTNode **phead, int flag);
28 ? ? BTNode *(*search_max)(struct _BTree *BT, BTNode **phead, int flag); ? ?
29?
30 ? ? void(*pre_traverse)(struct _BTree *BT, BTNode *phead);
31 ? ? void(*mid_traverse)(struct _BTree *BT, BTNode *phead);
32 ? ? void(*last_traverse)(struct _BTree *BT, BTNode *phead);
33?
34 ? ? //以下为实现AVL所需函数
35 ? ? int (*node_height)(_BTree *BT, BTNode *phead);
36 ? ? void (*height)(_BTree *BT, BTNode *phead);
37 ? ? int (*max_height)(int height1, int height2);
38 ? ? BTNode *(*singleRotateLL)(_BTree *BT, BTNode *phead);
39 ? ? BTNode *(*singleRotateRR)(_BTree *BT, BTNode *phead);
40 ? ? BTNode *(*doubleRotateLR)(_BTree *BT, BTNode *phead);
41 ? ? BTNode *(*doubleRotateRL)(_BTree *BT, BTNode *phead);
42 }BTree;
43?
44 void tree_init(BTree *BT, TYPE value);
45 void tree_exit(BTree *BT);
46?
47 #endif
复制代码
源文件binary.cpp代码：
?
?
复制代码
? 1 #include
? 2 #include
? 3 #include
? 4?
? 5 #include "binary.h"
? 6?
? 7 void tree_init(BTree *BT, TYPE head_value);
? 8 void tree_exit(BTree *BT);
? 9 void tree_print(BTree *BT, BTNode *phead);
?10 static BOOL tree_add(BTree *BT, BTNode *phead, TYPE value);
?11 static BOOL tree_del(BTree *BT, BTNode **phead, TYPE value);
?12 static BOOL tree_del_tree(BTree *BT, BTNode **phead);
?13 static BOOL tree_alter(BTree *BT, BTNode *phead, TYPE value, TYPE new_value);
?14 static BTNode *tree_search(BTree *BT, BTNode *phead, TYPE value);
?15 static BTNode *tree_search_min(BTree *BT, BTNode **phead, int flag);
?16 static BTNode *tree_search_max(BTree *BT, BTNode **phead, int flag);
?17 static void tree_pre_traverse(BTree *BT, BTNode *phead);
?18 static void tree_mid_traverse(BTree *BT, BTNode *phead);
?19 static void tree_last_traverse(BTree *BT, BTNode *phead);
?20?
?21 //以下为实现AVL所需函数
?22 static int tree_node_height(BTree *BT, BTNode *phead);
?23 static void tree_height(BTree *BT, BTNode *phead);
?24 static int max_height(int height1, int height2);
?25 static BTNode *singleRotateLL(BTree *BT, BTNode *phead);
?26 static BTNode *singleRotateRR(BTree *BT, BTNode *phead);
?27 static BTNode *doubleRotateLR(BTree *BT, BTNode *phead);
?28 static BTNode *doubleRotateRL(BTree *BT, BTNode *phead);
?29?
?30?
?31 void tree_init(BTree *BT, TYPE head_value)
?32 {//初始化
?33 ? ? BT->phead = (BTNode*)calloc(1, sizeof(BTNode));
?34 ? ? BT->phead->data = head_va