学步园

我在写一个哈夫曼编码解压缩文本文件时，遇到需要用一个数据结构来表示哈夫曼树的问题

一开始我是用面向对象的方法，采用最直观的建模方法,即链式存储结构：

template <class T><br /> class BiTreeNode<br /> {<br /> private:<br /> BiTreeNode<T>* leftChild;<br /> BiTreeNode<T>* rightChild;<br /> public:<br /> T data;<br /> BiTreeNode():leftChild(NULL),rightChild(NULL)<br /> {};<br /> BiTreeNode(T item,BiTreeNode<T>* left=NULL, BiTreeNode<T>* right=NULL):<br /> data(item),leftChild(left),rightChild(right)<br /> {};<br /> ~BiTreeNode()<br /> {};<br /> BiTreeNode<T>* &Left()<br /> {return leftChild;}<br /> BiTreeNode<T>* &Right()<br /> {return rightChild;}<br /> bool isLeaf() const<br /> {<br /> return (leftChild == NULL) && (rightChild == NULL) ;<br /> }<br /> }; 

这也是我学数据结构的时候遇到方法，但是此方法的效率太低，尤其是遍历很麻烦，导致程序无比的慢

后来看了别人的代码，哈夫曼树可以用一个数组表示，如果叶子结点的个数，由于哈夫曼树是一个颗二叉树，所以总结点树为2n-1。

用数组表示哈夫曼树，遍历效率会高很多。

我想，用数组比用指针表示更有效率的根本原因，是计算机的顺序储存结构。如果是人脑的话，那么他用神经元存储结构不同，所以人类最优的存储结构不是顺序的，是发散的。