《C++实现数据结构》：哈夫曼树_c++显示哈夫曼树

首先我们先来明确几个概念。
树的路径长度：从根到树中任意结点的路径长度是指从根结点到该结点的路径上所包括的边的数目，也相当于是该结点的层次-1。
树的内路径长度：除叶子结点外，从根到树中其他所有结点的路径长度之和。
树的外路径长度：从根到树中所有叶子结点的路径长度之和。
叶子结点的加权路径长度：从根到该叶子的路径长度与叶子的权的乘积。
树的加权路径长度：树中所有叶子结点的加权路径长度之和。
扩充二叉树：除叶子结点外，其余结点都必须有两个孩子。
所以，具有最小加权路径长度的扩充二叉树，可用于构造高效的不等长编码。
哈夫曼算法就是用来求如此的一棵扩充二叉树。
哈夫曼算法描述如下：
（1）用给定的一组权值{w1,w2,…,wn}，生成一个由n棵树组成的森林F={T1,T2,…,Tn}，其中每棵二叉树Ti只有一个结点，即权值为wi的根结点。
（2）从F中选择两棵根结点权值最小的树，作为新树根的左、右子树，新树根的权值是左、右子树根结点的权值之和。
（3）从F中删除这两棵树，另将新二叉树加入F中。
（4）重复（2）和（3），直到F中只包含一棵树为止。
————————————分割线——————————————
好了，理论说完了。接下来就用代码实现这个算法吧。
定义哈夫曼树类HfmTree，它是二叉树类的派生类。定义一个优先权队列，元素类型为哈夫曼树类，重载类型转换符将两个哈夫曼树对象间的比较转换成其数据成员weight间的比较，weight是该队列的优先权，最小的优先权最高。
为了实现这个算法，我花了近4个小时，orz。时间消耗在哪里了呢？就是浅拷贝和深拷贝的问题。一开始对于二叉树结点类BTNode和二叉树类BinaryTree，我没有自定义拷贝构造函数和赋值运算符，所以程序运行之后直接崩溃，因为其中涉及了指针成员变量，所以应该要注意拷贝构造函数和赋值运算符这两个的。知道了问题所在，接下来就是解决拷贝构造函数和赋值运算符了。然而，指针确实是个让人既爱又恨的存在，处理的时候要非常小心。唉，还是道行太浅了，这条路还很长，加油！最后，算是把程序调通了。（可能还有考虑不周到的地方，orz。）代码贴出如下：

//
// Created by huxijie on 17-3-21.
// 哈夫曼树

#include <iostream>
#include <stack>
#include <queue>
using namespace std;


// 用最小堆来实现优先权队列
template <typename T>
class PrioQueue{
private:
    T* q;
    int n,maxSize;          //maxSize是容量上限,n是队列中已有的数据个数
    void Swim(int k);       //上游,也就是向上调整
    void Sink(int k);       //下沉,也就是向下调整
    bool Less(int i, int j);
    void Swap(int i, int j);

public:
    PrioQueue();
    PrioQueue(int mSize);
    ~PrioQueue();
    bool IsEmpty() const;
    bool IsFull() const;
    bool GetMax(T &x);      //在x中返回具有最高优先权的元素值,并从优先权队列中删除该元素,返回true
    bool Append(const T &x); //元素值x加入队列
};

template <typename T>
PrioQueue<T>::PrioQueue() {
    this->PrioQueue(20);
}

template <typename T>
PrioQueue<T>::PrioQueue(int mSize) {
    maxSize = mSize;
    n = 0;
    q = new T[maxSize];
}

template <typename T>
PrioQueue<T>::~PrioQueue() {
    delete[]q;
}

template <typename T>
bool PrioQueue<T>::IsEmpty() const {
    return 0 == n;
}

template <typename T>
bool PrioQueue<T>::IsFull() const {
    return maxSize == n;
}

template <typename T>
bool PrioQueue<T>::Less(int i, int j) {
    if (q[i] < q[j]) {
        return true;
    } else {
        return false;
    }
}

template <typename T>
void PrioQueue<T>::Swap(int i, int j) {
    T tmp = q[i];
    q[i] = q[j];
    q[j] = tmp;
}

template <typename T>
void PrioQueue<T>::Swim(int k) {
    //如果子结点比父结点小,一直向上调整
    while (k >= 1 && Less(k,(k - 1) / 2)) {
        Swap((k - 1) / 2, k);
        k = (k - 1) / 2;
    }
}

template <typename T>
void PrioQueue<T>::Sink(int k) {
    int i;
    while (2 * k + 1 < n) {
        i = 2 * k + 1;
        //如果有右孩子并且右孩子比左孩子小
        if (i < n && Less(i + 1, i)) {
            i++;
        }
        if (!Less(i, k)) {  //父结点比子结点小,向下调整结束
            break;
        } else {
            Swap(k, i);
            k = i;
        }
    }
}

