二叉樹中的樹葉數

我是二叉樹的初學者，一直在通過算法書工作。我已經瞭解了BST的各種遍歷方法（預訂，後期訂單等）。二叉樹中的樹葉數

請問有人能解釋一下如何遍歷一個BST來計算樹葉節點的數量（沒有孩子）嗎？

非常感謝！

來源

2013-10-24 Has

使用遞歸方法：對於葉返回1，對於非葉，返回應用於其子級的該方法的總和。 –

使用您列出的任何遍歷（預先訂購DFS，後期DFS，BFS），並測試您當前訪問的節點是否沒有子節點。如果是這樣，請將計數器增加1. –

謝謝！是否有一個基本的實現，你會推薦PLZ？ – Has

不同遍歷方法會導致不同的算法（儘管對於這樣一個簡單的問題，所有的變體DFS或多或少相同）。

我假設你有一個BST，它由Node類型的對象組成。節點具有類型爲Node的left和right兩個字段，它們是節點的子節點。如果孩子不在場，該字段的值爲null。整棵樹被引用到根，稱爲root。在Java：

class Node { 
    public Node left; 
    public Node right; 
} 

Node root;

甲DFS是最容易通過遞歸來實現：定義一個方法

int numberOfLeafs(Node node)

它返回由node根的子樹的葉子的數量。當然，numberOfLeafs(root)應該產生整棵樹的葉子數量。

至於說，真的是人工在這裏區分會前，會和後序遍歷，但是我會做吧：

預購DFS：先處理當前節點，然後與孩子

int numberOfLeafs(Node node) { 
    int result = 0; 
    if (node.left == null && node.right == null) 
     result += 1; 
    if (node.left != null) 
     result += numberOfLeafs(node.left) 
    if (node.right != null) 
     result += numberOfLeafs(node.right) 
    return result; 
}

按序DFS：先處理左邊的孩子，然後與當前節點，然後用右子

int numberOfLeafs(Node node) { 
    int result = 0; 
    if (node.left != null) 
     result += numberOfLeafs(node.left) 
    if (node.left == null && node.right == null) 
     result += 1; 
    if (node.right != null) 
     result += numberOfLeafs(node.right) 
    return result; 
}

後才能DFS：先處理子女，則與當前節點

int numberOfLeafs(Node node) { 
    int result = 0; 
    if (node.left != null) 
     result += numberOfLeafs(node.left) 
    if (node.right != null) 
     result += numberOfLeafs(node.right) 
    if (node.left == null && node.right == null) 
     result += 1; 
    return result; 
}

對於BFS，通常使用一個簡單的循環，在其中添加一個隊列未訪問的頂點。我現在假設我有一個類Queue來，我可以在年底add節點和從前面take節點：

Queue queue = new Queue(); 
queue.add(root); 
int numberOfLeafs = 0; 
while (!queue.empty) { 
    // take an unhandled node from the queue 
    Node node = queue.take(); 

    if (node.left == null && node.right == null) 
     numberOfLeafs += 1; 
    if (node.left != null) 
     queue.add(node.left); 
    if (node.right != null) 
     queue.add(node.right); 
}

來源

2013-10-24 15:07:35

伴侶！我讀過這麼多書並觀看在線教程。這是迄今爲止我所遇到過的最好的逆轉BST的最好解釋！非常感謝！ – Has

使用遞歸方法：

對於葉回報1.
對於非葉，恢復應用到它的孩子，方法的總和。

實施例在PHP：

class BST { 
    public $left; // The substree containing the smaller entries 
    public $right; // The substree containing the larger entries 
    public $data; // The value that is stored in the node 
} 

function countLeafs(BST $b) { 
    // Test whether children exist ... 
    if ($b->left || $b->right) { 
    // ... yes, the left or the right child exists. It's not a leaf. 
    // Return the sum of calling countLeafs() on all children. 
    return ($b->left ? countLeafs($b->left) : 0) 
     + ($b->right ? countLeafs($b->right) : 0); 
    } else { 
    // ... no, it's a leaf 
    return 1; 
    } 
}

來源

2013-10-24 14:35:42 Oswald

很好措辭;-) +1 –

謝謝你。你已經回答了這個問題。你能不能推薦一個非常基本的實現PLZ？ – Has

非常感謝實施。如果您能用英語解釋您在函數countLeafs（BST $ b）中的做法，我將非常感激！ – Has

試試這個

int countLeafNodes(BTNode node) { 
if (node == null) 
     return 0; 
    if (node.getLeftChild() == null && node.getRightChild() == null 
      && node.getParent() != null)//this is a leaf, no left or right child 
     return 1; 
    else 
     return countLeafNodes(node.getLeftChild()) 
       + countLeafNodes(node.getRightChild()); 
}

該遞歸計數葉節點的左邊和右邊子樹和返回總計數

來源

2013-10-26 05:53:01 Nishant

二叉樹中的樹葉數

回答

相關問題