一種層級統(tǒng)計獲取帶權路徑長度算法

作者簡介：周銅（1962—），男，天津人，鄭州科技學院教授，主要研究方向：算法語言。

摘 要：哈夫曼二叉樹是一種最優(yōu)二叉樹，它是帶權路徑長度最短的二叉樹。為了使二叉樹的帶權路徑長度達到最小，在構建哈夫曼樹時需要遵循一個原則：權重越大的結點離樹根越近。因此，每次需要根據(jù)各個結點的權重值篩選出其中值最小的兩個結點，然后構建二叉樹。構建二叉樹有一定的規(guī)則，但是要確定是否最優(yōu)二叉樹，則必須通過計算其WPL值才能判斷。因此，需要設計一個專門計算WPL的算法，用以檢驗二叉樹帶權路徑長度的最小值。本文采用層級統(tǒng)計算法通過前序遍歷搜索帶有權值的葉子結點來獲得WPL值，為構建哈夫曼樹提供依據(jù)。

關鍵詞：帶權路徑；層級統(tǒng)計；算法

DOI：10.13783/j.cnki.cn41-1275/g4.2024.06.019

中圖分類號：TP393 文獻標識碼：A 文章編號：1008-3715（2024）06-0113-05

1 概述

1.1 哈夫曼編碼簡介

在數(shù)據(jù)結構的算法處理過程中，哈夫曼編碼是一種編碼技術，使用變長編碼表對源符號進行編碼^［1］。變長編碼表是通過對“來源符號”進行評估、根據(jù)其“出現(xiàn)頻度”得到的，出現(xiàn)頻度高的字母使用較短的編碼，而出現(xiàn)頻度低的則使用較長的編碼，這能夠使編碼之后字符串的平均長度、期望值降低，其本質是實現(xiàn)無損數(shù)據(jù)壓縮^［2］。若用普通方法存儲數(shù)據(jù)時，每個字母均占用一個字節(jié)，出現(xiàn)頻度高的字母存儲使用了普通編碼幾分之一的長度，而出現(xiàn)頻度低字符的存儲長度則高于其數(shù)倍^［3］。如果我們能夠對文章中各個字母出現(xiàn)概率有較準確的估算，存儲時就可以大幅度進行無損壓縮^［4］。

哈夫曼編碼由大衛(wèi)·哈夫曼（David A. Huffman）教授研發(fā)，采用數(shù)據(jù)樹型結構，在算法支持下構造出一棵最優(yōu)二叉樹^［5］。哈夫曼編碼是在哈夫曼樹的基礎之上構造出來的一種編碼形式，它的應用非常廣泛^［6］。

1.2 哈夫曼編碼過程

通過哈夫曼樹進而得到哈夫曼編碼的過程是：首先將每個出現(xiàn)的字符當作一個獨立的結點，其權值則是它出現(xiàn)的頻度或次數(shù)，權值越大，說明其出現(xiàn)頻度更高，這樣的結點應該放在更接近根結點的位置，以這種邏輯構造出的才是哈夫曼樹。顯然，樹中所有字符都應放在葉子結點，可將字符的編碼解釋為從根至該字符的所有路徑上“邊”的標記序列，其中邊標記為0表示“轉向左孩子”，標記為1表示“轉向右孩子”（左0右1）。而用其葉子結點與層數(shù)的乘積之和，即可得到最終二進制編碼的長度WPL。這個長度一般均低于采用固定長度編碼。哈夫曼編碼壓縮了一定比例的數(shù)據(jù)存儲空間。可見，哈夫曼樹可以構造出總長度最短的二進制編碼^［7］。

因此，討論哈夫曼樹（最優(yōu)二叉樹）帶權路徑長度算法具有重要實用價值。本文是在算法思想基礎上，用C++實現(xiàn)其最小二叉樹帶權路徑長度算法。

1.3 哈夫曼樹

哈夫曼樹的特點是帶權路徑長度最短，構建這樣的樹，必須使得權值較大的結點離根較近，才能使其乘積和最小，即：樹中所有葉子結點所具有的權值乘以其到根結點的路徑長度的積之和最小^［8］。根據(jù)樹的特點，一般情況下根結點為0層，則葉子結點到根結點的邊數(shù)即為葉結點的層數(shù)^［9］。而整個樹的路徑長度是從樹根到每一結點的路徑長度之和，記為：

WPL=（W1*L1+W2*L2+W3*L3+…+Wn*Ln），N個權值Wi（i=1，2，…n）

式中，Wi是第i個葉結點所帶的權值，Li是該葉結點到根結點的路徑長度。

