二進制搜索樹

我的教授發佈了一些期末考試的複習題。我似乎無法找到答案。任何幫助將不勝感激！二進制搜索樹

考慮n個節點的二叉樹：
a。什麼是葉節點的最小和最大數量？ b。高度的最小值和最大值是多少？
c。樹使用了多少指針（不包括空指針，並假設我們沒有保存存儲父代的字段）？

* d。將n個節點插入（最初爲空）的二叉搜索樹時，最糟糕的關懷運行時間是多少？

來源

2011-05-24 ylhtravis

你應該去和教授交談，看看他是否能夠讓你從這些問題中領悟到你的理解。也許他可以闡明他正在尋找的整體概念。 – 2011-05-24 17:31:57

你知道二叉樹是什麼嗎？如果是這樣，請嘗試將一些數字檢查是否可以找出答案，如n = 3,4等 – 2011-05-24 17:32:04

教授沒有說「平衡二叉樹」，最壞的二叉樹退化爲....布勒？ Bueler？任何人？ – 2011-05-24 17:33:34

葉子的最大數目是ceil（n/2）。最小數量爲1
最大高度爲n。最低限度是樓層（log_2（n））

來源

2011-05-24 17:44:39 arclight

嘗試在紙上繪製各種樹木，看看你得到了什麼。請記住，二叉樹被定義爲一棵樹，其中每個節點可以有0個（在這種情況下，它是一片葉子），1個或2個孩子。對於你的問題，你應該檢查每個節點1個孩子非常不平衡的情況。

來源

2011-05-24 17:31:55

考慮：

如果你想最大限度地提高葉片數，你要儘可能少的內部節點（如果你正在試圖儘量減少葉片數相反）。你怎麼能做到這一點？

要獲得最大高度的樹，您將盡可能少地放置每個級別的節點。你怎麼能這樣做？相反，對於最小高度，您可以在每個級別放置多少個節點？

有多少種方法可以到達樹的每個節點？因此，你需要多少指針？

來源

2011-05-24 17:33:41 William

我假設你要麼在C或C++編碼。

a。一個節點，如果結構是這樣定義的： struct node {struct node * left，* right; }; 您可以觀察到該結構可以具有0,1或2個葉子。所以，最大值是2，最小值是0葉。

b.Minimal高度爲零，其中只包含根節點。請注意，根節點不計爲1的高度。它有時也稱爲深度。下面是高度的算法：

int height(struct node *tree) 
    { 
    if (tree == NULL) return 0; 
    return 1 + max (height (tree->left), height (tree->right)); 
    }

℃。如果我採取這種方式，請原諒我，但是我假設我們是否將它映射在一張紙上，我們會試圖找到我們將使用的「鏈接」的數量？在這種情況下，它僅僅是樹中節點的數量-1作爲根節點。在此頁面http://forums.techarena.in/software-development/1147688.htm上找到的此算法可以幫助您：檢查root是否爲空，然後將左右節點作爲參數傳遞給函數。

int countnodes(Node* root) 
{ 
    if (root == null || k<=0) 
    { 
     return 0; 
    } else { 
     return 1 + count(root.left,k-1) + count(root.right,k-1); 
    } 
} 
// remember to subtract one at the end. 
int totalnodes = countnodes(root) - 1;

d。最佳情況下的時間複雜度爲O（nlogn），其中n是要插入的節點數。最糟糕的情況是O（n）。它是直接線性的。

如果你有任何其他問題只是谷歌它，有很多東西要知道二叉搜索樹。但其中大部分只是遞歸，你可以在30秒內學習。

我希望這會有所幫助。祝您考試順利！幾個月前我有我的。;）

來源

2011-05-24 17:39:56

二進制搜索樹

回答

相關問題