c++ - 二叉树深度

Question

试图找到二叉搜索树的深度。通过一些谷歌搜索做了一些事情，但我的代码崩溃了:

int treeDepth(int depth) const
        {
            int l = this->left->treeDepth(depth);
            int d = this->right->treeDepth(depth);

            return depth + std::max(l, d);
        }

调用此函数:root->treeDepth(1);

Answer 1

首先，我认为您可能混淆了树的深度和树的高度。引用What is the difference between tree depth and height?寻求解释。

例如，以下是此(二叉)树中节点的深度和高度('0' 是根):

    0     -- depth 0, height 2
   / \
  1   2   -- depth 1, height 1 and 2, respectively, for nodes 1 and 2
 / \
3   4     -- depth 2, height 0

如您所见，树根的深度为“0”，这是 O(1) 计算。然而，树的高度在递归方面更有趣，可以使用以下方法计算:

struct TreeNode {
    T _value;
    typedef TreeNode* node_ptr;    
    node_ptr _left, _right;
};
...
int treeHeight(Node* node)
{
    return std::max(node->_left? 1 + height(node->_left) : 0,
                    node->_right? 1 + height(node->_right) : 0);
}
...
std::cout << treeHeight(root);
...

基本思想是这样的:在递归(深度优先)遍历期间，如果到达叶节点，则返回值“0”(这是每个叶节点的高度)。否则，计算以非叶节点为根的树的高度(即该节点的左子树和右子树的高度的最大值 + 节点本身的 1)。从树的根开始。

我想在您的问题中解决的第二个方面是关于我从您的函数签名中收集到的信息:

int treeDepth(int depth) const

以及您的称呼方式:

root->treeDepth(1);

树的深度不有利于成为根的属性。相反，它是树的一个属性，它由树节点组成，其中一个是 root 节点。因此，我将按如下方式定义类(此处显示的 C++ 结构):

template<class T>
struct BinaryTree {
    struct TreeNode {
        T _value;
        typedef TreeNode* node_ptr;    
        node_ptr _left, _right;
    };
    TreeNode _root_node;
    typedef typename TreeNode::node_ptr node_ptr;
    node_ptr _root;
    ...
    int height(node_ptr node) const;
    ...
};

最后，找到树中给定节点的深度:

int depth(node_ptr node) const;
// returns depth of node if it is in the tree, else -1

是一个你可以应用递归的问题。然而，递归方法并不自然，广度优先(或级别顺序)遍历更适合这种情况。