编程练习——二叉查找树（BinarySearchTree）

BinarySearchTree和BinaryTree其实可以使用相同的构造和析构函数，所以继承吧。懒得再写一遍

template
class BinarySearchTree:public BinaryTree
{
public:
BinarySearchTree(T& data):BinaryTree(data)
{

}

~BinarySearchTree()
{

}
void insertNode(TreeNode* node)
{
insertNode(this->head,node);
}

void insertNode(T& data)
{
TreeNode* newNode = new TreeNode(data);
insertNode(this->head,newNode);
}

void deleteNode(T& data)
{
deleteNode(NULL,this->head,data);
}

TreeNode* searchNode(T& data)
{
return searchNode(this->head,data);
}

private:
TreeNode* insertNode(TreeNode* subTree,TreeNode* node)
{
if(subTree == NULL)
{

subTree = node;
}
else
{

if(subTree->getData() > node->getData())
{
subTree->setLeft(insertNode(subTree->getLeft(),node));

}
else if(subTree->getData() < node->getData())
{
subTree->setRight(insertNode(subTree->getRight(),node));
}
else
{
throw “insert same key”;
}
}
return subTree;
}

TreeNode* searchNode(TreeNode* subTree,T& data)
{
if(subTree == NULL)
{
return NULL;
}
else
{
if(subTree->getData() > data)
{
searchNode(subTree->getLeft(),data);
}
else if(subTree->getData() < data)
{
searchNode(subTree->getRight(),data);
}
else
{
return subTree;
}
}

}

void deleteNode(TreeNode* pSubTree,TreeNode* subTree,T& data)
{
if(subTree == NULL)
{
return ;
}
else
{
if(subTree->getData() > data)
{
deleteNode(subTree,subTree->getLeft(),data);
}
else if(subTree->getData() < data)
{
deleteNode(subTree,subTree->getRight(),data);
}
else
{
TreeNode* assignNode = NULL;
if(subTree->getLeft() == NULL && subTree->getRight() == NULL)
{
// no left, no right

}
else if(subTree->getLeft() == NULL && subTree->getRight() != NULL)
{
// no left child, but has right child
assignNode = subTree->getRight();
}
else if(subTree->getLeft() != NULL && subTree->getRight() == NULL)
{
// no right, has left child
assignNode = subTree->getLeft();
}
else
{
// Or has both right and left child
TreeNode* parent = NULL;
assignNode = getMaxNode(subTree->getLeft(),&parent);
if(parent!= NULL)
{
parent->setRight(NULL);
assert(assignNode!=NULL);
assignNode->setLeft(subTree->getLeft());
}
assignNode->setRight(subTree->getRight());
}
if(pSubTree != NULL)
{

if(pSubTree->getLeft() == subTree)
{
pSubTree->setLeft(assignNode);
}
else
{
pSubTree->setRight(assignNode);
}
}
else
{
this->head = assignNode;
}
delete subTree;
}
}
}

TreeNode* getMaxNode(TreeNode* subTree,TreeNode** pNode)
{
if(subTree == NULL)
{
return NULL;
}
if(subTree->getRight()!= NULL)
{
pNode = &subTree;
return getMaxNode(subTree->getRight(),pNode);
}
else
{

return subTree;
}

}

};

关于二叉查找树，其实插入和查找是一个很简单是事情。只要学会递归遍历，就可以轻松的做到。对于删除操作，删除规则与被删除节点是否有左右孩子节点有关。

1.当无左右节点。直接删除

2.当有右节点无左节点。将此节点删除，并用右节点取代此节点。

3.当有左节点（不管有无右节点）。删除时，将此树中序遍历中该节点的前一个节点代替该节点，再将该节点删除。

所以第3点要做一个寻找该节点中序遍历的前一节点。其实就是该节点左子树中序遍历的最后一个节点，详见getMaxNode()函数。