第06章樹和二叉樹

1、葉核亞葉核亞數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)（java版版）（第（第2版版）數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)（java版版）（第（第2版）版）第0章 java程序設計基礎第1章 緒論第2章 線性表第3章 棧與隊列第4章 串第5章 數(shù)組和廣義表第6章 樹和二叉樹第7章 圖第8章 查找第9章 排序第10章 綜合應用設計第11章 java開發(fā)運行環(huán)境數(shù)據(jù)結(jié)構(gòu)（java版）（第2版）第第6章章 樹和二叉樹樹和二叉樹l6.1 樹及其抽象數(shù)據(jù)類型樹及其抽象數(shù)據(jù)類型l6.2 二叉樹及其抽象數(shù)據(jù)類型二叉樹及其抽象數(shù)據(jù)類型l6.3 二叉樹的表示和實現(xiàn)二叉樹的表示和實現(xiàn)l6.4 線索二叉樹線索二叉樹l6.5 哈夫曼編碼與哈夫曼樹哈夫曼編碼與哈夫

2、曼樹l6.6 樹的表示樹的表示 目的：目的：理解樹結(jié)構(gòu)。理解樹結(jié)構(gòu)。 要求：要求：掌握二叉樹的表示和實現(xiàn)。掌握二叉樹的表示和實現(xiàn)。 重點：重點：二叉樹實現(xiàn)，哈夫曼樹。二叉樹實現(xiàn)，哈夫曼樹。 難點：難點：線索二叉樹，哈夫曼樹。線索二叉樹，哈夫曼樹。數(shù)據(jù)結(jié)構(gòu)（java版）（第2版）6.1 樹及其抽象數(shù)據(jù)類型樹及其抽象數(shù)據(jù)類型n6.1.1 樹定義樹定義n6.1.2 樹的術語樹的術語n6.1.3 樹的表示法樹的表示法n6.1.4 樹抽象數(shù)據(jù)類型樹抽象數(shù)據(jù)類型數(shù)據(jù)結(jié)構(gòu)（java版）（第2版）6.1.1 樹定義樹定義樹（樹（tree）是由）是由n（n0）個結(jié)點組成的有）個結(jié)點組成的有限集合。限集合。n=0

