如何从 IPL 函数中获取准确的值？

Question

#include <stdio.h>
#include <stdlib.h>

typedef struct treeNode {
    int key;
    struct treeNode* left;
    struct treeNode* right;
} treeNode;


int count = 0;

treeNode* insertNode(treeNode** t1, int x) {
    if (*t1 == NULL) {
        *t1 = malloc(sizeof(treeNode));
        (*t1)->key = x;
        (*t1)->left = NULL;
        (*t1)->right = NULL;
    }
    else if (x < (*t1)->key) {  //left
        (*t1)->left = insertNode(&(*t1)->left, x);
    }
    else if (x > (*t1)->key) { //right
        (*t1)->right = insertNode(&(*t1)->right, x);
    }
    else {
        printf("SameValue exist.\n");
    }
    return *t1;
}

int getIPL(treeNode* n1) {
    int rightcount;
    int leftcount;
    int rootcount = 1;

    if (n1 != NULL) {
        if (n1->left == NULL && n1->right == NULL) {
            count = rootcount;
        }
        else if (n1->left != NULL && n1->right == NULL) {
            leftcount = 1 + getIPL(n1->left);
            count += leftcount;
        }
        else if (n1->left == NULL && n1->right != NULL) {
            rightcount = 1 + getIPL(n1->right);
            count += rightcount;
        }
        else {
            leftcount = 1 + getIPL(n1->left);
            rightcount = 1 + getIPL(n1->right);
            count += leftcount + rightcount;
        }
    }
    return count;
}


int main() {
    treeNode* T1 = NULL;

    insertNode(&T1, 10);
    insertNode(&T1, 20);
    insertNode(&T1, 3);
    insertNode(&T1, 25);

    printf("IPL : %d", getIPL(T1));
}

此代码用于从 BST 获取内部路径长度 (IPL)。它在 2 级以下正常工作，但在 2 级以上时不起作用。

当放在树10 5 15上时，IPL值为5。

之后，穿上30，会得到9，不是正常值8。

我想要8的IPL值。

请告诉我问题出在哪里。

Answer 1

需要考虑每个节点的深度。例如：

static int getIPL_helper(treeNode *n1, int depth) {
    if (n1) {
        return getIPL_helper(n1->left, depth + 1) +
               getIPL_helper(n1->right, depth + 1) + depth;
    } else {
        return 0;
    }
}

int getIPL(treeNode *n1) {
    return getIPL_helper(n1, 1);
}

如何从 IPL 函数中获取准确的值？

How can I get the exact value from the IPL function?

c

binary-search-tree