這就是前述構建哈夫曼樹時需要遵循的原則：權重越大的結點離樹根越近，我們需要根據(jù)各個結點的權重值構建二叉樹。權重值可以理解為重要性，比如：我們在北京（根結點），計算下面兩個葉結點城市的帶權路徑和。通常，天津、鄭州、洛陽的重要性排序是天津（假設其權值為6）、鄭州（權值為5）、洛陽權值為4。天津、鄭州與北京直連，其路徑都是1，而洛陽需要經(jīng)過鄭州，其路徑是2。那么計算其帶權路徑和就是：（天津）6×1+（洛陽）4×2=14。但如果我們將天津掛在廊坊之下，此時，從北京到天津的路徑長度就變成2了，那么，樹的帶權路徑長度和為：6×2+4×2=20。這不是哈夫曼樹，因為其帶權路徑和不是最小的，沒有遵循“權值越大的結點應當離根結點越近”的原則。這里，因為鄭州不是葉子結點，所以不參加計算。

2 二叉樹的構建原則

構建二叉樹要遵循一定的規(guī)律，那么，如何確定是否最優(yōu)二叉樹則必須通過計算其WPL值才能判斷，所以，應該設計一個專門計算WPL的算法，用以檢驗誰是二叉樹帶權路徑長度的最小值。

最小二叉樹帶權路徑長度算法

所謂最小，無非是在多個取值中找到最小的那一個。找最小值用的是通用算法，將每個權值數(shù)據(jù)組合的（WPL）積和求出，分別放在數(shù)組中，然后排序找出最小的那一個。由于排序算法并無特殊，我們不再討論，而重點討論如何針對每一個組合計算其WPL值的算法。

2.1 算法原理

對于一棵最優(yōu)二叉樹（哈夫曼樹），給定n個權值作為n個葉子節(jié)點，計算其WPL值的算法因素如下：

（1）路徑和路徑長度：在一棵樹中，從一個結點往下可以達到其子孫結點之間的通路稱為路徑。通路中各個結點與其孩子結點間的路徑長度數(shù)為1，則從根結點到第L層結點的路徑長度為L-1（根結點為第0層）。

（2） 結點的權及帶權路徑長度：若將樹中結點賦予一個某種含義的數(shù)值，則這個數(shù)值稱為該結點的權，該結點路徑與其權值的乘積則是其帶權路徑長度。

（3） 樹的帶權路徑長度：規(guī)定為所有葉子結點的帶權路徑長度之和，記為WPL。算法的目的是計算WPL值 。這里要注意的是，參加計算的結點必須是葉子結點。

（4） 考慮因素：多種二叉樹結點結構，圖1是其中幾種情況實例。

2.2 層級統(tǒng)計算法

本代碼采用前序遍歷，對于每個結點做如下操作：

判斷是否葉子結點；

判斷其是否存在左子樹，若存在，則將其左結點作為當前結點；

判斷其是否存在右子樹，對于每個右結點（若存在）也要先處理其左子樹。

當2.1中（1）成立時，計算其結點WPL值，并累加存儲；

當2.1中（2）成立時，將左子樹作為當前結點，并層數(shù)+1，函數(shù)遞歸調用；回歸后判斷該結點是否存在右子結點，若存在，層數(shù)-1（返回一層）；

當2.1中（3）成立時，需要先判斷該右子結點的左子樹是否存在。

若存在，則直接將其左子結點作為當前結點，函數(shù)遞歸調用。因為每個結點總是先處理其左子樹，從左子樹返回上層結點后，其右子樹仍處于同層，所以層數(shù)不變；

若其左子樹不存在，則層數(shù)+1，將右子樹結點作為當前結點，函數(shù)遞歸調用。

由于三個判斷均是簡單判斷，2.1中（1）和（2）（3）不會同時成立，即：當（1）成立時，（2）和（3）均不成立；而（1）不成立時，（2）或（3）才可能成立。

對于每個結點采用遞歸調用，先順著左子樹找到其葉子結點計算其WPL值，然后逐層返回上個結點（回歸），再查找其右子結點，進而將其作為當前結點，重復上面的3個判斷。

WPL作為全局變量，其初值為0。

3 層級統(tǒng)計算法實現(xiàn)

3.1 定義二叉樹鏈表結點

每個結點需要做如下圖2定義：

其中：left域為左指針，right域為右指針，葉結點的weight域保存該結點的非負權值，層數(shù)L使用變量deep計數(shù)，root為指向T的根結點的指針，則每個帶權葉結點wpl = deep*weigth，那么，樹的WPL值則為：

3.2 層級統(tǒng)計算法

該算法采用先序遍歷，針對任意一個結點及其子樹，先判斷本結點是否為計算目標，然后處理左子樹、右子樹。針對任意結點均采用先序遍歷遞歸搜索左子樹查找計算目標，直到找到左子樹葉子結點，計算wpl后，再回歸一層查找該結點右子樹。

對于右子樹每個結點仍然采用先序遍歷，搜索其左子樹直到葉子結點，計算wpl后回歸。代碼中wpl是全局變量，用于累加存儲每個葉結點wpl之和。