3、的樹稱為空樹；的樹稱為空樹；n0的樹的樹t：n根（根（root）結(jié)點，它沒有前驅(qū)結(jié)點。）結(jié)點，它沒有前驅(qū)結(jié)點。n其他結(jié)點分為其他結(jié)點分為m棵互不相交的子樹?？没ゲ幌嘟坏淖訕?。數(shù)據(jù)結(jié)構(gòu)（java版）（第2版）6.1.2 樹的術語樹的術語1.父母、孩子與兄弟結(jié)點父母、孩子與兄弟結(jié)點2.度度 3.結(jié)點層次、樹的高度結(jié)點層次、樹的高度4.邊、路徑邊、路徑 5.無序樹、有序樹無序樹、有序樹 6.森林森林數(shù)據(jù)結(jié)構(gòu)（java版）（第2版）6.1.3 樹的表示法樹的表示法1.圖示法圖示法2.橫向凹入表示法橫向凹入表示法 abefcgdhij3.廣義表表示廣義表表示 a(b(e, f), c(g), d(h,

4、i, j) 數(shù)據(jù)結(jié)構(gòu)（java版）（第2版）6.1.4 樹抽象數(shù)據(jù)類型樹抽象數(shù)據(jù)類型public interface ttree /樹接口樹接口 boolean isempty(); /判斷是否空樹判斷是否空樹 e getroot(); /返回根結(jié)點元素返回根結(jié)點元素 e getparent(e child); /返回返回child的父母結(jié)點的父母結(jié)點 int getchildcount(e parent); /返回返回parent孩子結(jié)點數(shù)孩子結(jié)點數(shù) e getfirstchild(e parent); /返回返回parent的孩子結(jié)點的孩子結(jié)點 e getnextsibling(e ele

5、ment); /返回下一個兄弟結(jié)點返回下一個兄弟結(jié)點 void traverse(); /遍歷樹遍歷樹 void insert (e parent, e element); /插入作為插入作為parent的孩子的孩子 void remove(e parent); /刪除以刪除以parent為根的子樹為根的子樹 void clear(); /清空清空數(shù)據(jù)結(jié)構(gòu)（java版）（第2版）6.2 二叉樹及其抽象數(shù)據(jù)類型二叉樹及其抽象數(shù)據(jù)類型n6.2.1 二叉樹定義二叉樹定義n6.2.2 二叉樹性質(zhì)二叉樹性質(zhì)n6.2.3 二叉樹抽象數(shù)據(jù)類型二叉樹抽象數(shù)據(jù)類型數(shù)據(jù)結(jié)構(gòu)（java版）（第2版）6.2.1 二叉

6、樹定義二叉樹定義二叉樹（二叉樹（binary tree）是）是n個結(jié)點的有限集合：個結(jié)點的有限集合：n空二叉樹；空二叉樹；n由一個根結(jié)點、兩棵互不相交的左子樹和右由一個根結(jié)點、兩棵互不相交的左子樹和右子樹組成。子樹組成。 數(shù)據(jù)結(jié)構(gòu)（java版）（第2版）6.2.2 二叉樹性質(zhì)二叉樹性質(zhì)性質(zhì)性質(zhì)1：若根結(jié)點的層次為：若根結(jié)點的層次為1，則二叉樹第，則二叉樹第i層最層最多有多有2i 1（i1）個結(jié)點。）個結(jié)點。 性質(zhì)性質(zhì)2：在高度為：在高度為k的二叉樹中，最多有的二叉樹中，最多有2k 1個個結(jié)點（結(jié)點（k0）。）。 性質(zhì)性質(zhì)3：設一棵二叉樹的葉子結(jié)點數(shù)為：設一棵二叉樹的葉子結(jié)點數(shù)為n0，2度度結(jié)點

7、數(shù)為結(jié)點數(shù)為n2，則，則n0=n2+1。 數(shù)據(jù)結(jié)構(gòu)（java版）（第2版）性質(zhì)性質(zhì)4：一棵具有：一棵具有n個結(jié)點的完全二叉樹，其高個結(jié)點的完全二叉樹，其高度度 。性質(zhì)性質(zhì)5：一棵具有：一棵具有n個結(jié)點的完全二叉樹，對序號為個結(jié)點的完全二叉樹，對序號為i（0in）的結(jié)點，有：）的結(jié)點，有：若若i=0，則，則i為根結(jié)點，無父母結(jié)點；若為根結(jié)點，無父母結(jié)點；若i0，則，則i的父母結(jié)的父母結(jié)點序號為。點序號為。若若2i+1n，則，則i的左孩子結(jié)點序號為的左孩子結(jié)點序號為2i+1；否則；否則i無左孩子。無左孩子。若若2i+2n，則，則i的右孩子結(jié)點序號為的右孩子結(jié)點序號為2i+2；否則；否則i無右孩子。

8、無右孩子。 1log2nk數(shù)據(jù)結(jié)構(gòu)（java版）（第2版）6.2.3 二叉樹抽象數(shù)據(jù)類型二叉樹抽象數(shù)據(jù)類型public interface binaryttree /二叉樹接口二叉樹接口 boolean isempty(); /判斷是否空二叉樹判斷是否空二叉樹 int count(); /返回二叉樹的結(jié)點個數(shù)返回二叉樹的結(jié)點個數(shù) int height(); /返回二叉樹的高度返回二叉樹的高度 binarynode getroot(); /返回二叉樹的根結(jié)點返回二叉樹的根結(jié)點 binarynode getparent(binarynode node); /返回返回node父母結(jié)點父母結(jié)點 voi

9、d preorder(); /先根次序遍歷二叉樹先根次序遍歷二叉樹 void inorder(); /中根次序遍歷二叉樹中根次序遍歷二叉樹 void postorder(); /后根次序遍歷二叉樹后根次序遍歷二叉樹 void levelorder(); /按層次遍歷二叉樹按層次遍歷二叉樹 binarynode search(e element); /查找并返回元素為查找并返回元素為element結(jié)點結(jié)點 void insert(binarynode p, e element, boolean leftchild); /插入插入element元素作為元素作為p結(jié)點的左結(jié)點的左/右孩子右孩子 vo

10、id remove(binarynode p, boolean leftchild); /刪除刪除p的左的左/右子樹右子樹 void clear(); /清空清空數(shù)據(jù)結(jié)構(gòu)（java版）（第2版）6.3 二叉樹的表示和實現(xiàn)二叉樹的表示和實現(xiàn)n6.3.1 二叉樹的存儲結(jié)構(gòu)二叉樹的存儲結(jié)構(gòu)n6.3.2 二叉樹的二叉鏈表實現(xiàn)二叉樹的二叉鏈表實現(xiàn)n6.3.3 二叉樹的遍歷二叉樹的遍歷n6.3.4 構(gòu)造二叉樹構(gòu)造二叉樹n6.3.5 二叉樹的插入和刪除操作二叉樹的插入和刪除操作n6.3.6 二叉樹遍歷的非遞歸算法二叉樹遍歷的非遞歸算法n6.3.7 二叉樹的層次遍歷二叉樹的層次遍歷數(shù)據(jù)結(jié)構(gòu)（java版）（第2

11、版）6.3.1 二叉樹的存儲結(jié)構(gòu)二叉樹的存儲結(jié)構(gòu)1.二叉樹的順序存儲結(jié)構(gòu)二叉樹的順序存儲結(jié)構(gòu) 數(shù)據(jù)結(jié)構(gòu)（java版）（第2版）2.二叉樹的鏈式存儲結(jié)構(gòu)二叉樹的鏈式存儲結(jié)構(gòu) 二叉鏈表二叉鏈表三叉鏈表三叉鏈表 數(shù)據(jù)結(jié)構(gòu)（java版）（第2版）6.3.2 二叉樹的二叉鏈表實現(xiàn)二叉樹的二叉鏈表實現(xiàn)1.二叉鏈表結(jié)點類二叉鏈表結(jié)點類 public class binarynode /二叉樹的二叉鏈表結(jié)點類二叉樹的二叉鏈表結(jié)點類 public e data; /數(shù)據(jù)元素數(shù)據(jù)元素 public binarynode left, right; /分別指向左、右孩子分別指向左、右孩子2.二叉樹類二叉樹類 publ

12、ic class binarytree /二叉樹類二叉樹類 protected binarynode root; /根結(jié)點根結(jié)點數(shù)據(jù)結(jié)構(gòu)（java版）（第2版）6.3.3 二叉樹的遍歷二叉樹的遍歷先根次序：訪問根結(jié)點，遍歷左子樹，遍歷右子樹。先根次序：訪問根結(jié)點，遍歷左子樹，遍歷右子樹。中根次序：遍歷左子樹，訪問根結(jié)點，遍歷右子樹。中根次序：遍歷左子樹，訪問根結(jié)點，遍歷右子樹。后根次序：遍歷左子樹，遍歷右子樹，訪問根結(jié)點。后根次序：遍歷左子樹，遍歷右子樹，訪問根結(jié)點。先根遍歷序列：先根遍歷序列：a b d g c e f h中根遍歷序列：中根遍歷序列：d g b a e c h f后根遍歷序列

13、：后根遍歷序列：g d b e h f c a數(shù)據(jù)結(jié)構(gòu)（java版）（第2版）二叉樹三種次序遍歷的遞歸算法二叉樹三種次序遍歷的遞歸算法 private void preorder(binarynode p) /先根次序遍歷以先根次序遍歷以p結(jié)點為根的子樹結(jié)點為根的子樹 if (p!=null) /若二叉樹不空若二叉樹不空 system.out.print(p.data+ ); /訪問當前結(jié)點訪問當前結(jié)點 preorder(p.left); /按先根次序遍歷當前結(jié)點的左子樹按先根次序遍歷當前結(jié)點的左子樹 preorder(p.right); /按先根次序遍歷當前結(jié)點的右子樹按先根次序遍歷當前結(jié)點

14、的右子樹 【例例6.1】 構(gòu)造并遍歷二叉樹。構(gòu)造并遍歷二叉樹。n基于遍歷的操作基于遍歷的操作 數(shù)據(jù)結(jié)構(gòu)（java版）（第2版）6.3.4 構(gòu)造二叉樹構(gòu)造二叉樹1.先根和中根序列表示先根和中根序列表示 數(shù)據(jù)結(jié)構(gòu)（java版）（第2版）2.標明空子樹的先根序列表示標明空子樹的先根序列表示 【例例6.2】 輸出二叉樹中指定結(jié)點的所有祖先結(jié)點。輸出二叉樹中指定結(jié)點的所有祖先結(jié)點。數(shù)據(jù)結(jié)構(gòu)（java版）（第2版）3.廣義表表示廣義表表示 數(shù)據(jù)結(jié)構(gòu)（java版）（第2版）4.以完全二叉樹的層次遍歷序列構(gòu)以完全二叉樹的層次遍歷序列構(gòu)造鏈式存儲結(jié)構(gòu)的完全二叉樹造鏈式存儲結(jié)構(gòu)的完全二叉樹 【例例6.3】 建立二

15、叉鏈表表示的完全二叉樹。建立二叉鏈表表示的完全二叉樹。數(shù)據(jù)結(jié)構(gòu)（java版）（第2版）6.3.5 二叉樹的插入和刪除操作二叉樹的插入和刪除操作1.插入一個結(jié)點插入一個結(jié)點 2.刪除一棵子樹刪除一棵子樹 數(shù)據(jù)結(jié)構(gòu)（java版）（第2版）6.3.6 二叉二叉樹遍歷的非樹遍歷的非遞歸算法遞歸算法數(shù)據(jù)結(jié)構(gòu)（java版）（第2版）6.3.7 二叉樹的層次遍歷二叉樹的層次遍歷數(shù)據(jù)結(jié)構(gòu)（java版）（第2版）6.4 線索二叉樹線索二叉樹6.4.1 線索二叉樹定義線索二叉樹定義0 left指向 左孩 子ltag 1 left為線索 ，指向前驅(qū)結(jié) 點c0 rightrtag 1 right為線索 ，指向后繼 結(jié)

16、 點c數(shù)據(jù)結(jié)構(gòu)（java版）（第2版）6.4.2 中序線索二叉樹中序線索二叉樹1.二叉樹的中序線索化二叉樹的中序線索化 2.中序線索二叉樹類中序線索二叉樹類 3.中根次序遍歷中序線索二叉樹中根次序遍歷中序線索二叉樹 【例例6.4】 構(gòu)造中序線索二叉樹并進行中根次序構(gòu)造中序線索二叉樹并進行中根次序遍歷。遍歷。4.先根次序遍歷中序線索二叉樹先根次序遍歷中序線索二叉樹5.后根次序遍歷中序線索二叉樹后根次序遍歷中序線索二叉樹數(shù)據(jù)結(jié)構(gòu)（java版）（第2版）1.二叉二叉樹的中樹的中序線索序線索化化數(shù)據(jù)結(jié)構(gòu)（java版）（第2版）4.先根次序遍歷中序線索二叉樹先根次序遍歷中序線索二叉樹 數(shù)據(jù)結(jié)構(gòu)（java

17、版）（第2版）5.后根次序遍歷中序線索二叉樹后根次序遍歷中序線索二叉樹 數(shù)據(jù)結(jié)構(gòu)（java版）（第2版）6.5 哈夫曼編碼與哈夫曼樹哈夫曼編碼與哈夫曼樹6.5.1 哈夫曼編碼哈夫曼編碼6.5.2 哈夫曼樹哈夫曼樹數(shù)據(jù)結(jié)構(gòu)（java版）（第2版）6.5.1 哈夫曼編碼哈夫曼編碼存儲存儲“aaaabbbcddbbaaa”，字符集，字符集a、b、d、c，字符出現(xiàn)次數(shù)為，字符出現(xiàn)次數(shù)為7、5、2、1，頻率為，頻率為0.47、0.33、0.13、0.07，哈夫曼編碼過程為：，哈夫曼編碼過程為： aaaabbbcddbbaaa00001010101111101101010000數(shù)據(jù)結(jié)構(gòu)（java版）（第2

18、版）6.5.2 哈夫曼樹哈夫曼樹1.二叉樹的帶權外路徑長度二叉樹的帶權外路徑長度10wpl()niiiwl數(shù)據(jù)結(jié)構(gòu)（java版）（第2版）4.構(gòu)造哈夫曼樹并獲得哈夫曼編碼構(gòu)造哈夫曼樹并獲得哈夫曼編碼 哈夫曼樹定義為帶權外路徑長度最短的二叉樹。哈夫曼樹定義為帶權外路徑長度最短的二叉樹。哈夫曼樹不唯一哈夫曼樹不唯一 數(shù)據(jù)結(jié)構(gòu)（java版）（第2版）構(gòu)造哈夫曼樹構(gòu)造哈夫曼樹 數(shù)據(jù)結(jié)構(gòu)（java版）（第2版）例例6.5 構(gòu)造哈夫曼樹并獲得哈夫曼編碼。構(gòu)造哈夫曼樹并獲得哈夫曼編碼。數(shù)據(jù)結(jié)構(gòu)（java版）（第2版）圖圖6.35 哈夫曼樹和哈夫曼編碼哈夫曼樹和哈夫曼編碼若權值集合若權值集合5,29,7,8,14,23,3,11對應字符對應字符ahf192342hga835111010g：0000a：0001h：001f：01b：10e：110c：1110d：11111010010cd157108e291410b5