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

Python  /  管理员 发布于 7年前   262

二叉排序树（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.valif __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，返回其所在结点的地址，查找的次数取决于树的高度。

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持。