Python实现二叉搜索树BST的方法示例

yipeiwu_com5年前Python基础

二叉排序树(BST)又称二叉查找树、二叉搜索树

二叉排序树(Binary Sort Tree)又称二叉查找树。它或者是一棵空树;或者是具有下列性质的二叉树:

1.若左子树不空,则左子树上所有结点的值均小于根结点的值;
2.若右子树不空,则右子树上所有结点的值均大于根节点的值;
3.左、右子树也分别为二叉排序树。

  • 求树深度
  • 按序输出节点值(使用中序遍历)
  • 查询二叉搜索树中一个具有给点关键字的结点,返回该节点的位置。时间复杂度是O(h),h是树的高度。
  • 递归/迭代求最大关键字元素
  • 递归/迭代求最小关键字元素
# -*- coding:utf-8 -*-
'''
用Python实现二叉搜索树。
'''


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

#求树的深度
def depth(root):
    if root is None:
      return 0
    else:
      return 1 + max(depth(root.left), depth(root.right))


#按序输出结点值(中序遍历)
def input_in_order(root):
  if root is None:
    return
  input_in_order(root.left)
  print(root.val)
  input_in_order(root.right)



#(递归实现 、迭代实现)查询二叉搜索树中一个具有给点关键字的结点,返回该节点的位置。时间复杂度是O(h),h是树的高度。
#递归实现
def search1(root, value):
  if root is None or root.val == value:
    return root
  if root.val > value:
    return search1(root.left, value)
  if root.val < value:
    return search1(root.right, value)


#迭代实现
def search2(root, value):
  while root != None and root.val != value:
    if root.val > value:
      root = root.left
    elif root.val < value:
      root = root.right
  return root


#求最大关键字元素
#迭代实现
def max_value1(root):
  while root != None and root.left != None:
    root = root.right
  if root is None:
    return root
  else:
    return root.val

#递归实现
def max_value2(root):
  if root == None:
    return root
  elif root.right == None:
    return root.val
  else:
    return max_value2(root.right)


#求最小关键字元素
#递归实现
def min_value1(root):
  if root is None:
    return root
  elif root.left is None:
    return root.val
  else:
    return min_value1(root.left)


#迭代实现
def min_value2(root):
  if root is None:
    return root
  while root.left !=None:
    root = root.left
  return root.val


if __name__ == '__main__':
  a = Node(15)
  b = Node(6)
  c = Node(18)
  d = Node(4)
  e = Node(8)
  f = Node(17)
  g = Node(20)
  h = Node(13)
  i = Node(9)
  a.left = b
  a.right = c
  b.left = d
  b.right = e
  c.left = f
  c.right = g
  e.right = h
  h.left = i
  print(search1(a, 13))
  print(search2(a,13))
  print(max_value1(a))
  print(max_value2(a))
  print(min_value1(a))
  print(min_value2(a))

ps:从二叉查找树BST中查找元素X,返回其所在结点的地址,查找的次数取决于树的高度。

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持【听图阁-专注于Python设计】。

相关文章

使用PyCharm进行远程开发和调试的实现

使用PyCharm进行远程开发和调试的实现

你是否经常要在Windows 7或MAC OS X上面开发Python或Web应用程序,但是它们最后需要在linux上面来运行呢? 我们经常会碰到开发时没有问题但是到了正式的Linux环...

Python3分析处理声音数据的例子

将音频文件拷贝到程序所在目录即可。 如下所示: #!/usr/bin/env python # encoding: utf-8 """ @Company:华中科技大学电气学院聚变与等...

使用numpy和PIL进行简单的图像处理方法

如下所示: from PIL import Image import numpy as np # 反相 # a = np.array(Image.open("test.jpg"))...

django session完成状态保持的方法

django session完成状态保持的方法

本例使用登录页面演示,session的状态保持功能。 说明:因为http是无状态的,客户端请求一次页面后,就结束了,当再次访问时,服务器端并不知道浏览器此访问过什么。所以这样就需要状态保...

python内置数据类型之列表操作

 数据类型是一种值的集合以及定义在这种值上的一组操作。一切语言的基础都是数据结构,所以打好基础对于后面的学习会有百利而无一害的作用。   python内置的常用数据类型有:数字、字符串...