第三部分 樹與二叉樹[9]

    平衡化方法
　　LL型右旋一次
　　RR型左旋一次
　　LR型左旋一次右旋一次
　　RL型右旋一次左旋一次
　　
　　哈夫曼樹和哈夫曼編碼
　　
　　葉子結點的權值對葉子結點賦予的一個有意義的數值量
　　
　　二叉樹的帶權路徑長度設二叉樹具有n個帶權值的葉子結點從根結點到各個葉子結點的路徑長度與相應葉子結點權值的乘積之和
　　
　　哈夫曼樹給定一組具有確定權值的葉子結點帶權路徑長度最小的二叉樹
　　
　　【記】帶權路徑最小的樹
　　
　　哈夫曼算法基本思想
　　
　　（）初始化由給定的n個權值{ww…wn}構造n棵只有一個根結點的二叉樹從而得到一個二叉樹集合F＝{TT…Tn}
　　
　　（）選取與合並在F中選取根結點的權值最小的兩棵二叉樹分別作為左右子樹構造一棵新的二叉樹這棵新二叉樹的根結點的權值為其左右子樹根結點的權值之和
　　
　　（）刪除與加入在F中刪除作為左右子樹的兩棵二叉樹並將新建立的二叉樹加入到F中
　　
　　（）重復⑵⑶兩步當集合F中只剩下一棵二叉樹時這棵二叉樹便是哈夫曼樹

    返回《數據結構》考研復習精編

[]  []  []  []  []  []  []  []  []  []  

From:http://tw.wingwit.com/Article/program/sjjg/201311/23660.html