template <typename T>
bool PrioQueue<T>::GetMax(T &x) {
    if (IsEmpty()) {
        cout<<"Empty"<<endl;
        return false;
    } else {
        x = q[0];   //得到优先权最大的元素
        q[0] = q[n-1];  //将最后一个元素赋给根结点
        q[n-1].~T();
        n--;
        Sink(0);    //从根结点向下调整堆
        return true;
    }
}

template <typename T>
bool PrioQueue<T>::Append(const T &x) {
    if (IsFull()) {
        cout<<"Full"<<endl;
        return false;
    } else {
        q[n++] = x; //加入到堆底,结点数量加1
        Swim(n-1);  //从堆底向上调整堆
        return true;
    }
}

//二叉树结点类
template <typename T>
struct BTNode{
    T elemet;
    BTNode<T>* lChild,*rChild;

    BTNode() {
        lChild = rChild = NULL;
    }

//    ~BTNode() {
//        Clear(this);
//    }

    void Clear(BTNode<T> *t) {
        if (t != NULL) {
            Clear(t->lChild);
            Clear(t->rChild);
            delete (t);
            t = NULL;
        }
    }

    BTNode(const T& x,BTNode<T>* l, BTNode<T> *r) {
        elemet = x;
        lChild = l;
        rChild = r;
    }

    BTNode(const BTNode<T> &rhs) {
        Copy(&rhs);
    }

    BTNode<T>& operator=(const BTNode<T> &rhs) {
        Copy(&rhs);
        return *this;
    }


    BTNode<T>* Copy(const BTNode<T> *r) {
        if (this == r) {
            return NULL;
        }
        if (!r) {
            return NULL;
        } else {
            this->elemet = r->elemet;
            if (this->lChild != NULL) {
                this->Clear(this->lChild);
                this->lChild = NULL;
            }
            if (r->lChild != NULL) {
                this->lChild = new BTNode<T>;
                (this->lChild)->Copy(r->lChild);
            }
            if (this->rChild != NULL) {
                this->Clear(this->rChild);
                this->rChild = NULL;
            }
            if (r->rChild != NULL) {
                this->rChild = new BTNode<T>;
                (this->rChild)->Copy(r->rChild);
            }
            return this;
        }
    }

};

//二叉树类
template <typename T>
class BinaryTree{
private:
    void Clear(BTNode<T>* t);
    void PreOrder(void (*Visit)(T &x),BTNode<T> *r);
    void InOrder(void (*Visit)(T &x),BTNode<T> *r);
    void PostOrder(void (*Visit)(T &x),BTNode<T> *r);
    void LayerOrder(void (*Visit)(T &x), BTNode<T> *r);
    int Size(BTNode<T>* r);
    BTNode<T>* Copy(BTNode<T> *r);

protected:
    BTNode<T>* root;

public:
    BinaryTree();
    ~BinaryTree();
    BinaryTree(const BinaryTree<T> &);
    BinaryTree<T> &operator=(const BinaryTree<T>&);
    bool IsEmpty() const;
    void Clear();               //移去所有结点,成为空二叉树
    bool Root(T& x) const;      //若二叉树非空,则x为根的值,并返回true
    //构造一棵二叉树,根的值为x,以left和right为左右子树
    void MakeTree(const T& x,BinaryTree<T>& left,BinaryTree<T>& right);
    void PreOrder(void (*Visit)(T &x));            //先序遍历
    void InOrder(void (*Visit)(T &x));             //中序遍历
    void PostOrder(void (*Visit)(T &x));           //后序遍历
    void LayerOrder(void (*Visit)(T &x));          //层次遍历
    int Size();                 //结点个数
    BTNode<T>* Copy();          //二叉树的复制
};

template <typename T>
BinaryTree<T>::BinaryTree() {
    root = NULL;
}

template <typename T>
BinaryTree<T>::~BinaryTree() {
    Clear();
}

template <typename T>
BinaryTree<T>::BinaryTree(const BinaryTree<T> &rhs) {
    this->root = new BTNode<T>;
    *(this->root) = *(rhs.root);
}

template <typename T>
BinaryTree<T>& BinaryTree<T>::operator=(const BinaryTree<T> &rhs) {
    if (this == &rhs) {
        return *this;
    }
    if (this->root == NULL) {
        this->root = new BTNode<T>;
    }
    *(this->root) = *(rhs.root);
    return *this;
}

template <typename T>
bool BinaryTree<T>::IsEmpty() const {
    if (root == NULL) {
        return true;
    } else {
        return false;
    }
}

