當前位置:文庫下載 > 所有分類 > IT/計算機 > 實驗六 樹的應用
免費下載此文檔侵權投訴

實驗六 樹的應用

(一)借助二叉排序樹實現排序 1.問題描述 對于給定的n個關鍵字值,采用二叉排序樹方法對其進行排序。 2.基本要求 以二叉鏈表作為存儲結構。 (二)哈夫曼樹的構造

實驗六 樹的應用

09計算機1 白楊 0929210028

(一)借助二叉排序樹實現排序

1.問題描述

對于給定的n個關鍵字值,采用二叉排序樹方法對其進行排序。

2.基本要求

以二叉鏈表作為存儲結構。

(二)哈夫曼樹的構造

1.問題描述

對于給定的n 個結點的權值,建立一棵哈夫曼樹。

2.基本要求

詳細說明所采用的哈夫曼樹的存儲格式及輸出方式。

3.測試數據

(1)7個葉子結點,權值分別為:7 5 2 3 8 10 20

(2)自擬。

本實驗最低要求為在4個學時內完成實驗內容(一)和(二)。

二叉排序樹:

又稱二叉查找樹,是樹最簡單的應用,是折半查找等的有用工具,有很大的應用價值。 二叉排序樹(binary sort tree)或者是一棵空二叉樹,或者是有如下性質的二叉樹:

1、若其左子樹非空,則左子樹上所有結點的值均小于它的根結 點的值;

2、若其右子樹非空,則右子樹上所有結點的值均大于它的根結點的值;

3、左、右子樹本身又是一棵二叉排序樹。

Huffman樹:

又稱最優二叉樹

它是n個帶權葉子結點構成的所有二叉樹中,WPL最小的二叉樹。

Huffman樹不唯一!

Huffman樹中無度為1 的結點。

Huffman 算法:

1. 根據給定n個權值{w1,w2,…,wn}及相應的n個結點構成n棵二叉樹的森林F={T1,T2,…Tn};

其中Ti(1≤i≤n)只有一個權值為wi的根結點

2. 在F中選兩棵根的權最小的樹,作為左右子樹構造一新的二叉樹,且新根的權為其左右子樹權之和;

3. 在F中刪除這兩棵樹,同時將新得到的二叉樹加入到F中;

4. 重復1、2,直至F中只有一棵樹,此時便為Huffman 樹。

/* 二叉排序樹 */

第1頁

免費下載Word文檔免費下載:實驗六 樹的應用

(下載1-6頁,共6頁)

猜你喜歡

返回頂部
火山小视频怎么赚钱