二叉搜索树无法正常工作，但代码运行良好

Question

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

typedef struct BinSearchTreeNodeType
{
    int key;
    struct BinSearchTreeNodeType *pLeftChild;
    struct BinSearchTreeNodeType *pRightChild;
} BinSearchTreeNode;

typedef struct BinSearchTreeType
{
    BinSearchTreeNode *pRootNode;
} BinSearchTree;

BinSearchTree *createBinSearchTree()
{
    BinSearchTree *pReturn = NULL;
    pReturn = (BinSearchTree *)malloc(sizeof(BinSearchTree));
    if (pReturn != NULL) {
        pReturn->pRootNode = NULL;
    }
    else {
        printf("Error, Memory Allocation, createBinSearchTree()\n");
    }

    return pReturn;
}

BinSearchTreeNode *searchBST(BinSearchTree *pBinSearchTree, int key)
{
    BinSearchTreeNode *pReturn = NULL;
    if (pBinSearchTree == NULL) {
        return NULL;
    }
    pReturn = pBinSearchTree->pRootNode;
    while (pReturn != NULL) {
        if (key == pReturn->key) {
            break;
        }
        else if (key < pReturn->key) {
            pReturn = pReturn->pLeftChild;
        }
        else {
            pReturn = pReturn->pRightChild;
        }
    }
    return pReturn;
}

int getParentNode(BinSearchTreeNode *pCurrentNode, int key, BinSearchTreeNode **ppResult)
{
    int ret = 1;
    BinSearchTreeNode *pParentNode = NULL;

    while (pCurrentNode != NULL) {
        if (key == pCurrentNode->key) {
            printf("Same Key [%d], getParentNode()\n", key);
            ret = 0;
            return ret;
        }
        else if (key < pCurrentNode->key) {
            pParentNode = pCurrentNode;
            pCurrentNode = pCurrentNode->pLeftChild;
        }
        else {
            pParentNode = pCurrentNode;
            pCurrentNode = pCurrentNode->pRightChild;
        }
    }
    if (1 == ret) {
        *ppResult = pParentNode;
    }
    return ret;
}

BinSearchTreeNode *createNewBinSearchTreeNode(int key)
{
    BinSearchTreeNode *pNewNode = NULL;
    pNewNode = (BinSearchTreeNode *)malloc(sizeof(BinSearchTreeNode));
    if (pNewNode != NULL) {
        pNewNode->key = key;
        pNewNode->pLeftChild = NULL;
        pNewNode->pRightChild = NULL;
    }
    return pNewNode;
}

void insertNewBinSearchTreeNode(BinSearchTree *pBinSearchTree, BinSearchTreeNode *pParentNode, BinSearchTreeNode *pNewNode)
{
    if (pParentNode == NULL) {
        pBinSearchTree->pRootNode = pNewNode;
    }
    else {
        if (pNewNode->key < pParentNode->key) {
            pParentNode->pLeftChild = pNewNode;
        }
        else {
            pParentNode->pRightChild = pNewNode;
        }
    }
}

int insertDataBST(BinSearchTree *pBinSearchTree, int key)
{
    int ret = 1;
    BinSearchTreeNode *pParentNode = NULL;
    BinSearchTreeNode *pNewNode = NULL;

    if (pBinSearchTree == NULL) {
        ret = 0;
        return ret;
    }
    ret = getParentNode(pBinSearchTree->pRootNode, key, &pParentNode);
    if (0 == ret) {
        return ret;
    }
    pNewNode = createNewBinSearchTreeNode(key);
    if (NULL == pNewNode) {
        return 0;
    }
    insertNewBinSearchTreeNode(pBinSearchTree, pParentNode, pNewNode);
    return ret;
}

