二叉排序树

1.定义 

        二叉排序树（BinarySortTree）定义如下:

二叉排序树或者是一棵空树，或者是具有下列性质的二叉树：
（1）若左子树不空，则左子树上所有结点的值均小于或等于它的根结点的值；
（2）若右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值；
（3）左、右子树也分别为二叉排序树；

由定义可知二叉排序树左子树结点值小于它的根节点值，右子树的值大于它的根节点值。

如图所示。

2.实现

        二叉排序树有3个操作，分别是插入，删除，查找。

        查找:

        步骤：

   首先查找头结点，如果等于要查找的值，则成功找到，返回，如果它的值大于查找的值，递归调用左子树，如果小于查找的值，递归调用右子树。

实现：

首先定义一个二叉树的类:

#二叉链表实现二叉树
class Tree:
    __value=None
    __lChild=None
    __rChild=None
    def __init__(self,value=None):
        self.__value=value
    def get_lChild(self):
        return self.__lChild
    def set_lChild(self,lChild):
        self.__lChild=lChild
    def get_rChild(self):
        return self.__rChild
    def set_rChild(self,rChild):
        self.__rChild=rChild
    def get_value(self):
        return self.__value
    def set_value(self,value):
        self.__value=value

查找方法:

  #查找操作     树的头结点  要查找的键
    def select(self,head,key):
        node=head
        flag=False
        n1=node
        #print(node==head)
        #print(node==None)
        while True:
           if node == None:
               node=n1
               break
           elif node.get_value() == key:
               #print(node.get_value(), key)
               flag=True
               break

           elif key > node.get_value():
               n1 = node
               node = node.get_rChild()

           else:
               # print(2)
               n1 = node
               node = node.get_lChild()
               #self.select(node, key)
        #print(node,'node...')
        return  flag,node

flag表示查找成功或者失败，node表示查找到的结点

插入：

插入方法

插入操作先进行一次查找操作，如果查找成功，说明有相同的值，返回，如果没有成功，返回的结点就是最后要插入结点的父节点。

实现方法：

    def insert(self,key,head=None):
        #node=None
        flag,node=self.select(head,key)#进行一次查找操作  如果没有就插入
        #print(node,'asdad')
        if flag==False:#如果里面没有这个元素
            n=BinarySortTree(key)
            if node==None :
                #print(node, 'node')
                node=n
            elif key>node.get_value():

                node.set_rChild(n)
                #print(node,'node')

            else:
                node.set_lChild(n)
                #node.set_lChild(n)
                #print(node, 'node')
            return  True
        else:
            return False

删除方法:

    删除操作要分情况，因为如直接删除，就会导致树不满足BST的性质。

   首先查找头结点，如果它的值大于查找的值，递归将左子树调用remove方法，如果  小于查找的值，递归右子树调用remove方法。如果左子树和右子树都存在，寻找要删除结点的第一个后继结点（或者前驱）（中序遍历后，结点的前面结点叫前驱结点，后面的叫后继结点），然后将查到结点的值变成后继结点的值，如何对他的后继结点递归进行删除操作。如果只有左子树，将左子树变成要删除结点，如果只有右子树，将右子树变成要删除结点。

实现方法:

    def remove(self,head,key):
        #分为2种情况 当待删除的节点只有左子树或者右子树或者没有孩子节点时   
        if head :#如果有这个元素
            if head.get_value()>key:
                head.set_lChild(self.remove(head.get_lChild(),key))
            elif head.get_value()<key:
                head.set_rChild(self.remove(head.get_rChild(), key))#递归寻找等于key值的节点
            elif head.get_lChild() and head.get_rChild():#如果左子树或者右子树都存在
                #寻找后继节点
                temp=head.get_rChild()
                if temp:
                    while temp.get_lChild():
                        temp=temp.get_lChild()
                #print(head.get_rChild())
                head.set_value(temp.get_value())#将当前要删除结点的值变成后继结点的值
                head.set_rChild(self.remove(head.get_rChild(),temp.get_value()))#对后继结点进行删除
            else:
                
                if head.get_rChild() is None:
                    head= head.get_lChild()
                elif head.get_lChild() is None:
                    head = head.get_rChild()
                #print('c')
        return  head

测试过程

实现一个二叉树的层序遍历来检验:

