数据布局：树形布局（树、堆）详解

一、树

树的物理布局和逻辑布局上都是树形布局
（一）树的性子

   • ⼦树是不相交的
• 除了根结点外，每个结点有且仅有⼀个⽗结点
• ⼀棵N个结点的树有N-1条边
  （二）树的种类

树按照根节点的分支来分，可以分为二叉树和多叉树。
二叉树

   二叉树（Binary Tree）
界说：每个节点最多有两个子节点的树布局。可以是空树，或者由一个根节点和左、右子树组成。
  多叉树

   多叉树（Multiway Tree）
界说：每个节点可以有多个子节点的树布局，节点子节点的数量没有限定。
  树按照结点的特性来观察，又可以有满N叉树和完全N叉树
满N叉树

   满N叉树是一种深度为K的二叉树，此中每一层的节点数都到达了该层能有的最大节点数。
  

完全N叉树

   除了最后一层外，每一层都被完全填满，而且最后一层所有节点都尽量靠左排列。
  

（三）二叉树的实现

1、二叉树布局界说

用 typedef 可以使得反面的利用范围更广

1. typedef int BTDataType;
2. typedef struct BinaryTreeNode
3. {
4.         BTDataType data;
5.         struct BinaryTreeNode* left;
6.         struct BinaryTreeNode* right;
7. }BTNode;

复制代码

2、二叉树功能实现

（1）前序、中序、后序、层序遍历

下面的层序遍历方式采用的是一层一层的处理方式

1. void PreOrder(BTNode* root) {
2.         if (root == NULL) return;
3.         printf("%d ", root->data);
4.         PreOrder(root->left);
5.         PreOrder(root->right);
6.         return;
7. }
9. void InOrder(BTNode* root) {
10.         if (root == NULL) return;
11.         InOrder(root->left);
12.         printf("%d ", root->data);
13.         InOrder(root->right);
14.         return;
15. }
17. void PostOrder(BTNode* root) {
18.         if (root == NULL) return;
19.         PostOrder(root->left);
20.         PostOrder(root->right);
21.         printf("%d ", root->data);
22.         return;
23. }
25. void LevelOrder(BTNode* root) {
26.         queue<BTNode*> q;
27.         q.push(root);
28.         while (!q.empty()) {
29.                 int num = q.size();
30.                 for (int i = 0; i < num; i++) {
31.                         BTNode* temp = q.front();
32.                         if(temp->left) q.push(temp->left);
33.                         if(temp->right) q.push(temp->right);
34.                         printf("%d ", temp->data);
35.                         q.pop();
36.                 }
37.                 printf("\n");
38.         }
39.         return;
40. }

复制代码

（2）二叉树结点个数

两种方法都可以实现求结点个数，但是第二种必要别的创建变量吸收返回值，因此第一种方式比力好

1. //方法一
2. int BinaryTreeSize(BTNode* root) {
3.         if (root == NULL) return 0;
4.         return 1 + BinaryTreeSize(root->left) +
5.          BinaryTreeSize(root->right);
6. }
8. //方法二
9. void BinaryTreeSize(BTNode* root, int* psize) {
10.         if (root == NULL) return;
11.         if (root->left) {
12.                 (*psize)++;
13.                 BinaryTreeSize(root->left, psize);
14.         }
15.         if (root->right) {
16.                 (*psize)++;
17.                 BinaryTreeSize(root->right, psize);
18.         }
19.         return;
20. }

复制代码

（3） ⼆叉树叶⼦结点个数

只必要统计叶子结点即可，和求普通结点个数相似

1. int BinaryTreeLeafSize(BTNode* root) {
2.         if (root == NULL) return 0;
3.         if (root->left == NULL && root->right == NULL) return 1;
4.         return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
5. }

复制代码

（4） 二叉树第k层结点个数

必要加一个二叉树层数的变量

1. int BinaryTreeLevelKSize(BTNode* root, int k) {
2.         if (root == NULL) return 0;
3.         if (k == 1) return 1;
4.         return BinaryTreeLevelKSize(root->left, k - 1) + BinaryTreeLevelKSize(root->right, k - 1);
5. }

复制代码

（5）二叉树的深度/高度

1. int BinaryTreeDepth(BTNode* root) {
2.         if (root == NULL) return 0;
3.         int a = BinaryTreeDepth(root->left);
4.         int b = BinaryTreeDepth(root->right);
5.         return (a > b ? a : b) + 1;
6. }

复制代码

（6）⼆叉树查找值为x的结点

如果没有找到，不要忘记返回空

