二叉排序树是树结构的一种特殊形式，它的特征为：
1. 若它的左子树不空，左子树上所有结点的值都小于根结点的值。
2. 若它的右子树不空，右子树上所有结点的值都大于根结点的值。
3. 左右子树也都是二叉排序树。
#include < iostream > #include < vector > using namespace std; // the structure of the node in the binary sort tree typedef struct BTNode ... { int nData; struct BTNode* pLeftChild; struct BTNode* pRightChild;} BTNode; /**/ /** Function Name ：BinarySortTree_Insert* function ：insert a node into the binary sort tree* detail ：none* author ：weixiong* time ：2007-1-26* return type ：BTNode** return description : none* function parameters ：BTNode* pRoot root of this tree* BTNode* pNode pointer of the node you want to insert*/ BTNode * BinarySortTree_Insert(BTNode * pRoot, BTNode * pNode) ... { if (NULL == pRoot) ...{ pRoot = pNode; return pRoot; } BTNode* pCurrent = pRoot; BTNode* pParent = NULL; do ...{ if (pNode->nData <= pCurrent->nData) ...{ pParent = pCurrent; pCurrent = pRoot->pLeftChild; } else ...{ pParent = pCurrent; pCurrent = pRoot->pRightChild; } } while(NULL != pCurrent); if (pParent->nData >= pNode->nData) ...{ pParent->pLeftChild = pNode; } else ...{ pParent->pRightChild = pNode; } return pRoot;} /**/ /** Function Name ：InorderTraveralBinarySortTree* function ：traverse the binary sort tree follow the in_order rule* detail ：none* author ：weixiong* time ：2007-1-26* return type ：void* return description : none* function parameters ：BTNode* pRoot root of this tree*/ void InorderTraveralBinarySortTree(BTNode * pRoot) ... { if (pRoot) ...{ InorderTraveralBinarySortTree(pRoot->pLeftChild); cout << pRoot->nData << " "; InorderTraveralBinarySortTree(pRoot->pRightChild); }} /**/ /** Function Name ：BinarySortTree_Delete* function ：delete node in the binary sort tree(actually i only set the node's pointer null, and maintain the tree. Not delete the node in fact)* detail ：none* author ：weixiong* time ：2007-1-26* return type ：BTNode** return description : root of the new tree* function parameters ：BTNode* pRoot root of this tree* BTNode* pParent parent of the node you intend to delete* BTNOde* pNode node you want to delete*/ BTNode * BinarySortTree_Delete(BTNode * pRoot, BTNode * pParent, BTNode * pNode) ... { //BTNode* pTemp = NULL; //BTNode* pTempParent = NULL; //if (NULL == pNode->pLeftChild) //the node you want to delete doesn't have left child //{ // pTemp = pNode->pRightChild; //} //else if (NULL == pNode->pRightChild) // the node you want to delete doesn't have right child //{ // pTemp = pNode->pLeftChild; //} //else //{ // pTemp = pNode->pLeftChild; // while(NULL != pTemp->pRightChild) // { // pTempParent = pTemp; // pTemp = pTemp->pRightChild; // } // if (NULL != pTemp->pLeftChild) // { // pTempParent = pTemp->pLeftChild; // } //} /**/////pNode is the pointer of the root //if (NULL == pParent) //{ // pTemp->pLeftChild = pRoot->pLeftChild; // pTemp->pRightChild = pRoot->pRightChild; // pTempParent->pRightChild = NULL; // return pTemp; //} //else //{ // if (pParent->pLeftChild == pNode) // { // pTemp->pLeftChild = pNode->pLeftChild; // pTemp->pRightChild = pNode->pRightChild; // pParent->pLeftChild = pTemp; // delete pNode; // } // if (pParent->pRightChild == pNode) // { // pTemp->pLeftChild = pNode->pLeftChild; // pTemp->pRightChild = pNode->pRightChild; // pParent->pRightChild = pTemp;//!!! I even write it as pParent->pRightChild == pTemp, and it spent me a lot of time. // delete pNode; // } //} /**/////delete pNode; //return pRoot; BTNode* pTemp = NULL; BTNode* pPre = NULL; int flag = 0; if (NULL == pNode->pLeftChild)//pNode doesn't have left child ...{ pTemp = pNode->pRightChild; } else if (NULL == pNode->pRightChild)//pNode doesn't have right child ...{ pTemp = pNode->pLeftChild; } else //pNode have right child and left child ...{ pPre = pNode; pTemp = pNode->pLeftChild; while(NULL != pTemp->pRightChild) //search pTemp's rightest child ...{ pPre = pTemp;//pPre records pTemp's parent pTemp = pTemp->pRightChild; } if (pPre == pTemp) ...{ pNode->pLeftChild = pTemp->pLeftChild; pNode->nData = pTemp->nData; } pPre->pRightChild = pTemp->pLeftChild; pNode->nData = pTemp->nData; pTemp = pTemp->pLeftChild = pTemp->pRightChild = 0; //set pTemp and all its pointer to null flag = 1; } if (0 == flag) ...{ if (NULL == pParent) //pNode's parent is the root of the tree ...{ pRoot = pTemp; } else ...{ if (pParent->pLeftChild == pNode) //pNode is pParent's left child ...{ pParent->pLeftChild = pTemp; } else //pNode is pParent's right child ...{ pParent->pRightChild = pTemp; } pNode = pNode->pLeftChild = pNode->pRightChild = NULL;//set pNode and all its pointer to null } } return pRoot;} int main() ... { //all the nodes are allocated by the compiler in stack. When the program terminate, the storage of all these nodes will be free BTNode a = ...{10, NULL, NULL}; BTNode b = ...{3, NULL, NULL}; BTNode c = ...{7, NULL, NULL}; BTNode d = ...{9, NULL, NULL}; BTNode e = ...{17, NULL, NULL}; //push all the nodes in the vector vector<BTNode> BTNodeArray; BTNodeArray.push_back(a); BTNodeArray.push_back(b); BTNodeArray.push_back(c); BTNodeArray.push_back(d); BTNodeArray.push_back(e); BTNode * pRoot = NULL; //insert every node in the binary sort tree vector<BTNode>::iterator i; for (i = BTNodeArray.begin(); i != BTNodeArray.end(); i++) ...{ pRoot = BinarySortTree_Insert(pRoot, &(*i)); } InorderTraveralBinarySortTree(pRoot);//inorder travere the binary sort tree cout << endl; pRoot = BinarySortTree_Delete(pRoot, pRoot->pLeftChild, pRoot->pLeftChild->pRightChild);//delete pRoot->pLeftChild->pRightChild InorderTraveralBinarySortTree(pRoot);//inorder traverse the deleted binary sort tree getchar();}
在写BinarySortTree_Delete()的过程中，发现逻辑结构比较复杂，花了很多的时间理清思路。最后还是在参考别人的代码基础上写成的。
