BST - 查找元素數量

有沒有方法可以找到二叉搜索樹中的元素數量？BST - 查找元素數量

struct node 
{ 
    node *p, *left, *right; 
    int key; 
};

這是我的節點的結構，p指針指向父元素。

我需要找到這個數字將用於搜索樹，並傳回所有元素的數組分配內存。

我想出了這樣的事情：

int numberOfElements(node *root, int count = 0) 
{ 
    if(root) 
    { 
     numberOfElements(root->left, ++count); 
     numberOfElements(root->right, ++count); 
    } 
    return count + 1; 
}

但很好，它顯示了一些隨機的結果：P爲「1,2」是顯示器2，對於「1，2，3，4 ，5，6，7「它顯示3等...

我想在一個函數內做到這一點，這就是爲什麼count是一個參數在這裏。

我該怎麼做？

來源

2013-04-20 user2252786

記得按引用次數傳遞。 – stardust 2013-04-20 16:28:21

或保存返回值並將它們相加。 – Detheroc 2013-04-20 16:29:29

你似乎從你的函數中返回一些東西。我想知道這樣的事情可能會有用。如果我們只能調用一個函數，然後以某種方式查看這個值，並且可能將其保存以供將來參考... – 2013-04-20 16:31:02

你不需要第二個參數：

int numberOfElements(node *root) { 
    if (root) { 
     return 1 + numberOfElements(root->left) + numberOfElements(root->right); 
    } else { 
     return 0; 
    } 
}

來源

2013-04-20 16:32:14 NPE

不錯！謝謝：D – user2252786 2013-04-20 16:33:30

你似乎並不在所有使用的numberOfElements返回值。該版本可能工作：

int numberOfElements(node *root) 
{ 
    if(root) 
    { 
     return numberOfElements(root->left) + 
       numberOfElements(root->right) + 1; 
    } 
    return 0; 
}

通常，這種樹的大小應該被記錄在一個領域，你每次修改樹時被更新。沒有人期望O（N）運行時間只是爲了找到一棵樹的大小。

來源

2013-04-20 16:33:37

@seh哦，我的錯，已更新。 – 2013-04-20 16:36:16

BST - 查找元素數量

回答

相關問題