二叉查找树是一种数据结构,它是具有以下性质的二叉树: 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; }