二叉排序树（查找树）

二叉查找树：二叉查找树，也称二叉搜索树，或二叉排序树。其定义也比较简单，要么是一颗空树，要么就是具有如下性质的树：

1 若任意节点的左子树不空，则左子树上所有结点的值均小于它的根结点的值；

2 若任意节点的右子树不空，则右子树上所有结点的值均大于它的根结点的值；

3 任意节点的左、右子树也分别为二叉查找树；

4 没有键值相等的节点。

查找树核心查找：searchBET

相等于二分查找法

bool ErChaTree::serachBET(treeNode* root,int val, treeNode *preRoot, treeNode** end)
{if (!root){*end = preRoot;return false;}else if (root->val == val){*end = root;return true;}else if (root->val < val){return serachBET(root->prChild, val, root, end);}else{return serachBET(root->plChild, val, root, end);}return false;
}

end：找到时，等于当前结点，没有找到时等于父节点

插入操作也很简单

bool ErChaTree::insertNode(int val)
{treeNode* end = NULL;if (!serachBET(m_Root, val, NULL, &end)){treeNode* newNode = new treeNode;newNode->val = val;if (!end){m_Root = newNode;}else if (end->val < val){end->prChild = newNode;}else{end->plChild = newNode;}return true;}else{return false;}
}

当该值不存在时，end等于当前值root结点。

删除操作

bool ErChaTree::deleteBETNode(treeNode** root, int val)
{if (!*root){return false;}else if ((*root)->val == val){deleteNode(root);}else if ((*root)->val < val){return deleteBETNode(&(*root)->prChild,val);}else{return deleteBETNode(&(*root)->plChild, val);}return false;
}bool ErChaTree::deleteNode(treeNode ** node)
{treeNode* pCur;treeNode* pNext;pCur = *node;if (pCur->prChild == NULL){*node = pCur->plChild;delete pCur;}else if (pCur->plChild == NULL){*node = pCur->prChild;delete pCur;}else{pNext = pCur->plChild;while (pNext->prChild){pCur = pNext;pNext = pNext->prChild;}(*node)->val = pNext->val;if (pCur != *node){pCur->prChild = pNext->plChild;}else{pCur->plChild = pNext->plChild;}delete(pNext);}return true;
}

建树容易拆树难

删除结点的时候要考虑到4种情况：

1：删除结点左右子树均为空

2：删除结点左子树为空

3：删除结点右子树为空

4：删除结点左右子树均不为空