1. BTNode* BinaryTreeFind(BTNode* root, BTDataType x) {
2.         if (root == NULL) return NULL;
3.         if (root->data == x) return root;
4.         BTNode* left = BinaryTreeFind(root->left, x);
5.         if (left) return left;
6.         BTNode* right = BinaryTreeFind(root->right, x);
7.         if (right) return right;
8.         return NULL;
9. }

复制代码

（7）二叉树销毁

采用二级指针的方式传入，可以制止函数处理后在举行置空处理。

1. void BinaryTreeDestory(BTNode** root) {
2.         if (*root == NULL) return;
3.         BinaryTreeDestory(&((*root)->left));
4.         BinaryTreeDestory(&((*root)->right));
5.         free(*root);
6.         *root = NULL;
7.         return;
8. }

复制代码

（8）判断二叉树是否为完全二叉树

这段代码是老夫目前想了许久，以为很有不错的代码，先不思量它的实现复杂度以及简洁水平，它实现的功能不错，可以将二叉树包括空结点放在队列之中，自己以为很好，哈哈，也许你没看到这句，那我就放心了。

1. bool BinaryTreeComplete(BTNode* root) {
2.         queue<BTNode*> q;
3.         BinaryTreePushQueue(root, q);
4.         while (!q.empty()) {
5.                 if (q.front() != NULL) q.pop();
6.                 else break;
7.         }
8.         while (!q.empty()) {
9.                 if (q.front() == NULL) q.pop();
10.                 else return false;
11.         }
12.         return true;
13. }
15. void BinaryTreePushQueue(BTNode* root, queue<BTNode*>& q) {
16.         vector<vector<BTNode*>> v;
17.         BinaryNodePushVector(root, v, 0);
18.         for (int i = 0; i < v.size(); i++) {
19.                 for (auto x : v[i]) {
20.                         q.push(x);
21.                 }
22.         }
23.         return;
24. }
26. void BinaryNodePushVector(BTNode* root, vector<vector<BTNode*>>& v, int k) {
27.         if (v.size() == k) v.push_back(vector<BTNode*>());
28.         if (root == NULL) {
29.                 v[k].push_back(NULL);  //如果不处理空结点，取消这步即可
30.                 return;
31.         }
32.         v[k].push_back(root);
33.         BinaryNodePushVector(root->left, v, k + 1);
34.         BinaryNodePushVector(root->right, v, k + 1);
35.         return;
36. }

复制代码

二、堆

堆的物理布局是一段连续空间，但是逻辑机构是树形布局
（一）堆的实现

1、堆的布局界说

下面通过宏函数来实现交换，可以使得交换简便，或者用指针也行。

1. typedef int HeapDataType;
3. typedef struct Heap {
4.         HeapDataType* __data;
5.         HeapDataType* data;
6.         int count;
7.         int capacity;
8. }Heap;

复制代码

1. #define SWAP(a ,b){\
2.         HeapDataType c = (a);\
3.         (a) = (b);\
4.         (b) = (c);\
5. }

复制代码

2、堆的初始化

用偏移量的方式，节约了内存。
从数组下标为1开始分配结点，使得反面求父节点，左右孩子运算和逻辑更简单

1. void HeapInit(Heap* pHeap) {
2.         assert(pHeap);
3.         pHeap->__data = (HeapDataType*)malloc(sizeof(HeapDataType));
4.         pHeap->data = pHeap->__data - 1;
5.         pHeap->capacity = 1;
6.         pHeap->count = 0;
7.         return;
8. }

复制代码

3、向上调整操作

可以利用递归或者是循环来实现向上调整

1. void Heap_UP_Update(Heap* pHeap, int i) {
2.         assert(pHeap);
3.         while (FATHER(i) >= 1 && pHeap->data[FATHER(i)] > pHeap->data[i]) {
4.                 SWAP(pHeap->data[FATHER(i)], pHeap->data[i]);
5.                 i = FATHER(i);
6.         }
7.         return;
8. }
10. void DG_Heap_UP_Update(Heap* pHeap, int i) {
11.         assert(pHeap);
12.         if (FATHER(i) < 1) return;
13.         if (pHeap->data[FATHER(i)] > pHeap->data[i]) {
14.                 SWAP(pHeap->data[FATHER(i)], pHeap->data[i]);
15.                 i = FATHER(i);
16.                 DG_Heap_UP_Update(pHeap, i);
17.         }
18.         return;
19. }

复制代码

4、向下调整操作

