二叉搜索樹問答題

Question

誰能解釋的答案二進制搜索，

A binary search tree (BST) is built by inserting tree following 
values in the given order: 4,25,15,12,20,70,40. 
The Post Order Traversal will be 
      A. 12, 15, 20, 40,70,25, 4 
      B. 12,20, 15,40, 70,25, 4 
     C. 4,25, 70, 40,15, 12,20 
     D. 4,12, 15, 20, 25,40,70 

我嘗試了答案。但我力求得到它。

Answer 1

向BST插入值時，從根開始。如果該值小於當前節點的值，則轉到左側子樹並進行遞歸，否則轉到右側子樹。如果你最終在一個空的子樹中，在這個地方創建一個節點。

因此，對於給定的順序產生的BST是：

4 
* 
* 25 
    * 15 
    * 12 
     * 
     * 
    * 20 
     * 
     * 
    * 70 
    * 40 
     * 
     * 
    * 

後序遍歷訪問順序左子樹，右子樹，當前節點的節點。

假設(n)描述了遍歷節點n的子樹。然後遍歷是：

(4) 
=() (25) 4 
= (25) 4 
= (15) (70) 25 4 
= (12) (20) 15 (40)() 70 25 4 
= 12 20 15 40 70 25 4