二叉查找树的性质
对于任意节点，如果左子树不为空，左子树上所有节点的权值小于该节点的权值
对于任意节点，如果右子树不为空，右子树上所有节点的权值大于该节点的权值
中序遍历是一个有序数列
插入和查找的时间复杂度在理想状况下为O（logn），最坏情况为O（n），其中 n 为树中节点个数
二叉查找树的基本操作
1.结构定义
其本质仍是一颗二叉树，结构与普通二叉树相同。
代码实现：
typedef struct Node { int key; struct Node *lchild, *rchild;}Node;
复制代码
2.创建、销毁
创建与销毁也与普通二叉树相同。
代码实现：
Node *getNewNode(int key) { Node *p = (Node *)malloc(sizeof(Node)); p->key = key; p->lchild = p->rchild = NULL; return p;}
void clear (Node *root) { if (root == NULL) return; clear(root->lchild); clear(root->rchild); free(root); return;}
复制代码
3.插入节点
插入的节点一点会作为叶子节点，同时需保持二叉查找树的性质不变，故需找到正确的插入位置。
代码实现：
/*1.根节点为空则新元素作为根节点，否则将传入参数key与根节点的key比较2.根节点的值与需插入值进行比较，若等于则直接返回，若小于则进行步骤3，大于则进行步骤43.根节点的值小于插入值时，判断当前节点是否存在左孩子，若存在则继续将其左孩子作为参数调用插入方法，不存在则插入为左孩子4.根节点的值大于插入值时，判断当前节点是否存在右孩子，若存在则继续将其右孩子作为参数调用插入方法，不存在则插入为右孩子*/Node *insert(Node *root, int key) { if (root == NULL) return getNewNode(key); if (root->key == key) return root; if (key < root->key) root->lchild = insert(root->lchild, key); else root->rchild = insert(root->rchild, key); return root;}
复制代码
4.查找节点
查找操作与插入类似，先看当前节点，如果找到了就返回，否则与当前节点比较大小，再根据大小情况，递归的查找左右子节点。
代码实现：
/*1.若节点未找到返回0，找到返回12.当前节点是否为空，为空则返回03.当前节点值与查找值比较，相等则返回1，大于则在左子树查找，大于则在右子树查找*/int search (Node *root, int val) { if (root == NULL) return 0; if (root->key == val) return 1; if (root->key > val) return search(root->lchild, val); else return search(root->rchild, val);}
复制代码
5.删除节点
在进行节点删除时，需注意不能改变二叉查找树的基本性质。可分为 3 种情况：
删除节点度为 0；
删除节点度为 1；
删除节点度为 2；
当待删除节点度为 0 时，不会改变树的基本性质，故可直接删除；当删除节点的度为 1 时，将孤儿节点（待删除节点的子节点）挂到待删除节点的父节点即可；当待删除节点度为 2 时，我们找其前驱节点（其左子树中权值最大的节点）或者后继节点（其右子树中权值最小的节点）与其替换后，转换为度为 1 的问题。
代码实现：
Node *predecessor(Node *root) { Node *temp = root->lchild; while (temp->rchild) temp = temp->rchild; return temp;}Node *erase(Node *root, int key) { if (root == NULL) return NULL; if (key < root->key) { root->lchild = erase(root->lchild, key); } else if (key > root->key) { root->rchild = erase(root->rchild, key); } else { if (root->lchild == NULL || root->rchild == NULL) { Node *temp = root->lchild ? root->lchild : root->rchild; free(root); return temp; } else { Node *temp = predecessor(root); root->key = temp->key; root->lchild = erase(root->lchild, temp->key); } } return root;}
复制代码
总结
二叉查找树本质上还是二叉树，只是多了节点的权值大于左子节点的权值、小于右子节点的权值，我们只要在操作它的同时维护好这一基本性质即可。开篇说到，二叉查找树的最优查找时间复杂度为O（logn），最坏情况为O（n），其实这于二叉查找树的树形结构有关，当其各子树分布平衡时其能达到最优时间复杂度，当其分布不均时会退化为链表。这和它的节点插入顺序有关。这听起来很无语，为了解决这一问题，我们有优化其插入对树形结构影响的数据结构，如平衡二叉查找树、红黑树等...
封面： pixabay
评论