1. void Heap_DOWN_Update(Heap* pHeap, int i) {
2.         assert(pHeap);
3.         int size = pHeap->count - 1;
4.         while (LEFT(i) <= size) {
5.                 int l = LEFT(i), r = RIGHT(i), ind = i;
6.                 if (pHeap->data[ind] > pHeap->data[l]) ind = l;
7.                 if (r <= size && pHeap->data[ind] > pHeap->data[r]) ind = r;
8.                 if (ind == i) break;
9.                 SWAP(pHeap->data[i], pHeap->data[ind]);
10.                 i = ind;
11.         }
12.         return;
13. }

复制代码

5、入堆操作

1. void HeapPush(Heap* pHeap, HeapDataType x) {
2.         assert(pHeap);
3.         HeapCheckCapacity(pHeap);
4.         pHeap->data[pHeap->count + 1] = x;
5.         DG_Heap_UP_Update(pHeap, pHeap->count + 1);
6.         pHeap->count += 1;
7.         return;
8. }

复制代码

6、堆的扩容

1. void HeapCheckCapacity(Heap* pHeap) {
2.         assert(pHeap);
3.         if (pHeap->capacity == pHeap->count) {
4.                 HeapDataType* temp = (HeapDataType*)realloc(pHeap->__data, 2 * pHeap->capacity * sizeof(HeapDataType));
5.                 if (!temp) {
6.                         perror("Heap Realloc Fail!");
7.                         exit(1);
8.                 }
9.                 pHeap->__data = temp;
10.                 pHeap->capacity *= 2;
11.         }
12.         return;
13. }

复制代码

7、出堆操作

1. void HeapPop(Heap* pHeap) {
2.         assert(pHeap);
3.         assert(!HeapEmpty(pHeap));
4.         pHeap->data[1] = pHeap->data[pHeap->count];
5.         Heap_DOWN_Update(pHeap, 1);
6.         pHeap->count -= 1;
7.         return;
8. }

复制代码

8、堆的销毁

1. void HeapDestroy(Heap* pHeap) {
2.         assert(pHeap);
3.         free(pHeap->__data);
4.         pHeap->data = NULL;
5.         pHeap->__data = NULL;
6.         pHeap->capacity = 0;
7.         pHeap->count = 0;
8.         return;
9. }

复制代码

9、堆的判空、检察堆顶元素

1. int HeapEmpty(Heap* pHeap) {
2.         assert(pHeap);
3.         return pHeap->count == 0;
4. }
6. HeapDataType HeapTop(Heap* pHeap) {
7.         assert(!HeapEmpty(pHeap));
8.         return pHeap->data[1];
9. }

复制代码

（二）哈夫曼编码实现

