樹表查找

樹表查找是對樹型存儲結構所做的查找。樹型存儲結構是一種多鍊表，該表中的每個結點包含有一個數據域和多個指針域，每個指針域指向一個後繼結點。

基本介紹

• 中文名：樹表查找
• 定義：對樹型存儲結構所做的查找
• 使用對象：樹型存儲結構
• 對應邏輯：樹型邏輯結構

定義

樹型存儲結構和樹型邏輯結構是完全對應的，都是表示一個樹形圖，只是用存儲結構中的鏈指針代替邏輯結構中的抽象指針罷了，因此，往往把樹型存儲結構(即樹表)和樹型邏輯結構(樹)統稱為樹結構或樹。在本節中，將分別討論在樹表上進行查找和修改操作的方法。

基本思想

⑴當二叉排序樹不空時，首先將給定值k與根結點的關鍵字進行比較，若相等則查找成功；

⑵若給定值k小於根結點的關鍵字，則下一次與左子樹的根結點的關鍵字進行比較，若給定值k大於根結點的關鍵字，則與右子樹的根接到的關鍵字進行比較。如此遞歸的進行下去直到某一次比較相等，查找成功。如果一直比較到樹葉都不等，則查找失敗。