title: "二叉樹(shù)"
date: 2015-06-25 08:59:24
categories: 數(shù)據(jù)結(jié)構(gòu)
tags: 數(shù)據(jù)結(jié)構(gòu)

概念

• 樹(shù)的最大度為2；

• 分左右子樹(shù)；

  
  

斜樹(shù)

• 左斜樹(shù)：所有結(jié)點(diǎn)都只有左子樹(shù)的二叉樹(shù)；
• 右斜樹(shù)：所有結(jié)點(diǎn)都只有右子樹(shù)的二叉樹(shù)；
• 其實(shí)在業(yè)務(wù)羅輯中如果真有這樣的需求，那直接使用 線(xiàn)性表 就可以了；
  

滿(mǎn)二叉樹(shù)

• 所有分支結(jié)點(diǎn)的度為２；
• 所有葉子結(jié)點(diǎn)只能分布在最下層上；

• 同樣深度的二叉樹(shù)中，滿(mǎn)二叉樹(shù)的結(jié)點(diǎn)數(shù)最多，葉子結(jié)點(diǎn)數(shù)最多；

  
  

完全二叉樹(shù)

• 二叉樹(shù)從根結(jié)點(diǎn)出發(fā)，按著層次從左到右遍歷，第i個(gè)結(jié)點(diǎn)的位置與滿(mǎn)二叉樹(shù)中對(duì)應(yīng)結(jié)點(diǎn)位置完全相同；
• 所有葉子結(jié)點(diǎn)只能出現(xiàn)在最下兩層；
• 若結(jié)點(diǎn)度為1，則該結(jié)點(diǎn)只有左子樹(shù)，不存在只有右子樹(shù)的情況；
• 結(jié)點(diǎn)分配 先左后右；
  

規(guī)則（特性）

1. 每層結(jié)點(diǎn)數(shù)：二叉樹(shù)的第ｉ層上最多有 （n=２^ｉ－１）個(gè)結(jié)點(diǎn)，（ｉ>=1）；

• 所有結(jié)點(diǎn)數(shù)：深度為Ｋ的二叉樹(shù)最多有(n=２^Ｋ－１)個(gè)結(jié)點(diǎn)，（Ｋ>=1） ；
• 對(duì)于任意一棵二叉樹(shù)，n0 ＝葉子結(jié)點(diǎn)總數(shù)、n1=度為１的結(jié)點(diǎn)總數(shù)、n2=度為２的結(jié)點(diǎn)總數(shù)、ｎ＝總結(jié)點(diǎn)數(shù)：n0=n2+1

• 分支線(xiàn)總數(shù)＝n-1=n1+2n2；
• ｎ=n0+n1+n2;
• n0+n1+n2-1 = n1+2n2 => n0=n2+1;

• 滿(mǎn)二叉樹(shù)的深度：log2(n+1)；
• 完全二叉樹(shù)的深度：向下取整數(shù)(log2n)+1；
• 因?yàn)橥耆鏄?shù)的所有葉子結(jié)點(diǎn)只能出現(xiàn)在最下兩層，并且倒數(shù)第二層是滿(mǎn)的情況，所以倒數(shù)第二層所在深度+1也是完全二叉樹(shù)的深度；
• 層序遍歷二叉樹(shù)的順序，對(duì)于任意一個(gè)結(jié)點(diǎn)編號(hào)　i（1<=i<=n），ｉ可以理解為數(shù)組下標(biāo)+1，因?yàn)閿?shù)組下標(biāo)是從０開(kāi)始的：

• 雙親結(jié)點(diǎn)編號(hào)：向下取整(i/2)；
• 如果２i>n，則該結(jié)點(diǎn)無(wú)左孩子，否則左孩子結(jié)點(diǎn)是 2i；

• 如果2i+1>n，則該結(jié)點(diǎn)無(wú)右孩子，否則右孩子結(jié)點(diǎn)是2i+1；

  
  

存儲(chǔ)方式

• 順序存儲(chǔ)，方便查詢(xún)操作，并且可以根據(jù)層序遍歷，合理的利用以上特性；

  
  
  binary-tree-arr
