一千萬個為什麽

搜索

歪斜的二叉樹

1)術語不平衡二叉樹是什麽意思以及我們如何編寫算法來測試它?

2)我有一個問題,要求編寫一個函數來測試二叉樹的深度。我認為這會有效但不確定....:

function getDepth(Node n){
    if(node == null){
        return 0;
    }
    return 1 + Math.max(getDepth(node.left), getDepth(node.right));
}
getDepth(root);

任何人都可以給我指點......

最佳答案

1)偏斜的二叉樹不是100%普遍的常用術語(甚至谷歌也會感到困惑)。搜索您的講義或書籍以了解它們的含義。

  1. To test is a tree has as many leves as nodes, you could just use the function you already have that counts levels and another function to count the number of nodes.

    However, you should be abe to make another, more efficient, algorithm that terminates earlier if if finds that the number of nodes cannot be the same as the number of levels.

  2. The depth function is correct. After all, isn't this taken straight from the definition of tree depth?

    (the only possible nitpick is the depth(null) = 1. Just be sure you don't need depth(null) = 0 instead)

轉載註明原文: 歪斜的二叉樹