二叉搜索树
2018-02-25 本文已影响0人
_shen
1.概念
与二叉树相比,二叉搜索树的每个节点左孩子关键字小于等于该节点关键字,右孩子关键字大于等于该节点关键字。即:
node.left.key ≦ node.key ≦ node.right.key
/**
* struct treeNode
* @author liebert
* @member int key 关键字
* @member struct treeNode * parent 父节点
* @member struct treeNode *left 左孩子
* @member struct treeNode *right 右孩子
*/
typedef struct treeNode {
int key;
struct treeNode *parent = NULL;
struct treeNode *left = NULL;
struct treeNode *right = NULL;
} treeNode, *pTreeNode;
2.查找
(1)查找指定关键字节点
/**
* searchTreeNode
* @author liebert
* @param pTreeNode root 待分割数组
* @param int key 关键字
*/
pTreeNode *searchTreeNode(pTreeNode root, k)
{
pTreeNode n = root;
if (n == NULL || k == n.key){
return n;
} else if (k < n.key) {
searchTree(n->left, k);
} else {
searchTree(n->right, k);
}
}
(2)查找最小关键字节点
/**
* searchTreeMaxNode
* @author liebert
* @param pTreeNode root 树根
* @return 最小关键字节点
*/
pTreeNode searchTreeMinNode (pTreeNode root)
{
pTreeNode n = root;
while(n->left != NULL){
n = n->left;
}
return n;
}
(3)查找最大关键字节点
/**
* searchTreeMaxNode
* @author liebert
* @param pTreeNode root 树根
* @return 最大关键字节点
*/
pTreeNode searchTreeMaxNode (pTreeNode root)
{
pTreeNode n = root;
while(n->right != NULL){
n = n->right;
}
return n;
}
2.插入
从树根开始,根据节点关键字值查找其位置,如果树根节点为空,那么当前节点就直接作为树根节点。
/**
* insertTreeNode
* @author liebert
* @param pTreeNode root 树根
* @param pTreeNode node 带插入节点
*/
void insertTreeNode (pTreeNode root, pTreeNode node)
{
pTreeNode temp = root;
pTreeNode ptemp = NULL;
if(root == NULL){
root = node;
return;
}
while (temp != NULL) {
if (temp->key < node->key) {
ptemp = temp;
temp = node->right;
} else {
ptemp = temp;
temp = node->left;
}
}
node->parent = ptemp;
if (ptemp->key < node->key) {
ptemp->left = node;
} else {
ptemp->right = node;
}
}
3.删除
(1)如果要删除的节点A没有孩子节点,那么直接删除A节点即可。
image(2)如果要删除的节点A只有一个孩子B,那么直接将B节点提升到A节点位置即可。
(3)如果要删除的节点A左右两个孩子B、C都在,并且右孩子C的左孩子为空(也就是C节点是以C为根的最小关键字节点),那么将A节点插入到C节点的左孩子位置,然后将C节点提升至A节点位置即可。
(4)如果要删除的节点A左右两个孩子B、C都在,并且右孩子C的左孩子不为空,那么就需要找到以C节点为根的最小关键字节点D,然后以D为树根,将D的父亲节点移至D的右孩子位置,将删除节点A的左孩子B节点移至D的左孩子位置,最后将D移至删除节点A的位置即可。
由于父子节点之间是双向的关系,因此为了维护好这种关系,对于节点的移动操作进行了封装。
移动节点:
void transplant(pTreeNode root, pTreeNode s, pTreeNode d)
{
if (d.parent == NULL) {
root = s;
} else if (d.parent.left == d){
d.parent.left = s;
} else {
d.parent.right = s;
}
s.parent = d.parent;
}
删除节点:
/**
* deleteTreeNode
* @author liebert
* @param pTreeNode root 树根
* @param pTreeNode node 待删除节点
*/
void deleteTreeNode (pTreeNode root, pTreeNode node)
{
pTreeNode minNode;
// 如果node子节点为空
if (node.left == NULL && node.right == NULL) {
if (node.parent.left == node) {
node.parent.left = NULL;
} else {
node.parent.right = NULL;
}
} else if (node.left == NULL) {
transplant(root, node->right, node);
} else if (node.right == NULL) {
transplant(root, node->left, node);
} else {
minNode = searchTreeMinNode(node);
if (minNode.parent != node) {
transplant(root, minNode, minNode->right);
minNode.right = node.right;
minNode.right.parent = minNode;
}
minNode.left = node.left;
minNode.left.parent = minNode;
}
}