• 鏈?zhǔn)酱鎯?chǔ)，方便新增，刪除操作；結(jié)構(gòu)為數(shù)據(jù)域+左孩子指針+右孩子指針 （二叉鏈表），如果有必要的情況下可以添加雙親指針，指向結(jié)點(diǎn)的雙親（三叉鏈表），這都是根據(jù)業(yè)務(wù)需求 靈活控制 的；
  
  binary-tree-arr

總結(jié)：正是因?yàn)橥耆鏄?shù)有以上這些規(guī)則和特點(diǎn)，所以我們?cè)谌粘Ｊ褂弥斜M量使用完全二叉樹(shù)，存儲(chǔ)方式最好選擇順序存儲(chǔ)；

二叉樹(shù)的遍歷

• 主要針對(duì)鏈?zhǔn)酱鎯?chǔ)，按著一定順序訪(fǎng)問(wèn)各個(gè)結(jié)點(diǎn)，保證每個(gè)結(jié)點(diǎn)僅被訪(fǎng)問(wèn) 一次，以下是根據(jù)結(jié)點(diǎn)訪(fǎng)問(wèn)順序定義的；
  1. 前序：先訪(fǎng)問(wèn)根結(jié)點(diǎn) -> 遍歷左子樹(shù) -> 遍歷右子樹(shù)；先訪(fǎng)問(wèn)根結(jié)點(diǎn)
  • 中序：遍歷左子樹(shù) -> 訪(fǎng)問(wèn)根結(jié)點(diǎn) -> 遍歷右子樹(shù)；中間訪(fǎng)問(wèn)根結(jié)點(diǎn)
  • 后序：遍歷左子樹(shù) -> 遍歷右子樹(shù) -> 后訪(fǎng)問(wèn)根結(jié)點(diǎn)；后訪(fǎng)問(wèn)根結(jié)點(diǎn)

  • 層序：自上而下，從左到右逐層訪(fǎng)問(wèn)結(jié)點(diǎn)；

    
    

推導(dǎo)

• 已知前序、中序，可以唯一確定一個(gè)二叉樹(shù)；
• 已知后序、中序，可以唯一確定一個(gè)二叉樹(shù)；
• 但是已知前序、后序卻不能確定一棵二叉樹(shù)；

線(xiàn)索二叉樹(shù)

• 結(jié)點(diǎn)度<1的情況，相應(yīng)的空指針域遍歷時(shí)候指向它的前驅(qū)或后繼；
• 一次遍歷可以多次使用，在以后的應(yīng)用中減少遍歷算法，可以直接使用第一次遍歷的結(jié)果；
  

赫夫曼樹(shù)

• 路徑：結(jié)點(diǎn)之間的分支構(gòu)成兩個(gè)結(jié)點(diǎn)之間的路徑；
• 路徑長(zhǎng)度：兩個(gè)結(jié)點(diǎn)之間的分支數(shù)量；
• 樹(shù)的路徑長(zhǎng)度：從樹(shù)根到每一結(jié)點(diǎn)的路徑長(zhǎng)度之和；
• 葉子結(jié)點(diǎn)帶權(quán)路徑長(zhǎng)度：葉子結(jié)點(diǎn)到根結(jié)點(diǎn)的路徑長(zhǎng)度*葉子結(jié)點(diǎn)權(quán)值；
• 樹(shù)的帶權(quán)路徑長(zhǎng)度 WPL： 所有葉子結(jié)點(diǎn)帶權(quán)路徑長(zhǎng)度之和；
• 赫夫曼樹(shù) ： WPL 最小的二叉樹(shù)。也稱(chēng)最優(yōu)二叉樹(shù)；
  
  WPL

赫夫曼編碼

• 赫夫曼樹(shù)左分支代表0，右分支代表1
• 從根結(jié)點(diǎn)到葉子結(jié)點(diǎn)經(jīng)過(guò)的分支組成0和1的序列稱(chēng)為葉子結(jié)點(diǎn)對(duì)應(yīng)的字符編碼，即赫夫曼編碼。
  
  WPL-code