——搜索二叉树的插入，查找和删除递归&非递归

本代码是在windows平台下vs2008上编译通过，包含搜索二叉树的插入，查找和删除算法（采用递归和非递归两种方法）。包含全部在平台下的文件，解压可以直接运行。

#include “BSTree.h“

BSTreeNode *BuyTreeNode（DataType x） //创建节点
{
    BSTreeNode *node = （BSTreeNode*）malloc（sizeof（BSTreeNode））;
    assert（node）;

    node->_data = x;
    node->_left = NULL;
    node->_right = NULL;

    return node;
}

int BSTreeNodeInsert（BSTreeNode **pptreeDataType x） //搜索树的插入
{
    BSTreeNode *parent = NULL;
    BSTreeNode *cur = *pptree;
    if （*pptree == NULL）
    {
        *pptree = BuyTreeNode（x）;
        return 0;
    }
    while （cur）
    {
      parent = cur;
      if （cur->_data > x）
          cur = cur->_left;
      else if （cur->_data < x）
          cur = cur->_right;
      else
          return -1;
    }

    if （parent->_data > x）
        parent->_left = BuyTreeNode（x）;
    else 
        parent->_right = BuyTreeNode（x）;

    return 0;
}


int BSTreeNodeDel（BSTreeNode **treeDataType x） //删除
{

    BSTreeNode *cur = *tree;
    BSTreeNode *parent = *tree;
    BSTreeNode *del = NULL;
    
    while （cur）
    {
        if （cur->_data > x）
        {
            parent = cur;
            cur = cur->_left;
        }
        else if （cur->_data < x）
        {
            parent = cur;
            cur = cur->_right;
        }
        else
        {
            del = cur;

            if （cur->_left == NULL） //1、左孩子为空
            {
                if （parent->_left == cur）
                    parent->_left = cur->_right;
                else if （parent->_right == cur）
                    parent->_right = cur->_right;
                else if （parent == cur） //没有父亲节点时
                   *tree = parent->_right;
            }
            else if （cur->_right == NULL） //2、右孩子为空
            {
                if （parent->_left == cur）
                    parent->_left = cur->_left;
                else if （parent->_right == cur）
                    parent->_right = cur->_left;
                else if （parent == cur） //没有父亲节点时
                    *tree = parent->_left;
            }
            else//3、左右孩子都不为空
            {
                BSTreeNode *sub = cur->_right;
                while （sub->_left）
                {
                    parent = sub;
                    sub = sub->_left;
                }
                   
                del = sub;
                cur->_data = sub->_data;

                if （parent->_left == sub）
                    parent->_left = sub->_right;
                else 
                    parent->_right = sub->_right;
            }

            free（del）;
            del = NULL;
            return 0;

        }
    }

    return -1;
}

BSTreeNode *BSTreeNodeFind（BSTreeNode *treeDataType x） //查找
{
    while （tree）
    {
        if （tree->_data == x）
            return tree;
        else if （tree->_data < x）
            tree = tree->_right;
        else 
            tree = tree->_left;
    }

    return NULL;
}

void BSTreeNodeDestory（BSTreeNode **tree） //销毁
{

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----
     目录           0  2018-02-26 21:34  SearchBinaryTree\
     目录           0  2018-02-26 21:34  SearchBinaryTree\Debug\
     文件       31232  2018-02-26 20:56  SearchBinaryTree\Debug\SearchBinaryTree.exe
     文件      459916  2018-02-26 20:56  SearchBinaryTree\Debug\SearchBinaryTree.ilk
     文件      412672  2018-02-26 20:56  SearchBinaryTree\Debug\SearchBinaryTree.pdb
     目录           0  2018-02-26 21:34  SearchBinaryTree\SearchBinaryTree\
     文件        4655  2018-02-26 20:56  SearchBinaryTree\SearchBinaryTree\BSTree.c
     文件         795  2018-02-26 15:22  SearchBinaryTree\SearchBinaryTree\BSTree.h
     目录           0  2018-02-26 21:34  SearchBinaryTree\SearchBinaryTree\Debug\
     文件       12227  2018-02-26 20:56  SearchBinaryTree\SearchBinaryTree\Debug\BSTree.obj
     文件        7216  2018-02-26 20:56  SearchBinaryTree\SearchBinaryTree\Debug\BuildLog.htm
     文件         663  2018-02-26 15:01  SearchBinaryTree\SearchBinaryTree\Debug\SearchBinaryTree.exe.embed.manifest
     文件         728  2018-02-26 15:01  SearchBinaryTree\SearchBinaryTree\Debug\SearchBinaryTree.exe.embed.manifest.res
     文件         621  2018-02-26 20:56  SearchBinaryTree\SearchBinaryTree\Debug\SearchBinaryTree.exe.intermediate.manifest
     文件        8994  2018-02-26 20:55  SearchBinaryTree\SearchBinaryTree\Debug\Test.obj
     文件          65  2018-02-26 20:56  SearchBinaryTree\SearchBinaryTree\Debug\mt.dep
     文件       44032  2018-02-26 20:56  SearchBinaryTree\SearchBinaryTree\Debug\vc90.idb
     文件       61440  2018-02-26 20:56  SearchBinaryTree\SearchBinaryTree\Debug\vc90.pdb
     文件        4052  2018-02-26 15:01  SearchBinaryTree\SearchBinaryTree\SearchBinaryTree.vcproj
     文件        1427  2018-02-26 21:32  SearchBinaryTree\SearchBinaryTree\SearchBinaryTree.vcproj.DESKTOP-N4AD0S4.big shot.user
     文件        3011  2018-02-26 20:55  SearchBinaryTree\SearchBinaryTree\Test.c
     文件      396288  2018-02-26 21:32  SearchBinaryTree\SearchBinaryTree.ncb
     文件         914  2018-02-26 12:18  SearchBinaryTree\SearchBinaryTree.sln
     文件       11264  2018-02-26 21:32  SearchBinaryTree\SearchBinaryTree.suo