Chinaunix首页 | 论坛 | 博客
  • 博客访问: 1023873
  • 博文数量: 164
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 1336
  • 用 户 组: 普通用户
  • 注册时间: 2016-03-11 14:13
个人简介

狂甩酷拽吊炸天

文章分类

全部博文(164)

文章存档

2023年(1)

2022年(3)

2021年(4)

2020年(17)

2019年(37)

2018年(17)

2017年(35)

2016年(50)

分类: LINUX

2018-09-28 19:00:13

二叉排序树又称为二叉查找树。它或者是一颗空树,或者是具有下列性质的二叉树:

  • 若它的左子树不为空,则左子树上所有节点的值均小于它的根结构的值;
  • 若它的右子树不为空,则右子树上所有节点的值均大于它的根结构的值;
  • 它的左、右子树也分别为二叉排序树。
    image_1b2cm8v3mi50141m1vi31v658dh13.png-61.7kB

  • 二叉树的第i层至多有2^{i-1}个结点
  • 深度为k的二叉树至多有2^k-1个结点;
  • 对任何一棵二叉树T,如果其终端结点数为N0,度为2的结点数为N2,则N0=N2+1

二叉排序树的操作:

  1. 查找:对比节点的值和关键字,相等则表明找到了;小了则往节点的左子树去找,大了则往右子树去找,这么递归下去,最后返回布尔值或找到的节点。
  2. 插入:从根节点开始逐个与关键字进行对比,小了去左边,大了去右边,碰到子树为空的情况就将新的节点链接。
  3. 删除:如果要删除的节点是叶子,直接删;如果只有左子树或只有右子树,则删除节点后,将子树链接到父节点即可;如果同时有左右子树,则可以将二叉排序树进行中序遍历,取将要被删除的节点的前驱或者后继节点替代这个被删除的节点的位置。


二叉树遍历分为三种:前序、中序、后序,其中序遍历最为重要。为啥叫这个名字?是根据根节点的顺序命名的。

比如上图正常的一个满节点,A:根节点、B:左节点、C:右节点,前序顺序是ABC(根节点排最先,然后同级先左后右);中序顺序是BAC(先左后根最后右);后序顺序是BCA(先左后右最后根)。

    

比如上图二叉树遍历结果

    前序遍历:ABCDEFGHK

    中序遍历:BDCAEHGKF

    后序遍历:DCBHKGFEA


具体代码如下:

