python数据分析与算法之四 二叉树和排序二叉树

4.1二叉树

• 根节点

• 左叶子节点

• 右叶子节点

• 子树

• 高度

• 广度遍历（层次遍历）

• 深度遍历：

• 前序（根左右）：把根放到最前面　　　　　　

• 中序（左根右）：把根放到中间　　　　　　

• 后序（左右根）：把根放到最后

  class Node():
      def __init__(self,item):
          self.item = item
          self.left = None
          self.right = None
  
  class Tree():
      def __init__(self):    #构造出一个空的二叉树
          self.root = None   #root指向第一个节点的地址,如果root指向为 None,则代表着该二叉树为空
  
      #向二叉树中插入节点
      def addNode(self,item):
          node = Node(item)
          if self.root == None:
              #addNode第一次被调用-->向空树中插入第一个节点,该节点一定是该树的根节点
              self.root = node
              return
          # 如果上述不执行,就意味着该树为非空,下面就执行向一个非空的树中插入节点的操作
          cur = self.root
          queue = [cur]
          while True:
              n = queue.pop(0)
              if n.left != None:
                  queue.append(n.left)
              else:
                  n.left = node
                  break
              if n.right != None:
                  queue.append(n.right)
              else:
                  n.right = node
                  break
  
      def travel(self):
          #如果树为空
          if self.root == None:
              print('空')
              return
          #树为非空
          cur = self.root
          queue = [cur]
          while queue:
              n = queue.pop(0)
              print(n.item)
              if n.left != None:
                  queue.append(n.left)
              if n.right != None:
                  queue.append(n.right)
  
      def forward(self,root):
          if root == None:
              return
          print(root.item)
          self.forward(root.left)
          self.forward(root.right)
          
      def middle(self,root):
          if root == None:
              return
          self.middle(root.left)
          print(root.item)
          self.middle(root.right)
  
      def back(self,root):
          if root == None:
              return
          self.back(root.left)
          self.back(root.right)
          print(root.item)
  
  tree = Tree()
  tree.addNode(1)
  tree.addNode(2)
  tree.addNode(3)
  tree.addNode(4)
  tree.addNode(5)
  tree.addNode(6)
  tree.addNode(7)
  # tree.travel()
  tree.forward(tree.root)
  print('*******************')
  tree.middle(tree.root)
  print('*******************')
  tree.back(tree.root)

4.1.1遍历

1.广度遍历:逐层遍历

    def travel(self):
       #如果数为空
        if self.root == None:
            print('空')
            return
        #树为非空
        cur = self.root
        queue = [cur]
        while queue:
            n = queue.pop(0)
            print(n.item)
            if n.left != None:
                queue.append(n.left)
            if n.right != None:
                queue.append(n.right)

2.深度遍历

前序:根左右

中序:左根右

后序:左右根

4.2排序二叉树

插入节点的时候一定要遵从：比根节点小的节点同一插入在树的左侧，比根节点大的节点同一插在数据的右侧

class Node():
    def __init__(self,item):
        self.item = item
        self.left = None
        self.right = None

class SortTree:
    def __init__(self):
        self.root = None

    def insertNoed(self,item):
        node = Node(item)
        #向空树中插入第一个节点的情况
        if self.root == None:
            self.root = node
            return
        #树为非空的情况
        cur = self.root
        while True:
            if node.item > cur.item:   #向右插
                if cur.right == None:
                    cur.right = node
                    break
                else:
                    cur = cur.right
            else:
                if cur.left == None:
                    cur.left = node
                    break
                else:
                    cur = cur.left

    def middle(self, root):
        if root == None:
            return
        self.middle(root.left)
        print(root.item)
        self.middle(root.right)


tree = SortTree()
tree.insertNoed(3)
tree.insertNoed(8)
tree.insertNoed(15)
tree.middle(tree.root)

4.3二分查找

• 有序列表对于我们的实现搜索是很有用的。在顺序查找中，当我们与第一个元素进行比较时，如果第一个元素不是我们要查找的，则最多还有 n-1 个元素需要进行比较。 二分查找则是从中间元素开始，而不是按顺序查找列表。 如果该元素是我们正在寻找的元素，我们就完成了查找。 如果它不是，我们可以使用列表的有序性质来消除剩余元素的一半。如果我们正在查找的元素大于中间元素，就可以消除中间元素以及比中间元素小的一半元素。如果该元素在列表中，肯定在大的那半部分。然后我们可以用大的半部分重复该过程，继续从中间元素开始，将其与我们正在寻找的内容进行比较。

  def sort(alist,item):       # item:要找的元素
      low = 0                 #二分查找中列表第一个元素的下标
      high = len(alist)-1       #二分查找中列表最后一个元素的下标
      find = False
  
      while low <= high:
          mid = (low+high) // 2 #中间元素的下标
          if item > alist[mid]:#我们要找的数比中间元素值大，则意味着我们要找的数在中间元素的右侧
              low = mid + 1
          elif item < alist[mid]:#找的数比中间元素小，则意味着我们要找的数是在中间元素左侧
              high = mid - 1
          else:#找到啦
              find = True
              break
      return '{}-{}'.format(find,low)
  
  alist = [1,2,3,4,5,6,7]
  print(sort(alist,41))