本代碼的關鍵是對結點所在層級統(tǒng)計變量deep的控制。當進入一個新結點時應當deep+1，但是，當進入左結點和右結點和回歸時，不能簡單地deep+1或者deep-1，而要根據(jù)情況加以區(qū)別。進入左子結點時deep+1，但回歸時，只有其不存在右子結點時deep-1，否則，deep維持原值不變。因為還需要對右子結點搜索，但層數(shù)相同。

而在進入右子結點時，需判斷其有無左子結點，若有，則說明deep仍處于同一層；若無，則deep+1。

這兩處判斷是非常重要的關鍵所在。

函數(shù)Node *bu_tree（char *str）" 對輸入數(shù)據(jù)的格式分析，找出各個結點數(shù)據(jù)。結點定義為Node及其指針 *BiTree：

輸入數(shù)據(jù)采用諸如一下格式：

42（13，37（42，27））； 41（39（7，72（，42）），99（32（51（，47），39），26（，50）））

結點定義為：

typedef struct Node {

int weight； //結點數(shù)據(jù)

struct Node *lchild，，*rchild； //左右子樹指針

} Node，*BiTree；

3.3 函數(shù)采用遞歸算法

函數(shù)采用遞歸算法，每次用下一層結點地址作為函數(shù)地址遞歸調用。遞歸、回歸算法如圖3。

層級統(tǒng)計算法函數(shù)流程如圖4和圖5。

4 結束語

二叉樹是每個結點最多有兩個子樹的有序樹，通常子樹包含“左子樹”和“右子樹”。二叉樹算法是計算機科學重要組成部分，是一種最簡單、基礎、重要的樹結構。它的特點是支持強大的搜索算法、鏈式結構按需分配內(nèi)存、有規(guī)則的存儲對象等。它支持多種操作，復雜度比完成同樣功能的其他結構更低。

本文給出一種最小二叉樹帶權路徑長度算法，主要特征是在研究理論的基礎上通過C++代碼實現(xiàn)。代碼通過遞歸方法，前序遍歷搜索每個葉子結點并計算其wpl值之后，累加計算全樹WPL，對構建二叉樹提供可靠依據(jù)。

參考文獻：

［1］吐爾地·托合提，崔青，劉淑嫻. 哈夫曼樹在排序算法中的案例教學研究［J］. 現(xiàn)代計算機， 2021（14）： 96-99.

［2］杜敏，郭珊珊，潘鵬，等. 哈夫曼樹教學探討［J］. 電腦知識與技術， 2020 （2）： 106-108.

［3］陳桂英，王亞鵬. 哈夫曼樹及其應用［J］. 河南科技， 2014 （24）： 256-257.

［4］付勇. 一個利用小頂堆構造哈夫曼樹的C++算法［J］. 計算機應用與軟件， 2011（3）： 253-256.

［5］謝娜. 哈夫曼樹算法的改進［J］.電腦知識與技術， 2010（29）： 8224-8226.

［6］陳立山. 哈夫曼樹帶權路徑長度簡便算法［J］. 哈爾濱職業(yè)技術學院學報， 2007（4）： 109-110.

［7］陳麗芳，陳亮，劉保相. 基于粒計算的哈夫曼樹SVM多分類模型研究［J］. 計算機科學， 2016（1）： 64-68.

［8］王琛，王云，陳麗芳，等.哈夫曼樹SVM在空氣質量等級分類中的應用［J］. 智能計算機與應用， 2016（1）： 64-67.

［9］江忠. 哈夫曼樹Hufferman構成原理應用及其數(shù)學證明［J］. 科技廣場， 2016（2）： 20-25.

（責任編輯 李玉玲）

A Hierarchical Statistical Algorithm for Obtaining Weighted Path Length

ZHOU Tong¹， XU Shuang²

（1. Zhengzhou University of Science and Technology， Zhengzhou， Henan 450046， China;2. Zhengzhou University of Technology， Zhengzhou， Henan 450044， China）

Abstract：The huffman binary tree is an optimal binary tree， which is the shortest binary tree with weight path length. In order to minimize the weighted path length of a binary tree， a principle should be followed when constructing a Huffman tree， that is， the node with greater weight is closer to the root of the tree. Therefore， each time we need to filter out the two nodes with the smallest value according to the weight value of each node， and then build a binary tree. There are certain rules for constructing a binary tree， but to determine whether it is the optimal binary tree， it must be determined by calculating its WPL value. Therefore， it is necessary to design a special algorithm to calculate WPL to test which is the minimum value of the weighted path length of the binary tree. In this paper， the hierarchical statistical algorithm is used to search the leaf node with weight by preorder traversal to obtain the WPL value， which provides the basis for the construction of Huffman tree.

Key words：weighted path; hierarchical statistics; algorithm