//递归实现清空二叉树
template <typename T>
void BinaryTree<T>::Clear(BTNode<T> *t) {
    if (!t) {
        return;
    } else {
        Clear(t->lChild);
        Clear(t->rChild);
        delete (t);
        t = NULL;
    }
}

template <typename T>
void BinaryTree<T>::Clear() {
    Clear(root);
    root = NULL;
}

template <typename T>
bool BinaryTree<T>::Root(T &x) const {
    if (IsEmpty()) {
        return false;
    }else {
        x = root->elemet;
        return true;
    }
}

template <typename T>
void BinaryTree<T>::MakeTree(const T &x, BinaryTree<T> &left, BinaryTree<T> &right) {
    if (root || &left == &right) {    //若root不空则返回,若左右子树相同则返回,不构造树
        return;
    }
    root = new BTNode<T>(x, left.root, right.root);
    left.root = NULL;
    right.root = NULL;
}

//访问元素的函数,作为参数传入遍历函数中
template <typename T>
void Visit(T &x) {
    cout << x << " ";
}

递归实现先序遍历
//template <typename T>
//void BinaryTree<T>::PreOrder(void (*Visit)(T &x),BTNode<T> *r) {
//    if (r) {
//        Visit(r->elemet);
//        PreOrder(Visit, r->lChild);
//        PreOrder(Visit, r->rChild);
//    }
//}

//非递归实现先序遍历
template <typename T>
void BinaryTree<T>::PreOrder(void (*Visit)(T &x),BTNode<T> *r) {
    if (r == NULL) {
        return;
    }
    BTNode<T>* p = r;
    stack<BTNode<T> *> mystack;
    while (p != NULL || !mystack.empty()) {
        //边遍历边打印,并存入栈中,以后需要通过这些结点进入右子树
        while (p != NULL) {
            Visit(p->elemet);
            mystack.push(p);
            p = p->lChild;
        }
        //当p为空时,说明根和左子树已经遍历完了,需要进入右子树了
        if (!mystack.empty()) {
            p = mystack.top();
            mystack.pop();
            p = p->rChild;
        }
    }
}

template <typename T>
void BinaryTree<T>::PreOrder(void (*Visit)(T &)) {
    PreOrder(Visit, root);
}

递归实现中序遍历
//template <typename T>
//void BinaryTree<T>::InOrder(void (*Visit)(T &), BTNode<T> *r) {
//    if (r) {
//        InOrder(Visit, r->lChild);
//        Visit(r->elemet);
//        InOrder(Visit, r->rChild);
//    }
//}

//非递归实现中序遍历
template <typename T>
void BinaryTree<T>::InOrder(void (*Visit)(T &), BTNode<T> *r) {
    if (r == NULL) {
        return;
    }
    BTNode<T> *p = r;
    stack<BTNode<T>*> mystack;

    while (p != NULL || !mystack.empty()) {
        //一直遍历到最后一棵左子树,边遍历边保存根结点到栈中
        while (p != NULL) {
            mystack.push(p);
            p = p->lChild;
        }
        //当p为空时,说明已经到达最后一棵左子树了,这时需要出栈了
        if (!mystack.empty()) {
            p = mystack.top();
            mystack.pop();
            Visit(p->elemet);
            //进入右子树,开始新的一轮左子树遍历
            p = p->rChild;
        }
    }
}

template <typename T>
void BinaryTree<T>::InOrder(void (*Visit)(T &)) {
    InOrder(Visit, root);
}

递归实现后序遍历
//template <typename T>
//void BinaryTree<T>::PostOrder(void (*Visit)(T &), BTNode<T> *r) {
//    if (r) {
//        PostOrder(Visit, r->lChild);
//        PostOrder(Visit, r->rChild);
//        Visit(r->elemet);
//    }
//}

//非递归实现后序遍历
template <typename T>
void BinaryTree<T>::PostOrder(void (*Visit)(T &), BTNode<T> *r) {
    if (r == NULL) {
        return;
    }
    stack<BTNode<T>*> mystack;
    BTNode<T>* pCur = r;        //当前访问结点
    BTNode<T>* pLast = NULL;    //上次访问结点

    //一直遍历到最后一棵左子树,边遍历边保存根结点到栈中
    while (pCur != NULL) {
        mystack.push(pCur);
        pCur = pCur->lChild;
    }

    //已经遍历到最后一棵左子树了,接下来从栈中取结点
    while (!mystack.empty()) {
        pCur = mystack.top();
        mystack.pop();
        //一个根结点被访问的前提是：无右子树或者右子树已被访问过
        if (pCur->rChild == NULL || pCur->rChild == pLast) {
            Visit(pCur->elemet);
            //修改最近被访问的结点
            pLast = pCur;
        } else { //先进入右子树
            mystack.push(pCur);     //根结点重新入栈
            pCur = pCur->rChild;    //进入右子树
            while (pCur != NULL) {  //开始在右子树中一直遍历到最后一棵左子树
                mystack.push(pCur);
                pCur = pCur->lChild;
            }
        }
    }
}