点击(此处)折叠或打开

  1. # -*- coding:utf-8 -*-

  2. import sys

  3. reload(sys)
  4. sys.setdefaultencoding('utf-8')


  5. class BSTNode:
  6.     """
  7.     定义一个二叉树节点类。
  8.     以讨论算法为主,忽略了一些诸如对数据类型进行判断的问题。
  9.     """
  10.     def __init__(self, data, left=None, right=None):
  11.         """
  12.         初始化
  13.         :param data: 节点储存的数据
  14.         :param left: 节点左子树
  15.         :param right: 节点右子树
  16.         """
  17.         self.data = data
  18.         self.left = left
  19.         self.right = right


  20. class BinarySortTree:
  21.     """
  22.     基于BSTNode类的二叉排序树。维护一个根节点的指针。
  23.     """
  24.     def __init__(self):
  25.         self._root = None

  26.     def is_empty(self):
  27.         return self._root is None

  28.     def search(self, key):
  29.         """
  30.         关键码检索
  31.         :param key: 关键码
  32.         :return: 查询节点或None
  33.         """
  34.         bt = self._root
  35.         while bt:
  36.             entry = bt.data
  37.             if key < entry:
  38.                 bt = bt.left
  39.             elif key > entry:
  40.                 bt = bt.right
  41.             else:
  42.                 return entry
  43.         return None

  44.     def insert(self, key):
  45.         """
  46.         插入操作
  47.         :param key:关键码
  48.         :return: 布尔值
  49.         """
  50.         if self.is_empty():
  51.             self._root = BSTNode(key)

  52.         bt = self._root

  53.         while True:
  54.             entry = bt.data

  55.             if key < entry:
  56.                 if bt.left is None:
  57.                     bt.left = BSTNode(key)
  58.                 bt = bt.left
  59.             elif key > entry:
  60.                 if bt.right is None:
  61.                     bt.right = BSTNode(key)
  62.                 bt = bt.right
  63.             else:
  64.                 bt.data = key
  65.                 return

  66.     def delete(self, key):
  67.         """
  68.         二叉排序树最复杂的方法
  69.         :param key: 关键码
  70.         :return: 布尔值
  71.         """
  72.         p, q = None, self._root # 维持p为q的父节点,用于后面的链接操作
  73.         if not q:
  74.             print("空树!")
  75.             return
  76.         while q and q.data != key:
  77.             p = q
  78.             if key < q.data:
  79.                 q = q.left
  80.             else:
  81.                 q = q.right
  82.             if not q: # 当树中没有关键码key时,结束退出。
  83.                 return
  84.         # 上面已将找到了要删除的节点,用q引用。而p则是q的父节点或者None(q为根节点时)。
  85.         if not q.left:
  86.             if p is None:
  87.                 self._root = q.right
  88.             elif q is p.left:
  89.                 p.left = q.right
  90.             else:
  91.                 p.right = q.right
  92.             return
  93.         # 查找节点q的左子树的最右节点,将q的右子树链接为该节点的右子树
  94.         # 该方法可能会增大树的深度,效率并不算高。可以设计其它的方法。
  95.         r = q.left
  96.         while r.right:
  97.             r = r.right
  98.         r.right = q.right
  99.         if p is None:
  100.             self._root = q.left
  101.         elif p.left is q:
  102.             p.left = q.left
  103.         else:
  104.             p.right = q.left

  105.     def _pre_order(self, node=None):

  106.         if node is None:
  107.             node = self._root

  108.         yield node.data

  109.         if node.left is not None:
  110.             for item in self._pre_order(node.left):
  111.                 yield item
  112.         if node.right is not None:
  113.             for item in self._pre_order(node.right):
  114.                 yield item

  115.     def _mid_order(self, node=None):
  116.         if node is None:
  117.             node = self._root

  118.         if node.left is not None:
  119.             for item in self._mid_order(node.left):
  120.                 yield item

  121.         yield node.data

  122.         if node.right is not None:
  123.             for item in self._mid_order(node.right):
  124.                 yield item

  125.     def _mid_order1(self):
  126.         """
  127.         实现二叉树的中序遍历算法,
  128.         展示我们创建的二叉排序树.
  129.         直接使用python内置的列表作为一个栈。
  130.         :return: data
  131.         """
  132.         stack = []
  133.         node = self._root
  134.         while node or stack:
  135.             while node:
  136.                 stack.append(node)
  137.                 node = node.left
  138.             node = stack.pop()
  139.             yield node.data
  140.             node = node.right

  141.     def _post_order(self, node=None):
  142.         if node is None:
  143.             node = self._root

  144.         if node.left is not None:
  145.             for item in self._post_order(node.left):
  146.                 yield item

  147.         if node.right is not None:
  148.             for item in self._post_order(node.right):
  149.                 yield item

  150.         yield node.data

  151.     def pre_order(self):
  152.         return list(self._pre_order())

  153.     def mid_order(self):
  154.         return list(self._mid_order()) # return list(self._mid_order1())

  155.     def post_order(self):
  156.         return list(self._post_order())


  157. if __name__ == '__main__':
  158.     lis = [62, 58, 88, 47, 73, 99, 35, 51, 93, 37]
  159.     bs_tree = BinarySortTree()
  160.     for i in range(len(lis)):
  161.         bs_tree.insert(lis[i])

  162.     print "先序遍历:", bs_tree.pre_order()
  163.     print "中序遍历:", bs_tree.mid_order()
  164.     print "后序遍历:", bs_tree.post_order()





阅读(5568) | 评论(0) | 转发(0) |
0

上一篇:设计模式6大原则

下一篇:MapReduce计数器

给主人留下些什么吧!~~