内部路径长度函数的问题

Question

有人要求我计算二叉搜索树和 AVL 树中节点的平均深度。通过一些研究，我发现一棵树的平均深度是内部路径长度除以树中的节点数，并且给出内部路径长度（树中每个节点的路径长度之和）通过这次重复：

D(1) = 0, D(N) = D(i) + D(N − i − 1) + N − 1

其中D(N)是一棵有N个节点的树，D(i)是左子树的IPL，D(N-i-1)是右子树的IPL。

使用它，我写了这个函数：

int internalPathLength(Node *t, int& sum) const{
        if(t == nullptr || (t->left == nullptr && t->right == nullptr)) {
            return 0;
        }
        else {
            int a = 0;
            sum += internalPathLength(t->left, sum) + internalPathLength(t->right, sum) + (countNodes(t,a)-1);
            cout << sum << endl;
            return sum;
        }

此函数为我提供了 565 个节点的二叉搜索树、1,264,875,230 的 IPL 和 2,238,717 的平均深度，这是一个高得离谱的数字。在类似大小的 AVL 树上使用它得到了 -1,054,188,525 的 IPL 和 -1,865,820 的平均深度，这是一个负数，而且高得离谱。是不是我的interpretation/implementation的复发有问题？我还能尝试什么？还是我得到的值毕竟在这个计算的正常范围内？

Answer 1

问题是您通过引用传递了 sum，所以它递增了太多次。你根本不需要这笔钱。这应该有效：

int internalPathLength(Node *t) const{
        if(t == nullptr || (t->left == nullptr && t->right == nullptr)) {
            return 0;
        }
        else {
            return internalPathLength(t->left) + internalPathLength(t->right) + countNodes(t) - 1;
        }
    }

这不是最优的，因为您的计数函数可能也是递归的。您可以在同一递归中计算每个子树中的节点，然后使用它。像这样：

int internalPathLength(Node *t, int &count) const{
        if(t == nullptr) {
            count = 0;
            return 0;
        }
        else if(t->left == nullptr && t->right == nullptr){
            count = 1;
            return 0;
        }
        else {
            count = 1;
            int leftCount;
            int rightCount;
            int sum = internalPathLength(t->left, leftCount) + internalPathLength(t->right, rightCount);

            count += leftCount + rightCount;

            return sum + count - 1;
        }
    }

内部路径长度函数的问题

Problems with Internal path length function

c++

tree

binary-search-tree

avl-tree