|
|
|
二叉排序树又称为二叉查找树，它或者是一棵空树，或者是满足以下性质的二叉树。
|
|
|
|
（1）若它的左子树非空，则左子树上所有节点的值均小于根节点的值。
|
|
|
|
（2）若它的右子树非空，则右子树上所有节点的值均大于根节点的值。
|
|
|
|
|
|
二叉排序树的查找过程是：若二叉排序树非空，则将给定值与根节点的关键字值相比较，若相等，则查找成功；若不等，则当根节点的关键字值大于给定值时，到根的左子树中进行查找；否则到根的右子树中进行查找。若找到，则查找过程是走了一条从树根到所找到节点的路径；否则查找过程终止于一棵空树。
|
|
|
|
二叉排序树中插入节点的操作：每读入一个元素，建立一个新节点，若二叉树非空，则将新节点的值与根节点的值相比较，如果小于根节点的值，则插入到左子树中，否则插入到右子树中；若二叉排序树为空，则新节点作为二叉排序树的根节点。
|
|
|
|
二叉排序树中删除节点的操作：在二叉树中删除一个节点，不能把以该节点为根的子树都删除，只能删除这个节点并仍旧保持二叉排序树的特性，也就是说，删除二叉排序树上一个节点相当于删除有序数列中的一个元素。假设二叉排序树上的被删除节点为*p（p指针指向被删除节点），*f为其双亲节点，则删除节点*p的过程可分为以下3种情况。
|
|
|
|
①若*p节点为叶子节点，即p→lchild及p→rchild均为空，则由于删去叶子节点后不破坏整棵树的结构，因此只需修改*p节点的双亲节点*f的相应指针即可，即f→lchild（或f→rchild）=NULL。
|
|
|
|
②若*p节点只有左子树或者只有右子树，此时只要将*p的左子树或右子树接成其双亲节点*f左子树或右子树，即令f→lchild（或f→rchild）=p→lchild，或f→lchild（或f→rchild）=p→rchild。
|
|
|
|
③若*p节点的左、右子树均不空，则不能像上面那样简单处理，删除*p节点时应将*p的左子树、右子树连接到适当的位置，并保持二叉排序树的特性。可采用以下两种方法进行处理：一是令*p的左子树为*f的左（或右）子树，而将*p的右子树下接到*p的中序遍历的直接前驱节点*s的右孩子指针上；二是用*p的中序直接前驱（或后继）节点*s代替*p节点，然后删除*s节点。
|
|
|
