二叉查找树
二叉查找树是一种数据结构，它是具有以下性质的二叉树： 1.若左子树不空，则左子树上所有结点的值均小于或等于它的根结点的值； 2.若右子数不空，则右子树上所有结点的值均大于或等于它的根结点的值； 3.左右子树也分别为二叉查找树； 4.等于的情况只能出现在左子树或右子树中的某一侧，一般二叉查找树中无重复节点。 5.二叉查找树的中序遍历从小到大的顺序，故又名二叉排序树。
struct TreeNode{
int val;
TreeNode * left;
TreeNode * right;
TreeNode(int x); val(x), left(NULL),right(NULL){}
};二叉查找树插入节点
将某节点(insert_node),插入至以node为根二叉查找树种： 如果insert_node节点值小于当前node节点值： 1.如果node有左子树，则递归的将该节点插入至左子树为根二叉排序树中 2.否则，将node->left赋值为该节点地址 否则(大于等于情况)： 1.如果node有右子树，则递归的将该节点插入至右子树为根二叉排序树中 2.否则，将node->right赋值为该节点地址
二叉查找树插入节点复杂度为O(h),h为树的高度，若二叉查找树较为平衡，则平均查找复杂度为log（n）
递归实现
void BST_insert(TreeNode *node, TreeNode *insert_node){
if(insert_node->val < node->val ){
if(node->left){
BST_insert(node->left, insert_node);
}
else{
node->left = insert_node;
}
}
else{
if(node->right){
BST_insert(node->right,insert_node);
}
else{
node->right = node_insert;
}
}
}循环实现
void BST_insert(TreeNode *node, TreeNode * insert){
while(node != insert_node){
if(insert_node -> val < node->val){
if( !node->left){
node->left = insert_node;
}
node = node->left;
}
else{
if(!node->rifht){
node->rifht = insert_node;
}
node = node->rifht;
}
}
}二叉查找树查找数值
查找数值value是否在二叉查找树中出现： 如果value等于当前查看node的节点 值:返回True 如果value节点值小于当前node节点值： 1.如果当前节点值有左子树，继续在左子树中查找该值；否则，返回假 否则(value)节点值大于当前node节点值： 如果当前节点值有右子树，继续在右子树中查找该值；否则，返回假
二叉查找树查找数值复杂度为O(h),h为树的高度，若二叉查找树较为平衡，则平均查找复杂度为log（n）
递归实现
bool BST_search(TreeNode * node, int value){
if(node->val == value){
return true;
}
if(value < node-> val){
if(node->left){
return BST_search(node->left, value);
}
else{
return false;
}
}
else{
if(node->right){
return BST_search(node-right, value);
}
else{
return false;
}
}
}循环实现
bool BST_search(*node, value){
while(node){
if(node->val == value){
return true;
}
if(value < node->val){
node = node->left;
}
else{
node = node->right
}
}
return false;
}测试
··· int main(){ TreeNode a(8); TreeNode b(3); TreeNode c(10); TreeNode d(1); TreeNode e(6); TreeNode f(15); a.left = &b; a.rifht = &c; b.left = &d; b.right = &e; c.right = &f; for(int i = 0; i <20; i++){ if(BST_search(&a, i)){ printf("%d is in the BST.\n",i) } else{ printf("%d is not in the BST.\n",i) } } return 0; }
腾讯云开发者