1. #define _CRT_SECURE_NO_WARNINGS
2. #include<stdio.h>
3. #include<stdlib.h>
4. #include<time.h>
5. #include<string.h>
6. #include<algorithm>
7. #include<unordered_map>
8. #include<vector>
9. using namespace std;
11. #define FATHER(i) ((i) / 2)
12. #define LEFT(i) ((i) * 2)
13. #define RIGHT(i) ((i) * 2 + 1)
15. typedef struct Node {
16.         char* c;
17.         int freq;
18.         struct Node* lchild, * rchild;
19. }Node;
21. template<typename T>
22. void Swap(T& a, T& b) {
23.         T c = a;
24.         a = b;
25.         b = c;
26.         return;
27. }
29. //void swap(Node* a, Node* b) {
30. //        Node* c = a;
31. //        a = b;
32. //        b = c;
33. //        return;
34. //}
36. Node* getNewNode(int freq,const char* c) {
37.         Node* p = (Node*)malloc(sizeof(Node));
38.         p->freq = freq;
39.         p->c = _strdup(c);
40.         p->lchild = p->rchild = NULL;
41.         return p;
42. }
44. void clear(Node* root) {
45.         if (root == NULL) return;
46.         clear(root->lchild);
47.         clear(root->rchild);
48.         free(root);
49.         return;
50. }
52. typedef struct heap {
53.         Node** data, **__data;
54.         int size, count;
55. }heap;
57. heap* initHeap(int n) {
58.         heap* p = (heap*)malloc(sizeof(heap));
59.         p->__data = (Node**)malloc(sizeof(Node*) * n);
60.         p->data = p->__data - 1;
61.         p->size = n;
62.         p->count = 0;
63.         return p;
64. }
66. int empty(heap* h) {
67.         return h->count == 0;
68. }
70. int full(heap* h) {
71.         return h->count == h->size;
72. }
74. Node* top(heap* h) {
75.         if (empty(h)) return NULL;
76.         return h->data[1];
77. }
79. //void up_update(Node** data, int i) {
80. //        while (FATHER(i) >= 1) {
81. //                int ind = i;
82. //                if (data[i]->freq < data[FATHER(i)]->freq) {
83. //                        swap(data[i], data[FATHER(i)]);
84. //                }
85. //                if (ind == i) break;
86. //                i = FATHER(i);
87. //        }
88. //        return;
89. //}
91. void up_update(Node** data, int i) {
92.         while (i > 1 && data[i]->freq < data[FATHER(i)]->freq) {
93.                 Swap(data[i], data[FATHER(i)]);
94.                 i = FATHER(i);
95.         }
96.         return;
97. }
99. void down_update(Node** data, int i, int n) {
100.         while (LEFT(i) <= n) {
101.                 int ind = i, l = LEFT(i), r = RIGHT(i);
102.                 if (data[i]->freq > data[l]->freq) ind = l;
103.                 if (RIGHT(i) <= n && data[r]->freq < data[ind]->freq) ind = r;
104.                 if (ind == i) break;
105.                 Swap(data[ind], data[i]);
106.                 i = ind;
107.         }
108.         return;
109. }
111. void push(heap* h, Node* node) {
112.         if (full(h)) return;
113.         h->count += 1;
114.         h->data[h->count] = node;
115.         up_update(h->data, h->count);
116.         return;
117. }
119. void pop(heap* h) {
120.         if (empty(h)) return;
121.         h->data[1] = h->data[h->count];
122.         h->count -= 1;
123.         down_update(h->data, 1, h->count);
124.         return;
125. }
127. void clearHeap(heap* h) {
128.         if (h == NULL) return;
129.         free(h->__data);
130.         free(h);
131.         return;
132. }
134. Node* build_huffman_tree(Node** nodeArr, int n) {
135.         heap* h = initHeap(n);
136.         for (int i = 0; i < n; i++) {
137.                 push(h, nodeArr[i]);
138.         }
139.         Node* node1, * node2;
140.         int freq;
141.         for (int i = 1; i < n; i++) {
142.                 node1 = top(h);
143.                 pop(h);
144.                 node2 = top(h);
145.                 pop(h);
146.                 freq = node1->freq + node2->freq;
147.                 Node* node3 = getNewNode(freq, "0");
148.                 node3->lchild = node1;
149.                 node3->rchild = node2;
150.                 push(h, node3);
151.         }
152.         return h->data[1];
153. }
155. void output(Node* root) {
156.         if (root == NULL) return;
157.         output(root->lchild);
158.         //if (root->lchild == NULL && root->rchild == NULL)
159.                 printf("%s : %d\n", root->c, root->freq);
160.         output(root->rchild);
161.         return;
162. }
164. char charArr[100];
165. unordered_map<char*, char*> h;
167. void extract_huffman_code(Node* root, int i) {
168.         charArr[i] = 0;
169.         if (root->lchild == NULL && root->rchild == NULL) {
170.                 h[root->c] = _strdup(charArr);
171.                 return;
172.         }
173.         charArr[i - 1] = '0';
174.         extract_huffman_code(root->lchild, i + 1);
175.         charArr[i - 1] = '1';
176.         extract_huffman_code(root->rchild, i + 1);
177.         return;
178. }
181. int main() {
182. #define MAX_CHAR 26
183.         //1.首先用一个数组读取相关字符串及其频率
184.         Node** charArr = (Node**)malloc(sizeof(Node*)*MAX_CHAR);
185.         char arr[10];
186.         int freq;
187.         for (int i = 0; i < MAX_CHAR;i++) {
188.                 scanf("%s%d", arr, &freq);
189.                 charArr[i] = getNewNode(freq, arr);
190.         }
192.         //2.建立哈夫曼树
193.         Node* root = build_huffman_tree(charArr, MAX_CHAR);
195.         //3.提取哈夫曼编码进入unordered_map
196.         extract_huffman_code(root, 1);
198.         //4.将unordered_map转换成vector排序，可以按照字典序输出编码
199.         vector<pair<char*, char*>> v(h.begin(), h.end());
200.         sort(v.begin(), v.end(), [&](const pair<char*, char*>& a, const pair<char*, char*>& b) {
201.                 return strcmp(a.first, b.first) < 0;
202.                 });
203.         for (auto& x : v) {
204.                 printf("%s : %s\n", x.first, x.second);
205.         }
206.         return 0;
207. }

复制代码

结束语

关注博主的专栏，博主会分享更多的数据布局知识！