BinSearchTreeNode *searchWithParentNodeBST(BinSearchTree *pBinSearchTree, int key, BinSearchTreeNode **ppParentNode)
{
    BinSearchTreeNode *pReturn = NULL;
    BinSearchTreeNode *pParentNode = NULL;

    if (pBinSearchTree == NULL) {
        return NULL;
    }
    pReturn = pBinSearchTree->pRootNode;
    while (pReturn != NULL) {
        if (key == pReturn->key) {
            break;
        }
        pParentNode = pReturn;
        if (key < pReturn->key) {
            pReturn = pReturn->pLeftChild;
        }
        else {
            pReturn = pReturn->pRightChild;
        }
    }
    if (NULL != ppParentNode) {
        *ppParentNode = pParentNode;
    }

    return pReturn;
}

void deleteNodeNoChild(BinSearchTree *pBinSearchTree, BinSearchTreeNode *pParentNode, BinSearchTreeNode *pDelNode)
{
    if (pParentNode != NULL) {
        if (pParentNode->pLeftChild == pDelNode) {
            pParentNode->pLeftChild = NULL;
        }
        else {
            pParentNode->pRightChild = NULL;
        }
    }
    else {
        pBinSearchTree->pRootNode = NULL;
    }
}

void deleteNodeOneChild(BinSearchTree *pBinSearchTree, BinSearchTreeNode *pParentNode, BinSearchTreeNode *pDelNode)
{
    BinSearchTreeNode *pChildNode = NULL;

    if (pDelNode->pLeftChild != NULL) {
        pChildNode = pDelNode->pLeftChild;
    }
    else {
        pChildNode = pDelNode->pRightChild;
    }

    if (pParentNode != NULL) {
        if (pParentNode->pLeftChild == pDelNode) {
            pParentNode->pLeftChild = pChildNode;
        }
        else {
            pParentNode->pRightChild = pChildNode;
        }
    }
    else {
        pBinSearchTree->pRootNode = pChildNode;
    }
}

void deleteNodeTwoChildren(BinSearchTree* pBinSearchTree, BinSearchTreeNode* pParentNode, BinSearchTreeNode* pDelNode)
{
    BinSearchTreeNode *pPredecessor = NULL, *pSuccessor = NULL;

    pPredecessor = pDelNode;
    pSuccessor = pDelNode->pLeftChild;

    while (pSuccessor->pRightChild != NULL) {
        pPredecessor = pSuccessor;
        pSuccessor = pSuccessor->pRightChild;
    }

    pPredecessor->pRightChild = pSuccessor->pLeftChild;
    pSuccessor->pLeftChild = pDelNode->pLeftChild;
    pSuccessor->pRightChild = pDelNode->pRightChild;

    if (pParentNode != NULL) {
        if (pParentNode->pLeftChild == pDelNode) {
            pParentNode->pLeftChild = pSuccessor;
        }
        else {
            pParentNode->pRightChild = pSuccessor;
        }
    }
    else {
        pBinSearchTree->pRootNode = pSuccessor;
    }
}

int deleteDataBST(BinSearchTree *pBinSearchTree, int key)
{
    int ret = 1;
    BinSearchTreeNode *pDelNode = NULL, *pParentNode = NULL;

    if (pBinSearchTree == NULL) {
        ret = 0;
        return ret;
    }
    pDelNode = searchWithParentNodeBST(pBinSearchTree, key, &pParentNode);
    if (pDelNode == NULL) {
        printf("don't exist [%d], deleteDataBST()\n", key);
        ret = 0;
        return ret;
    }

    if (pDelNode->pLeftChild == NULL && pDelNode->pRightChild == NULL) {
        deleteNodeNoChild(pBinSearchTree, pParentNode, pDelNode);
    }
    else if (pDelNode->pLeftChild != NULL && pDelNode->pRightChild != NULL) {
        deleteNodeTwoChildren(pBinSearchTree, pParentNode, pDelNode);
    }
    else {
        deleteNodeOneChild(pBinSearchTree, pParentNode, pDelNode);
    }

    free(pDelNode);
    return ret;
}

void deleteBinSearchTreeInternal(BinSearchTreeNode *pTreeNode)
{
    if (pTreeNode != NULL) {
        deleteBinSearchTreeInternal(pTreeNode->pLeftChild);
        deleteBinSearchTreeInternal(pTreeNode->pRightChild);
        free(pTreeNode);
    }
}