template <typename T>
void BinaryTree<T>::PostOrder(void (*Visit)(T &)) {
    PostOrder(Visit, root);
}

//用队列实现层次遍历
template <typename T>
void BinaryTree<T>::LayerOrder(void (*Visit)(T &x),BTNode<T> *r) {
    if (!r) {
        return;
    }
    queue<BTNode<T>*> myqueue;
    BTNode<T> *p = r;
    while (p != NULL || !myqueue.empty()) {
        if (p != NULL) {
            Visit(p->elemet);
            myqueue.push(p->lChild);
            myqueue.push(p->rChild);
        }
        p = myqueue.front();
        myqueue.pop();
    }
}

template <typename T>
void BinaryTree<T>::LayerOrder(void (*Visit)(T &)) {
    LayerOrder(Visit, root);
}

//递归实现求结点总数
template <typename T>
int BinaryTree<T>::Size(BTNode<T> *r) {
    if (!r) {
        return 0;
    } else {
        return Size(r->lChild) + Size(r->rChild) + 1;
    }
}

template <typename T>
int BinaryTree<T>::Size() {
    return Size(root);
}

//递归实现复制二叉树
template <typename T>
BTNode<T>* BinaryTree<T>::Copy(BTNode<T> *r) {
    if (!this) {
        return NULL;
    } else {
        BTNode<T> *p = new BTNode<T>(r->elemet);
        p->lChild = Copy(r->lChild);
        p->rChild = Copy(r->rChild);
        return p;
    }
}

template <typename T>
BTNode<T>* BinaryTree<T>::Copy() {
    return Copy(root);
}


//哈夫曼树类
template <typename T>
class HfmTree:public BinaryTree<T>{
private:
    T weight;   //二叉树根的权值
public:
    T GetW();
    operator T();   //重载类型转换运算符
    void PutW(const T& x);
    void SetNull(); //将二叉树置为空
};

template <typename T>
T HfmTree<T>::GetW() {
    return weight;
}

template <typename T>
HfmTree<T>::operator T() {
    return weight;
}

template <typename T>
void HfmTree<T>::PutW(const T &x) {
    weight = x;
}

template <typename T>
void HfmTree<T>::SetNull() {
    this->root = NULL;
}

//构造哈夫曼树,w[]中保存n个元素类型为T的权值
template <typename T>
HfmTree<T> CreateHfmTree(T w[],int n) {
    //定义一个优先权队列
    PrioQueue<HfmTree<T>> prioQueue(n);
    HfmTree<T> x,y,z;   //都是空哈夫曼树
    for (int i = 0; i < n; ++i) {
        z.MakeTree(w[i], x, y); //构造树中只有一个结点的哈夫曼树
        z.PutW(w[i]);
        prioQueue.Append(z);    //将哈夫曼树对象加入优先权队列
        z.SetNull();            //将z置成空树
    }
    for (int j = 1; j < n; ++j) {
        prioQueue.GetMax(x);    //从优先权队列中得到两棵最小的树
        prioQueue.GetMax(y);
        //构造一棵新的哈夫曼树对象,根的权值为两棵子树的权值之和
        z.PutW(x.GetW() + y.GetW());
        z.MakeTree(x.GetW() + y.GetW(), x, y);
        //将新树加入队列中
        prioQueue.Append(z);
        z.SetNull();
    }//重复n-1次操作,最终队列中只剩下一棵树,也就是构造成功的哈夫曼树
    prioQueue.GetMax(z);
    return z;
}

int main() {
    int w[] = {3, 5, 9, 11, 12, 13};
    int n = 6;
    HfmTree<int> hfmTree = CreateHfmTree(w, n);

    cout<<"先序遍历：";
    hfmTree.PreOrder(Visit);
    cout<<endl;

    cout<<"中序遍历：";
    hfmTree.InOrder(Visit);
    cout<<endl;

    cout<<"后序遍历：";
    hfmTree.PostOrder(Visit);
    cout<<endl;

    cout<<"层次遍历：";
    hfmTree.LayerOrder(Visit);
    cout<<endl;

    cout<<"结点个数：";
    cout << hfmTree.Size()<<endl;

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585

最后得到的哈夫曼树如下：

程序运行结果如下：

先序遍历：53 23 11 12 30 13 17 8 3 5 9 
中序遍历：11 23 12 53 13 30 3 8 5 17 9 
后序遍历：11 12 23 13 3 5 8 9 17 30 53 
层次遍历：53 23 30 11 12 13 17 8 9 3 5 
结点个数：11

Process finished with exit code 0
1
2
3
4
5
6
7