#层序遍历  二叉树
#定义一个last  为当前最右节点  nlast为当前入队的节点  当last等于nlast时  输入\n  然后last等于nlast
def levelOrder(head):
    queue=Queue()
    queue2= Queue()
    last=head.get_value()

    queue.enQueue(head)
    nlast = head.get_value()
    flag=''
    queue2.enQueue(flag)
    while not( queue.isEmpty()):

         n=queue.deQueue()
         #print(type(n))
         count=n.get_value()
         print(count,queue2.deQueue(),end='\t')

         if n.get_lChild()!=None:
             queue.enQueue(n.get_lChild())
             num = n.get_lChild()
             nlast = num.get_value()
             flag = ('为', n.get_value(),'的左子树')
             queue2.enQueue(flag)
         if n.get_rChild() != None:
             queue.enQueue(n.get_rChild())
             num=n.get_rChild()
             nlast=num.get_value()
             flag = ('为',n.get_value(),'的右子树')
             queue2.enQueue(flag)
             #print('b')
         if last == count:
             print()
             last = nlast

#队列
class Queue:
    _index=-1
    _queue=[]
    #入队方法
    def enQueue(self,value):
        #print(value,'value')
        self._queue.append(value)

        self._index += 1
        #print(self._index, 'index')
        #print(value)

    #出队方法
    def deQueue(self):
        if  not self.isEmpty():

            x=self._queue[0]
            self._queue.pop(0)
            self._index -= 1
            return x
        else:
            return None
    def isEmpty(self):
        if self._index==(-1):
            return True
        return  False
    def queueLast(self):
        if self._index>-1:
            return self._queue[self._index]

输入:

a=BinarySortTree(10)
x=[8,11,4,9,13,5]
for i in x:
    a.insert(i,a)#循环插入
print('层序遍历:')
lo.levelOrder(a)
print('删除5')
a.remove(a,5)#
lo.levelOrder(a)
print('删除10')
a.remove(a,10)#
lo.levelOrder(a)

输出:

层序遍历:
10 	
8 ('为', 10, '的左子树')	11 ('为', 10, '的右子树')	
4 ('为', 8, '的左子树')	9 ('为', 8, '的右子树')	13 ('为', 11, '的右子树')	
5 ('为', 4, '的右子树')	
删除5
10 	
8 ('为', 10, '的左子树')	11 ('为', 10, '的右子树')	
4 ('为', 8, '的左子树')	9 ('为', 8, '的右子树')	13 ('为', 11, '的右子树')	
删除10
11 	
8 ('为', 11, '的左子树')	13 ('为', 11, '的右子树')	
4 ('为', 8, '的左子树')	9 ('为', 8, '的右子树')	

进程已结束,退出代码0

完整版代码:

class BinarySortTree(Tree.Tree):
    #查找操作     树的头结点  要查找的键
    def select(self,head,key):
        node=head
        flag=False
        n1=node
        #print(node==head)
        #print(node==None)
        while True:
           if node == None:
               node=n1
               break
           elif node.get_value() == key:
               #print(node.get_value(), key)
               flag=True
               break

           elif key > node.get_value():
               n1 = node
               node = node.get_rChild()

           else:
               # print(2)
               n1 = node
               node = node.get_lChild()
               #self.select(node, key)
        #print(node,'node...')
        return  flag,node
    def insert(self,key,head=None):
        #node=None
        flag,node=self.select(head,key)#进行一次查找操作  如果没有就插入
        #print(node,'asdad')
        if flag==False:#如果里面没有这个元素
            n=BinarySortTree(key)
            if node==None :
                #print(node, 'node')
                node=n
            elif key>node.get_value():

                node.set_rChild(n)
                #print(node,'node')

            else:
                node.set_lChild(n)
                #node.set_lChild(n)
                #print(node, 'node')
            return  True
        else:
            return False
    def remove(self,head,key):
        #分为2种情况 当待删除的节点只有左子树或者右子树或者没有孩子节点时
        if head :#如果有这个元素
            if head.get_value()>key:
                head.set_lChild(self.remove(head.get_lChild(),key))
            elif head.get_value()<key:
                head.set_rChild(self.remove(head.get_rChild(), key))#递归寻找等于key值的节点
            elif head.get_lChild() and head.get_rChild():#如果左子树或者右子树都存在
                #寻找后继节点
                temp=head.get_rChild()
                if temp:
                    while temp.get_lChild():
                        temp=temp.get_lChild()
                #print(head.get_rChild())
                head.set_value(temp.get_value())#将当前要删除结点的值变成后继结点的值
                head.set_rChild(self.remove(head.get_rChild(),temp.get_value()))#对后继结点进行删除
            else:

                if head.get_rChild() is None:
                    head= head.get_lChild()
                elif head.get_lChild() is None:
                    head = head.get_rChild()
                #print('c')
        return  head