Python数据结构第二天—循环链表、树、二叉搜索树

双向链表

之前学习的单向链表只能从头遍历到尾，过程是单向的，而双向链表既可以从头遍历到尾，也可以从尾遍历到头，它的过程是双向的。

既然它是双向的，那么我们要实现一个双向链表，就需要在单向链表的基础上，给每一个结点增加一个向前的引用。

双向链表的创建：

"""
我们要实现的是一个双向链表
因此每个结点需要包含三个属性
一个用来指向前一个对象一个用来指向后一个元素
还有一个用来存储对象
"""


class Node:
    def __init__(self, element):
        self.next = None
        self.prev = None
        self.element = element


class DoubleLinkList:
    # 双向链表中需要一个头节点来指向第一个结点对象，同时还需要一个尾结点来指向最后一个元素
    # 同时需要一个length来记录链表的长度
    def __init__(self):
        self.__head = None
        self.__tail = None
        self.__length = 0
        # 向链表末尾添加元素

    def append(self, element):
        # 首先我们要考虑链表是否为空，如果链表为空，直接将node赋值给头节点
        # 如果链表不为空，我们就将node添加到链表的末尾，并将node的prev指向之前链表中的最后一个对象
        # 将之前链表中的最后一个对象的next指向node
        node = Node(element)
        if self.__length == 0:
            self.__head = node
            self.__tail = node
        else:
            # 我们要把当前链表的最后一个元素的next指向node
            # 然后把node的prev指向当前链表的最后一个元素
            # 现在node变成了链表中的最后一个元素了，所有要将node赋值给self.__tail，让它始终都指向链表的末尾
            self.__tail.next = node
            node.prev = self.__tail
            self.__tail = node
        # 最后让链表的长度加1
        self.__length += 1
        # 按位置插入元素

    def insert(self, position, element):
        # 我们该如何考虑呢？
        # 首先我们要想一下一共会出现几种情况
        """
        第一种情况：链表为空的时候，我们只能把元素插入到第一个位置。如果超出了这个第一个位置
        应该报错
        第二种情况，当链表中只有一个元素的时候，要插入到链表第一个位置
        第三种情况：链表不为空但插入的位置是最后一个位置的时候
        第四种情况：链表不为空，但插入的位置在某两个元素之间的时候
        """
        node = Node(element)
        # 首先我们要判断position会不会超出范围，position不能小于0，也不能大于链表的长度
        if position < 0 or position > self.__length:
            return False
        else:
            # 第一种情况
            if self.__length == 0:
                self.__head = node
                self.__tail = node
            # 第二种情况
            elif position == 0:
                self.__head.prev = node
                node.next = self.__head
                self.__head = node

            #第三种情况
            elif position == self.__length:
                self.__tail.next = node
                node.prev = self.__tail
                self.__tail = node
            # 第四种情况
            else:
                # 我们首先要找到我们要插入的位置
                index = 0
                curent = self.__head
                while index < position:
                    curent = curent.next
                    index += 1
                curent.prev.next = node
                node.prev = curent.prev
                node.next = curent
                curent.prev = node
            self.__length += 1
            return True
    def removeAt(self,position):
        """
        我们同样要思考会出现哪些情况
        首先position的值不能超出范围
        在position不超出范围的情况下我们考虑一哪些情况

        """
        if position < 0 or position >= self.__length:
            return False

        current = self.__head
        if position == 0:
            if self.length == 1:
                self.__head = None
                self.__tail = None
            else:
                self.__head = self.__head.next
                self.__head.prev = None
        elif position == self.__length - 1:
            current = self.__tail
            self.__tail = self.__tail.prev
            self.__tail.next = None
        else:
            index = 0
            previous = None
            while index < position:
                previous = current
                current = current.next
                index += 1
            previous.next = current.next
            current.next.prev = previous

        # 3.length-1
        self.__length -= 1
        return current.element

    def indexOf(self, element):
        # 定义变量保存信息
        current = self.__head
        index = 0
        # 查找正确的信息
        while current:
            if current.element == element:
                return index
            index += 1
            current = current.next
        return -1

    def remove(self, element):
        index = self.indexOf(element)
        return self.removeAt(index)
        # 判断是否为空

    def is_empty(self):
        return self.length == 0

        # 获取链表长度

    def size(self):
        return self.length

        # 获取第一个元素

    def getHead(self):
        return self.head.element

        # 获取最后一个元素

    def getTail(self):
        return self.tail.element

