//删除节点,返回指向修改过的节点的指针

TREE_NODE* deleteNode(TREE_TYPE value, TREE_NODE *tree)

{

    TREE_NODE *tempTree;

    if(tree == NULL){

        //未找到节点

        printf("no found value in tree\n");

        return NULL;

    }else if(tree -> value > value){

        //如果要找的值在左子树中,到左子树中删除，删除节点后，返回节点指针给父节点，然后父节点修正自己的leftPtr或者rightPtr

        tree -> leftPtr = deleteNode(value, tree -> leftPtr);

    }else if(tree -> value < value){

        //如果在右子树中

        tree -> rightPtr = deleteNode(value, tree -> rightPtr);

    }else if(tree -> leftPtr && tree -> rightPtr){

        //找到该节点，且有双子树,先找最大左子树节点

        tempTree = findMaxNode(tree -> leftPtr);

        //替换值即可

        tree -> value = tempTree -> value;

        //然后删除该最大左子树节点,最大左子树只会有一个或者没有子节点，否则不会是最大子节点

        deleteNode(tree -> value, tempTree);

    }else{

        //如果没有子节点，或者有一个子节点,直接用子节点替换，然后删除

        //先保存最大右子树，然后将最大右子树用它的子节点替换，然后删除最大右子树

        tempTree = tree;

        if(tree -> leftPtr == NULL){

            tree = tree -> rightPtr;

        }else if(tree -> rightPtr == NULL){

            tree = tree -> leftPtr;

        }

        free(tempTree);

    }

    return tree;

}

#include <stdio.h>

#include "BinaryTree.h"

int main()

{

    createTree(20);

    insertNode(12);

    insertNode(5);

    insertNode(9);

    insertNode(16);

    insertNode(17);

    insertNode(25);

    insertNode(28);

    insertNode(26);

    insertNode(29);

    TREE_NODE *ptr;

    //删除节点5的父节点值12

    deleteNode(12, root);

    //再次查看5的父节点

    ptr = findParent(5);

    //如果为根节点，没有父节点

    if(ptr == NULL){

        printf("it's root");

    }else{

        printf("%d\n", ptr -> value);

    }

    return 1;

}