|
|
二叉排序树又称为二叉查找树它或者是一棵空树，或者是满足以下性质的二叉树
|
|
|
|
（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。
|
|
|
|
点击联系发帖人
