1萝招，樹的高度和深度
樹的高度：從所有葉節(jié)點開始數(shù)高度到根節(jié)點蚂斤，其中的最大值；也就是從結點x向下到某個葉結點最長簡單路徑中邊的條數(shù)槐沼。（注意與節(jié)點的高度的一般默認從1開始曙蒸，最低為1）
樹的深度：樹根下中所有分支結點層數(shù)的最大值，遞歸定義岗钩。（一般以根節(jié)點深度層數(shù)為0）
2纽窟，哈希表
散列表（Hash table，也叫哈希表）兼吓，是根據(jù)關鍵碼值(Key value)而直接進行訪問的數(shù)據(jù)結構臂港。也就是說，它通過把關鍵碼值映射到表中一個位置來訪問記錄视搏，以加快查找的速度审孽。這個映射函數(shù)叫做散列函數(shù)，存放記錄的數(shù)組叫做散列表浑娜。
給定表M佑力，存在函數(shù)f(key)，對任意給定的關鍵字值key筋遭，代入函數(shù)后若能得到包含該關鍵字的記錄在表中的地址打颤，則稱表M為哈希(Hash）表，函數(shù)f(key)為哈希(Hash) 函數(shù)漓滔。
常用方法
散列函數(shù)能使對一個數(shù)據(jù)序列的訪問過程更加迅速有效编饺，通過散列函數(shù)，數(shù)據(jù)元素將被更快地定位响驴。
實際工作中需視不同的情況采用不同的哈希函數(shù)透且，通常考慮的因素有：
· 計算哈希函數(shù)所需時間
· 關鍵字的長度
· 哈希表的大小
· 關鍵字的分布情況
· 記錄的查找頻率
- 直接尋址法：取關鍵字或關鍵字的某個線性函數(shù)值為散列地址踏施。即H(key)=key或H(key) = a·key + b石蔗，其中a和b為常數(shù)（這種散列函數(shù)叫做自身函數(shù)）。若其中H(key）中已經(jīng)有值了畅形，就往下一個找，直到H(key）中沒有值了诉探，就放進去日熬。
- 數(shù)字分析法：分析一組數(shù)據(jù)，比如一組員工的出生年月日肾胯，這時我們發(fā)現(xiàn)出生年月日的前幾位數(shù)字大體相同竖席，這樣的話耘纱，出現(xiàn)沖突的幾率就會很大，但是我們發(fā)現(xiàn)年月日的后幾位表示月份和具體日期的數(shù)字差別很大毕荐，如果用后面的數(shù)字來構成散列地址束析，則沖突的幾率會明顯降低。因此數(shù)字分析法就是找出數(shù)字的規(guī)律憎亚，盡可能利用這些數(shù)據(jù)來構造沖突幾率較低的散列地址员寇。
- 平方取中法：當無法確定關鍵字中哪幾位分布較均勻時，可以先求出關鍵字的平方值第美，然后按需要取平方值的中間幾位作為哈希地址蝶锋。這是因為：平方后中間幾位和關鍵字中每一位都相關，故不同關鍵字會以較高的概率產(chǎn)生不同的哈希地址什往。
- 折疊法：將關鍵字分割成位數(shù)相同的幾部分扳缕，最后一部分位數(shù)可以不同，然后取這幾部分的疊加和（去除進位）作為散列地址别威。數(shù)位疊加可以有移位疊加和間界疊加兩種方法躯舔。移位疊加是將分割后的每一部分的最低位對齊，然后相加省古；間界疊加是從一端向另一端沿分割界來回折疊庸毫，然后對齊相加。
- 隨機數(shù)法：選擇一隨機函數(shù)衫樊，取關鍵字的隨機值作為散列地址飒赃，通常用于關鍵字長度不同的場合。
- 除留余數(shù)法：取關鍵字被某個不大于散列表表長m的數(shù)p除后所得的余數(shù)為散列地址科侈。即 H(key) = key MOD p,p<=m载佳。不僅可以對關鍵字直接取模，也可在折疊臀栈、平方取中等運算之后取模蔫慧。對p的選擇很重要，一般取素數(shù)或m权薯，若p選的不好姑躲，容易產(chǎn)生同義詞。
處理沖突
- 開放尋址法：Hi=(H(key) + di) MOD m,i=1,2盟蚣，…黍析，k(k<=m-1），其中H(key）為散列函數(shù)屎开，m為散列表長阐枣，di為增量序列，可有下列三種取法：
1.1. di=1,2,3，…蔼两，m-1甩鳄，稱線性探測再散列；
1.2. di=12,-12,22,-22额划，⑶2妙啃，…，±（k)2,(k<=m/2）稱二次探測再散列俊戳；
1.3. di=偽隨機數(shù)序列揖赴，稱偽隨機探測再散列。 - 再散列法：Hi=RHi(key),i=1,2品抽，…储笑，k RHi均是不同的散列函數(shù)，即在同義詞產(chǎn)生地址沖突時計算另一個散列函數(shù)地址圆恤，直到?jīng)_突不再發(fā)生突倍，這種方法不易產(chǎn)生“聚集”，但增加了計算時間盆昙。
- 鏈地址法（拉鏈法）
- 建立一個公共溢出區(qū)