树

我们先来看一下树的结构

树的定义:

• 树（Tree）: n（n≥0）个结点构成的有限集合。
  • 当n=0时，称为空树；
  • 对于任一棵非空树（n> 0），它具备以下性质：
  • 树中有一个称为“根（Root）”的特殊结点，用 root 表示；
  • 其余结点可分为m(m>0)个互不相交的有限集T1，T2，… ，Tm，其中每个集合本身又是一棵树，称为原来树的“子树（SubTree）”
• 注意:
  • 子树之间不可以相交
  • 除了根结点外，每个结点有且仅有一个父结点；
  • 一棵N个结点的树有N-1条边。

树的术语:

• 1.结点的度（Degree）：结点的子树个数.
• 2.树的度：树的所有结点中最大的度数. (树的度通常为结点的个数N-1)
• 3.叶结点（Leaf）：度为0的结点. (也称为叶子结点)
• 4.父结点（Parent）：有子树的结点是其子树的根结点的父结点
• 5.子结点（Child）：若A结点是B结点的父结点，则称B结点是A结点的子结点；子结点也称孩子结点。
• 6.兄弟结点（Sibling）：具有同一父结点的各结点彼此是兄弟结点。
• 7.路径和路径长度：从结点n1到nk的路径为一个结点序列n1 , n2,… , nk, ni是 ni+1的父结点。路径所包含边的个数为路径的长度。
• 8.结点的层次（Level）：规定根结点在1层，其它任一结点的层数是其父结点的层数加1。
• 9.树的深度（Depth）：树中所有结点中的最大层次是这棵树的深度。

二叉树

• 二叉树的定义

  • 二叉树可以为空, 也就是没有结点.
  • 若不为空，则它是由根结点和称为其左子树TL和右子树TR的两个不相交的二叉树组成。

• 二叉树有五种形态:

  • 注意c和d是不同的二叉树, 因为二叉树是有左右之分的.

二叉树有几个比较重要的特性, 在笔试题中比较常见:

• 一个二叉树第 i 层的最大结点数为：2^(i-1), i >= 1;

• 深度为k的二叉树有最大结点总数为： 2^k - 1, k >= 1;

• 对任何非空二叉树 T，若n0表示叶结点的个数、n2是度为2的非叶结点个数，那么两者满足关系n0 = n2 + 1

