#include?“BSTree.h“

BSTreeNode?*BuyTreeNode（DataType?x）?//創(chuàng)建節(jié)點(diǎn)
{
????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???????????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?????????{
????????????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）?//沒有父親節(jié)點(diǎn)時(shí)
???????????????????*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）?//沒有父親節(jié)點(diǎn)時(shí)
????????????????????*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?????????????tree?=?tree->_right;
????????else?
????????????tree?=?tree->_left;
????}

????return?NULL;
}

void?BSTreeNodeDestory（BSTreeNode?**tree）?//銷毀
{

?屬性????????????大小?????日期????時(shí)間???名稱
-----------?---------??----------?-----??----
?????目錄???????????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