void deleteBinSearchTree(BinSearchTree *pBinSearchTree)
{
    if (pBinSearchTree != NULL) {
        deleteBinSearchTreeInternal(pBinSearchTree->pRootNode);
        free(pBinSearchTree);
    }
}

void displayBinSearchTree(BinSearchTreeNode *pTreeNode, int array[])
{
    if (pTreeNode == NULL) {
        return;
    }

    else {
        int i = 0;
        if (pTreeNode->pLeftChild != NULL && pTreeNode->pRightChild == NULL) {
            array[i] = pTreeNode->key;
            array[i+1] = pTreeNode->pLeftChild->key;
            i += 2;
        }

        else if (pTreeNode->pLeftChild == NULL && pTreeNode->pRightChild != NULL) {
            array[i] = pTreeNode->key;
            array[i+1] = pTreeNode->pRightChild->key;
            i += 2;
        }

        else if (pTreeNode->pLeftChild != NULL && pTreeNode->pRightChild != NULL) {
            array[i] = pTreeNode->key;
            array[i+1] = pTreeNode->pRightChild->key;
            array[i+1] = pTreeNode->pRightChild->key;
            array[i+1] = pTreeNode->pRightChild->key;
            i += 4;
        }
    }
    displayBinSearchTree(pTreeNode->pLeftChild, array);
    displayBinSearchTree(pTreeNode->pRightChild, array);
}

int main (int argc, char *argv[])
{
    FILE *ip = fopen("C:\VScode\final\hw_input.txt", "r");

    if (ip == NULL) {
        printf("File Open Error");
        return 1;
    }

    char temp[10];
    char *ptemp;

    int buffer[1024];
    int count = 0;

    while (!feof(ip)) {
        ptemp = fgets(temp, 10, ip);
        char *seperate = strtok(ptemp, " ");

        while (seperate != NULL) {
            int num = atoi(seperate);
            seperate = strtok(NULL, " ");
            buffer[count] = num;
            count++;
        }
    }

    int nodeNumber = buffer[0];
    int dataNumber = (nodeNumber*2) - 1;
    int sizeNumber = buffer[dataNumber];

    BinSearchTree *pTree = NULL;
    BinSearchTreeNode *pSearchNode = NULL;
    int key = 0;

    pTree = createBinSearchTree();
    if (pTree != NULL)
    {
        insertDataBST(pTree, buffer[1]);
        for (int i=2; i<dataNumber; i+=2) {
            insertDataBST(pTree, buffer[i]);
        }

        insertDataBST(pTree, buffer[dataNumber+1]);
        for (int j=dataNumber+2; j<count; j+=2) {
            insertDataBST(pTree, buffer[j]);
        }
        fclose(ip);

        int display[1024];
        char displayResult[1024];
        displayBinSearchTree(pTree->pRootNode, display);

        int A = dataNumber;
        int B = ((buffer[dataNumber+1])*2)-1;
        int C = A + B;

        FILE *op = fopen("C:\VScode\final\hw_output.txt", "w");

        for (int i=0; i<C; i++) {
            sprintf(displayResult, "%d %d\n", display[i], display[i+1]);
            char *presult = displayResult;
            fputs(presult, op);
        }

        fclose(op);
        deleteBinSearchTree(pTree);
    }
    return 0;
}

我正在 vscode 中编写代码。代码运行良好，但我无法获得我想要的值。

hw_input.txt 是

我得到的结果是

6 7
0 0
0 0

...它一直只重复零...

我想要的结果是

我的代码哪里出错了？我一直在寻找它，但我几个小时都无法回答，所以我问你一个问题。请给我一些建议。谢谢

Answer 1

我认为它与显示函数中的变量 i 有关，它总是以值 0 开始每次调用请在这样的代码中添加评论

二叉搜索树无法正常工作，但代码运行良好

binary search tree is not working properly, but the code works well

c

tree