• 完美二叉树(Perfect Binary Tree) , 也称为满二叉树(Full Binary Tree）

  • 在二叉树中, 除了最下一层的叶结点外, 每层节点都有2个子结点, 就构成了满二叉树.

• 完全二叉树(Complete Binary Tree)

  • 除二叉树最后一层外, 其他各层的节点数都达到最大个数.
  • 且最后一层从左向右的叶结点连续存在, 只缺右侧若干节点.
  • 完美二叉树是特殊的完全二叉树.

• 下面不是完全二叉树, 因为D节点还没有右结点, 但是E节点就有了左右节点.

二叉搜索树

• 二叉搜索树（BST，Binary Search Tree），也称二叉排序树或二叉查找树

• 二叉搜索树是一颗二叉树, 可以为空；如果不为空，满足以下性质：

  • 非空左子树的所有键值小于其根结点的键值。
  • 非空右子树的所有键值大于其根结点的键值。
  • 左、右子树本身也都是二叉搜索树。

• 下面哪些是二叉搜索树, 哪些不是?

  

• 二叉搜索树的特点:

  • 二叉搜索树的特点就是相对较小的值总是保存在左结点上, 相对较大的值总是保存在右结点上.
  • 那么利用这个特点, 我们可以做什么事情呢?
  • 查找效率非常高, 这也是二叉搜索树中, 搜索的来源.

二叉搜索树有哪些常见的操作呢?

• insert(key)：向树中插入一个新的键。
• search(key)：在树中查找一个键，如果结点存在，则返回true；如果不存在，则返回false。
• preOrderTraverse：通过先序遍历方式遍历所有结点。
• inOrderTraverse：通过中序遍历方式遍历所有结点。
• postOrderTraverse：通过后序遍历方式遍历所有结点。
• min：返回树中最小的值/键。
• max：返回树中最大的值/键。
• remove(key)：从树中移除某个键。

创建二叉搜索树

• 我们像封装其他数据结构一样, 先来封装一个BinarySearchTree的类

  #创建结点类
  class Node:
   def __init__(self,key):
      self.key = key
      self.left = None
      self.right = None
  
  #创建BinarySearchTree
  class BinarySerachTree:
       def __init__(self):
           self.root = None#保存根的属性
       #二叉搜索树相关的操作方法
       def x1(self):
           pass
       def x2(self):
           pass
  

• 代码解析:

  • 封装BinarySearchTree的类.
  • 还需要封装一个用于保存每一个结点的类Node.
    • 该类包含三个属性: 结点对应的key, 指向的左子树, 指向的右子树
  • 对于BinarySearchTree来说, 只需要保存根结点即可, 因为其他结点都可以通过根结点找到.

向树中插入数据

• 我们两个部分来完成这个功能.

• 外界调用的insert方法

      # 向树中插入数据
      def insert(self, key):
          # 1.根据key创建对应的node
          newNode = Node(key)
          # 2.判断根结点是否有值
          if self.root == None:
              self.root = newNode
          else:
              self.insertNode(self.root, newNode)
  

• 代码解析:

  • 首先, 根据传入的key, 创建对应的Node.
  • 其次, 向树中插入数据需要分成两种情况:
    • 第一次插入, 直接修改根结点即可.
    • 其他次插入, 需要进行相关的比较决定插入的位置.
  • 在代码中的insertNode方法, 我们还没有实现, 也是我们接下来要完成的任务.

• 插入非根结点

   def insertNode(self, node, newNode):
          # 1.准备向左子树插入数据
          if newNode.key < node.key:
              if (node.left == None):
                  # 1.1.node的左子树上没有内容
                  node.left = newNode
              else:
                  # 1.2.node的左子树上已经有了内容
                  self.insertNode(node.left, newNode)
          # 2.准备向右子树插入数据
          else:
              if node.right == None:
                  # 2.1.node的右子树上没有内容
                  node.right = newNode
              else:
                  # 2.2.node的右子树上有内容
                  self.insertNode(node.right, newNode)
  

  #测试代码
  bst = BinarySerachTree()
  
  #插入数据
  bst.insert(11)
  bst.insert(7)
  bst.insert(15)
  bst.insert(5)
  bst.insert(3)
  bst.insert(9)
  bst.insert(8)
  bst.insert(10)
  bst.insert(13)
  bst.insert(12)
  bst.insert(14)
  bst.insert(20)
  bst.insert(18)
  bst.insert(25)
  

• 形成的树:

  

• 如果这个时候, 我新插入一个数据6, 那么插入的位置和顺序应该怎样的呢?

  bst.insert(6)
  

• 新的树:
  

遍历二叉搜索树

• 前面, 我们向树中插入了很多的数据, 为了能很多的看到测试结果. 我们先来学习一下树的遍历.
  • 注意: 这里我们学习的树的遍历, 针对所有的二叉树都是适用的, 不仅仅是二叉搜索树.
• 树的遍历:
  • 遍历一棵树是指访问树的每个结点(也可以对每个结点进行某些操作, 我们这里就是简单的打印)
  • 但是树和线性结构不太一样, 线性结构我们通常按照从前到后的顺序遍历, 但是树呢?
  • 应该从树的顶端还是底端开始呢? 从左开始还是从右开始呢?
  • 二叉树的遍历常见的有三种方式: 先序遍历/中序遍历/后续遍历.

先序遍历

• 遍历过程为：

  • ①访问根结点；
  • ②先遍历其左子树；
  • ③再序遍历其右子树。

• 遍历过程:

  

• 遍历的代码实现

      #先序遍历  
      def preOrderTraversal(self, handler):
          self.preOrderTranversalNode(self.root, handler)
      def preOrderTranversalNode(self, node, handler):
          if node is not None:
              # 1.打印当前经过的节点
              handler(node.key)
              # 2.遍历所有的左子树
              self.preOrderTranversalNode(node.left, handler)
              # 3.遍历所有的右子树
              self.preOrderTranversalNode(node.right, handler)
  

• 测试代码:

  #测试前序遍历结果
  bst.preOrderTraversal(lambda key: print(key,end=" "))
  #11 7 5 3 6 9 8 10 15 13 12 14 20 18 25
  

• 代码解析:

  • 遍历树最好用的办法就是递归, 因为每个节点都可能有自己的子节点, 所以递归调用是最好的方式.
  • 在先序遍历中, 我们在经过节点的时候, 会先将该节点打印出来.
  • 然后, 我们会遍历节点的左子树, 再然后遍历节点的右子树.

• 代码先序遍历图解:

  

中序遍历

• 遍历过程为:

  • ①中序遍历其左子树；
  • ②访问根结点；
  • ③中序遍历其右子树。

• 遍历过程:

  

• 遍历的代码实现:

      #中序遍历
      def inOrderTraversal(self, handler):
          self.inOrderTraversalNode(self.root, handler)
      def inOrderTraversalNode(self, node, handler):
          if node is not None:
              # 1.遍历所有的左子树
              self.inOrderTraversalNode(node.left, handler)
              # 2.打印当前经过的节点
              handler(node.key)
              # 3.遍历所有的右子树
              self.inOrderTraversalNode(node.right, handler)
  

• 测试代码:

  #测试中序遍历结果
  bst.inOrderTraversal(lambda key: print(key,end=" "))
  #3 5 6 7 8 9 10 11 12 13 14 15 18 20 25
  

• 代码解析:

  • 先从最左边开始, 进行中序遍历.
  • 依次向右移动, 最后遍历最右边.
  • 可以根据代码和图片解析来查看. (这里不太好描述, 但是一图胜千言, 大家多看一下图片)

• 代码中序遍历图解:

  

后序遍历

• 遍历过程为：

  • ①后序遍历其左子树；
  • ②后序遍历其右子树；
  • ③访问根结点。

• 遍历过程:

  

• 遍历的代码实现:

      #后续遍历
      def postOrderTraversal(self, handler):
          self.postOrderTraversalNode(self.root, handler)
      def postOrderTraversalNode(self, node, handler):
          if node is not None:
              # 1.遍历所有的左子树
              self.postOrderTraversalNode(node.left, handler)
              # 2.遍历所有的右子树
              self.postOrderTraversalNode(node.right, handler)
              # 3.打印当前经过的节点
              handler(node.key)
  
  

• 测试代码:

  #测试后续遍历结果
  bst.inOrderTraversal(lambda key: print(key,end=" "))
  #3 6 5 8 10 9 7 12 14 13 18 25 20 15 11 
  

• 后续遍历

  • 先遍历左子树上的节点, 再遍历右子树上的节点, 最后遍历根节点. (仔细查看图片和代码)

• 代码后续遍历图解:

  

最大值&最小值

• 在二叉搜索树中搜索最值是一件非常简单的事情, 其实用眼睛看就可以看出来了.

  

• 下面, 我们通过代码来实现一下.

• 获取最大值&最小值:

      #获取最小值
      def min(self):
          node = self.root
          while node.left is not None:
              node = node.left
          return node.key
  
      # 获取最大值
      def max(self):
          node = self.root
          while node.right is not None:
              node = node.right
          return node.key
  

• 代码解析:

  • 代码也是比较简单的:
    • 代码依次向左找到最左边的结点就是最小值,
    • 代码依次向右找到最右边的结点就是最大值.
  • 也可以使用递归来实现, 不过这里就没有什么必要了, 递归反而增加代码的复杂度.

• 代码测试:

  print(bst.min())#3
  print(bst.max())#25
  

搜索特定的值

• 二叉搜索树不仅仅获取最值效率非常高, 搜索特定的值效率也非常高.

      #搜索特定的值
      def search(self,key):
          return self.searchNode(self.root, key)
      def searchNode(self,node, key):
          # 1.如果传入的node为None那么, 那么就退出递归
          if node is None:
              return False
          # 2.判断node节点的值和传入的key大小
          if node.key>key:#2.1.传入的key较小, 向左边继续查找
              return self.searchNode(node.left, key)
          elif node.key < key:#2.2.传入的key较大, 向右边继续查找
              return self.searchNode(node.right, key)
          else:#2.3.相同, 说明找到了key
              return True
  

• 代码解析:

  • 这里我们还是使用了递归的方式. 待会儿我们来写一个非递归的实现.
  • 递归必须有退出条件, 我们这里是两种情况下退出.
    • node === None, 也就是后面不再有节点的时候.
    • 找到对应的key, 也就是node.key === key的时候.
  • 在其他情况下, 根据node.的key和传入的key进行比较来决定向左还是向右查找.
    • 如果node.key > key, 那么说明传入的值更小, 需要向左查找.
    • 如果node.key < key, 那么说明传入的值更大, 需要向右查找.

• 测试代码:

  #查找特定的值
  print(bst.search(25))#True
  print(bst.search(100))#False
  

• 非递归代码实现:

  def search(key): 
      node = self.root
      while node != None: 
          if node.key > key: 
              node = node.left
          elif node.key < key: 
              node = node.right
          else: 
              return True
      return False
  

• 递归or循环?

  • 其实递归和循环之间可以相互转换.
  • 大多数情况下, 递归调用可以简化代码, 但是也会增加空间的复杂度.
  • 循环空间复杂度较低, 但是代码会相对复杂.
  • 可以根据实际的情况自行选择, 不需要套死必须使用某种方式.

二叉搜索树的删除

删除节点的思路

• 删除节点要从查找要删的节点开始, 找到节点后, 需要考虑三种情况:

  • 该节点是叶结点(没有子节点, 比较简单) 没有子节点的根节点
  • 该节点有一个子节点(也相对简单)
  • 该节点有两个子节点.(情况比较复杂, 我们后面慢慢道来)

• 我们先从查找要删除的节点入手

      # 删除结点
      def remove(self, key):
          # 1.定义临时保存的变量
          current = self.root
          parent = None
          isLeftChild = True
  
          # 2.开始查找节点
          while current.key != key:
              parent = current
              if key < current.key:
                  isLeftChild = True
                  current = current.left
              else:
                  isLeftChild = False
                  current = current.right
              # 如果发现current已经指向None, 那么说明没有找到要删除的数据
              if current is None:
                  return False
          
          #3.找到了开始删除
          #4.删除完毕返回True     
          return True
  

• 代码解析:

  • 在上面的代码序号1位置中, 我们先保存了一些临时变量.
    • current: 用于一会儿找到的要删除的节点对应的node.
    • parent: 用于保存current节点的父节点. 因为如果current有子节点, 那么在删除current节点的时候, 必然需要将parent的left或者right指向它的某一个子节点. 所以需要保存起来current的parent. (树中的节点关系不能向上的, 和链表非常相似)
    • isLeftChild: boolean类型,它用户记录我们是在current是在父节点的左侧还是右侧, 以便到时候设置parent的left或者right
  • 在上面的代码序号2位置中, 开始查找对应的key.
    • 还是之前的思路, 依次向下找到节点, 同时记录current/parent/isLeftChild这些变量
    • 如果遍历到current === None, 那么说明在二叉搜索树中没有该key, 直接返回false即可.
    • 如果找到, 后面就需要我们进一步考虑更加复杂的情况了.

情况一: 没有子节点

• 情况一: 没有子节点.

  • 这种情况相对比较简单, 我们需要检测current的left以及right是否都为None.
  • 都为None之后还要检测一个东西, 就是是否current就是根, 都为None, 并且为跟根, 那么相当于要清空二叉树(当然, 只是清空了根, 因为只有它).
  • 否则就把父节点的left或者right字段设置为None即可.

• 图解过程:

  • 如果只有一个单独的根, 直接删除即可

  • 如果是叶结点, 那么处理方式如下:

• 代码实现如下:

          #3.1删除的结点是叶结点
          if current.left is None and current.right is None:
              if current == self.root:
                  self.root = None
              elif isLeftChild:
                  parent.left = None
              else:
                  parent.right = None
  

• 代码解析:

  • 首先, 判断是否是叶结点. 通过current的left&right是否为None
  • 上面条件成立, 再判断current是否是根结点: 回答是, 那么就将self.root = None即可.
  • 如果不是根, 再判断是左结点, 还是右结点, 以便于将parent的left或者right设置为None

情况二: 一个子节点

• 情况二: 有一个子节点

  • 这种情况也不是很难.
  • 要删除的current结点, 只有2个连接(如果有两个子结点, 就是三个连接了), 一个连接父节点, 一个连接唯一的子节点.
  • 需要从这三者之间: 爷爷 - 自己 - 儿子, 将自己(current)剪短, 让爷爷直接连接儿子即可.
  • 这个过程要求改变父节点的left或者right, 指向要删除节点的子节点.
  • 当然, 在这个过程中还要考虑是否current就是根.

• 图解过程:

  • 如果是根的情况, 大家可以自己画一下, 比较简单, 这里不再给出.
  • 如果不是根, 并且只有一个子节点的情况.

• 代码实现如下:

          # 3.2删除有一个子节点的节点
          elif current.right is None:
              if current == self.root:
                  self.root = current.left
              elif isLeftChild:
                  parent.left = current.left
              else:
                  parent.right = current.left
          elif current.left is None:
              if current == self.root:
                  self.root = current.right
              elif isLeftChild:
                  parent.left = current.right
              else:
                  parent.right = current.right
  

• 代码解析:

  • 首先, 我们需要判断是current的left还是right为None. 因为这样才能决定, 只有我们从current中取儿子的时候, 取的是current.left还是current.right来给别的地方赋值.
  • 三种情况:
    • current是根节点, 那么直接将self.root = son.
    • current不是根节点, 是父节点的left节点, 那么parent.left = son.
    • current不是根节点, 是父节点的right节点, 那么parent.right = son.

情况三: 两个子节点

• 情况三: 有两个子节点.

  • 事情变得非常复杂, 也非常有趣了.

• 我们先来思考一下我提出的一些问题:

  

• 先来, 我们来总结一下删除有两个子节点的规律:

  • 如果我们要删除的节点有两个子节点, 甚至子节点还有子节点, 这种情况下我们需要从下面的子节点中找到一个节点, 来替换当前的节点.
  • 但是找到的这个节点有什么特征呢? 应该是current节点下面所有节点中最接近current节点的.
    • 要么比current节点小一点点, 要么比current节点大一点点.
    • 总结谁最接近current, 谁就可以用来替换current的位置.
  • 这个节点怎么找呢?
    • 比current小一点点的节点, 一定是current左子树的最大值.
    • 比current大一点点的节点, 一定是current右子树的最小值.
  • 前驱&后继
    • 而在二叉搜索树中, 这两个特别的节点, 有两个特别的名字.
    • 比current小一点点的节点, 称为current节点的前驱.
    • 比current大一点点的节点, 称为current节点的后继.
  • 也就是为了能够删除有两个子节点的current, 要么找到它的前驱, 要么找到它的后继.
  • 所以, 接下来, 我们先找到这样的节点(前驱或者后继都可以, 我这里以找后继为例)

• 代码实现:

      # 找后继的方法
      def getSuccessor(self, delNode):
          # 1.使用变量保存临时的节点
          successorParent = delNode
          successor = delNode
          current = delNode.right  # 要从右子树开始找
          # 2.寻找节点
          while current is not None:
              successorParent = successor#while循环完毕-后继的父节点
              successor = current#while循环完毕-要删除的节点的右子树种最left节点:后继
              current = current.left#while循环完毕-None
          # 3.如果是删除图中15的情况, 还需要如下代码
          if successor != delNode.right:
              successorParent.left = successor.right
              successor.right = delNode.right
          return successor
  

• 找到后继后的处理代码:

          # 3.3删除有两个子节点的节点
          else:
              # 3.3.1.获取后继节点
              successor = self.getSuccessor(current)
              # 3.3.2. 判断是否是根节点
              if current == self.root:
                  self.root = successor
              elif isLeftChild:
                  parent.left = successor
              else:
                  parent.right = successor
              # 3.3.3.将删除节点的左子树赋值给successor
              successor.left = current.left
  

• 代码解析:

  • 1: 调用刚才封装的方法, 获取后继节点.
  • 2: 判断三种情况:
    • 情况一: 是根节点, 那么self.root = successor. 并且successor的left应该等于current的left
    • 情况二: 是父节点的左结点, parent.left = successor, 并且successor的left应该等于current的left
    • 情况三: 是父节点的右结点, parent.right = successor, 并且successor的left应该等于current的left
  • 3: 就是将successor.left = current.left从判断中抽取出来.

• 回头头看TODO的情况

  • 上面的代码实现, 对于删除9是适用的. 做法就是将7节点的left 赋值为 10. 10节点的left应该赋值为8即可.
  • 但是, 对于删除15我们还缺少什么呢?
    • 已经完成: 11的left指向了18, 18的right指向了13.
    • 没有完成: 19怎么办? 20这个左子树怎么办?
    • 很明显, 19应该放在20的左边, 20应该放在18的右边.
    • 19放在20的左边代码: successorParent.left = successor.right
    • 20放在18的右边代码: successor.right = delNode.right
  • 搞定, 收工!!!

删除节点完整代码

    # 找后继的方法
    def getSuccessor(self, delNode):
        # 1.使用变量保存临时的节点
        successorParent = delNode
        successor = delNode
        current = delNode.right  # 要从右子树开始找
        # 2.寻找节点
        while current is not None:
            successorParent = successor
            successor = current
            current = current.left
        # 3.如果是删除图中15的情况, 还需要如下代码
        if successor != delNode.right:
            successorParent.left = successor.right
            successor.right = delNode.right
        return successor

    # 删除结点
    def remove(self, key):
        # 1.定义临时保存的变量
        current = self.root
        parent = None
        isLeftChild = True

        # 2.开始查找节点
        while current.key != key:
            parent = current
            if key < current.key:
                isLeftChild = True
                current = current.left
            else:
                isLeftChild = False
                current = current.right
            # 如果发现current已经指向None, 那么说明没有找到要删除的数据
            if current is None:
                return False
        # 3.找到了开始删除
        # 3.1删除的结点是叶结点
        if current.left is None and current.right is None:
            if current == self.root:
                self.root = None
            elif isLeftChild:
                parent.left = None
            else:
                parent.right = None
        # 3.2删除有一个子节点的节点
        elif current.right is None:
            if current == self.root:
                self.root = current.left
            elif isLeftChild:
                parent.left = current.left
            else:
                parent.right = current.left
        elif current.left is None:
            if current == self.root:
                self.root = current.right
            elif isLeftChild:
                parent.left = current.right
            else:
                parent.right = current.right

        # 3.3删除有两个子节点的节点
        else:
            # 3.3.1.获取后继节点
            successor = self.getSuccessor(current)
            # 3.3.2. 判断是否是根节点
            if current == self.root:
                self.root = successor
            elif isLeftChild:
                parent.left = successor
            else:
                parent.right = successor
            # 3.3.3.将删除节点的左子树赋值给successor
            successor.left = current.left

删除节点的回顾

• 看到这里, 你就会发现删除节点相当棘手.
• 实际上, 因为它非常复杂, 一些程序员都尝试着避开删除操作.
  • 他们的做法是在Node类中添加一个boolean的字段, 比如名称为isDeleted.
  • 要删除一个节点时, 就将此字段设置为true.
  • 在查找之前先判断这个节点是不是标记为删除.
  • 这样相对比较简单, 每次删除节点不会改变原有的树结构.
  • 但是在二叉树的存储中, 还保留着那些本该已经被删除掉的节点.
• 上面的做法看起来很聪明, 其实是一种逃避.

  • 这样会造成很大空间的浪费, 特别是针对数据量较大的情况.

  • 而且, 作为程序员要学会通过这些复杂的操作, 锻炼自己的逻辑, 而不是避重就轻.

           parent.left = current.right
        else:
            parent.right = current.right
    
    # 3.3删除有两个子节点的节点
    else:
        # 3.3.1.获取后继节点
        successor = self.getSuccessor(current)
        # 3.3.2. 判断是否是根节点
        if current == self.root:
            self.root = successor
        elif isLeftChild:
            parent.left = successor
        else:
            parent.right = successor
        # 3.3.3.将删除节点的左子树赋值给successor
        successor.left = current.left
    

**删除节点的回顾**

- 看到这里, 你就会发现删除节点相当棘手.
- 实际上, 因为它非常复杂, 一些程序员都尝试着避开删除操作. 
  - 他们的做法是在Node类中添加一个boolean的字段, 比如名称为isDeleted.
  - 要删除一个节点时, 就将此字段设置为true.
  - 在查找之前先判断这个节点是不是标记为删除.
  - 这样相对比较简单, 每次删除节点不会改变原有的树结构.
  - 但是在二叉树的存储中, 还保留着那些本该已经被删除掉的节点.
- 上面的做法看起来很聪明, 其实是一种逃避. 
  - 这样会造成很大空间的浪费, 特别是针对数据量较大的情况.
  - 而且, 作为程序员要学会通过这些复杂的操作, 锻炼自己的逻辑, 而不是避重就轻.