樹是n個(gè)結(jié)點(diǎn)的有限集合，非空時(shí)必須滿足：只有一個(gè)稱為根的結(jié)點(diǎn)；其余結(jié)點(diǎn)形成m個(gè)不相交的子集，并稱根的子樹。
根是開始結(jié)點(diǎn)；結(jié)點(diǎn)的子樹數(shù)稱度；度為0的結(jié)點(diǎn)稱葉子(終端結(jié)點(diǎn))；度不為0的結(jié)點(diǎn)稱分支結(jié)點(diǎn)(非終端結(jié)點(diǎn))；除根外的分支結(jié)點(diǎn)稱內(nèi)部
　結(jié)點(diǎn)；
　有序樹是子樹有左，右之分的樹；無序樹是子樹沒有左，右之分的樹；森林是m個(gè)互不相交的樹的集合；　樹的四種不同表示方法：·樹形表示法；·嵌套集合表示法；·凹入表示法·廣義表表示法。　二叉樹的定義：是n≥0個(gè)結(jié)點(diǎn)的有限集，它是空集(n=0)或由一個(gè)根結(jié)點(diǎn)及兩棵互不相交的分別稱作這個(gè)根的左子樹和右子樹的二叉樹組成。
二叉樹不是樹的特殊情形，與度數(shù)為2的有序樹不同。
二叉樹的4個(gè)重要性質(zhì)： ·.二叉樹上第i層上的結(jié)點(diǎn)數(shù)目最多為2^(i-1)(i≥1).；
·深度為k的二叉樹至多有(2^k)-1個(gè)結(jié)點(diǎn)(k≥1)；
·.在任意一棵二叉樹中，若終端結(jié)點(diǎn)的個(gè)數(shù)為n0,度為2的結(jié)點(diǎn)數(shù)為n2，則n0=n2+1；
·.具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為int(log2n)+1。
滿二叉樹是一棵深度為k，結(jié)點(diǎn)數(shù)為(2^k)-1的二叉樹；完全二叉樹是滿二叉樹在最下層自右向左去處部分結(jié)點(diǎn)；
二叉樹的順序存儲(chǔ)結(jié)構(gòu)就是把二叉樹的所有結(jié)點(diǎn)按照層次順序存儲(chǔ)到連續(xù)的存儲(chǔ)單元中。（存儲(chǔ)前先將其畫成完全二叉樹）樹的存儲(chǔ)結(jié)構(gòu)多用的是鏈?zhǔn)酱鎯?chǔ)。BinTNode的結(jié)構(gòu)為lchild|data|rchild，把所有BinTNode類型的結(jié)點(diǎn)，加上一個(gè)指向根結(jié)點(diǎn)的BinTree型頭指針就構(gòu)成了二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，稱為二叉鏈表。它就是由根指針root唯一確定的。共有2n個(gè)指針域，n+1個(gè)空指針。

　根據(jù)訪問結(jié)點(diǎn)的次序不同可得三種遍歷：先序遍歷(前序遍歷或先根遍歷)，中序遍歷(或中根遍歷)、后序遍歷(或后根遍歷)。時(shí)間復(fù)雜度為O(n).

　利用二叉鏈表中的n+1個(gè)空指針域來存放指向某種遍歷次序下的前趨結(jié)點(diǎn)和后繼結(jié)點(diǎn)的指針，這些附加的指針就稱為"線索"，加上線索的
　二叉鏈表就稱為線索鏈表。線索使得查找中序前趨和中序后繼變得簡單有效，但對(duì)于查找指定結(jié)點(diǎn)的前序前趨和后序后繼并沒有什么作用。

樹和森林及二叉樹的轉(zhuǎn)換是唯一對(duì)應(yīng)的。
轉(zhuǎn)換方法： ·樹變二叉樹：兄弟相連，保留長子的連線。
 ·二叉樹變樹：結(jié)點(diǎn)的右孩子與其雙親連。
 ·森林變二叉樹：樹變二叉樹，各個(gè)樹的根相連。

樹的存儲(chǔ)結(jié)構(gòu)：·有雙親鏈表表示法：結(jié)點(diǎn)data | parent，對(duì)于求指定結(jié)點(diǎn)的雙親或祖先十分方便，但不適于求指定結(jié)點(diǎn)的孩子及后代。
 ·孩子鏈表表示法：為樹中每個(gè)結(jié)點(diǎn)data | next設(shè)置一個(gè)孩子鏈表firstchild，并將data | firstchild存放在一個(gè)向量中。
·雙親孩子鏈表表示法：將雙親鏈表和孩子鏈表結(jié)合。
·孩子兄弟鏈表表示法：結(jié)點(diǎn)結(jié)構(gòu)leftmostchild |data | rightsibing，附加兩個(gè)分別指向該結(jié)點(diǎn)的最左孩子和右鄰兄弟的指針域。

　樹的前序遍歷與相對(duì)應(yīng)的二叉樹的前序遍歷一致；樹的后序遍歷與相對(duì)應(yīng)的二叉樹的中序遍歷一致。

　樹的帶權(quán)路徑長度是樹中所有葉結(jié)點(diǎn)的帶權(quán)路徑長度之和。樹的帶權(quán)路徑長度最小的二叉樹就稱為最優(yōu)二叉樹（即哈夫曼樹）。
在葉子的權(quán)值相同的二叉樹中，完全二叉樹的路徑長度最短。
哈夫曼樹有n個(gè)葉結(jié)點(diǎn)，共有2n-1個(gè)結(jié)點(diǎn)，沒有度為1的結(jié)點(diǎn)，這類樹又稱為嚴(yán)格二叉樹。
變長編碼技術(shù)可以使頻度高的字符編碼短，而頻度低的字符編碼長，但是變長編碼可能使解碼產(chǎn)生二義性。如00、01、0001這三個(gè)碼無法
　在解碼時(shí)確定是哪一個(gè)，所以要求在字符編碼時(shí)任一字符的編碼都不是其他字符編碼的前綴，這種碼稱為前綴碼（其實(shí)是非前綴碼）。
哈夫曼樹的應(yīng)用最廣泛地是在編碼技術(shù)上，它能夠容易地求出給定字符集及其概率分布的最優(yōu)前綴碼。哈夫曼編碼的構(gòu)造很容易，只要畫
　好了哈夫曼樹，按分支情況在左路徑上寫代碼0，右路徑上寫代碼1，然后從上到下到葉結(jié)點(diǎn)的相應(yīng)路徑上的代碼的序列就是該結(jié)點(diǎn)的最優(yōu)前綴碼。