Python實(shí)現(xiàn)二叉搜索樹BST的方法示例

更新時(shí)間：2019年07月30日 11:21:27 作者：神不煩

這篇文章主要介紹了Python實(shí)現(xiàn)二叉搜索樹BST的方法示例，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧

二叉排序樹（BST）又稱二叉查找樹、二叉搜索樹

二叉排序樹(Binary Sort Tree)又稱二叉查找樹。它或者是一棵空樹；或者是具有下列性質(zhì)的二叉樹：

1.若左子樹不空，則左子樹上所有結(jié)點(diǎn)的值均小于根結(jié)點(diǎn)的值；
2.若右子樹不空，則右子樹上所有結(jié)點(diǎn)的值均大于根節(jié)點(diǎn)的值；
3.左、右子樹也分別為二叉排序樹。

求樹深度
按序輸出節(jié)點(diǎn)值（使用中序遍歷）
查詢二叉搜索樹中一個(gè)具有給點(diǎn)關(guān)鍵字的結(jié)點(diǎn)，返回該節(jié)點(diǎn)的位置。時(shí)間復(fù)雜度是O(h),h是樹的高度。
遞歸/迭代求最大關(guān)鍵字元素
遞歸/迭代求最小關(guān)鍵字元素

# -*- coding:utf-8 -*-
'''
用Python實(shí)現(xiàn)二叉搜索樹。
'''


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))


#按序輸出結(jié)點(diǎn)值（中序遍歷）
def input_in_order(root):
  if root is None:
    return
  input_in_order(root.left)
  print(root.val)
  input_in_order(root.right)



#（遞歸實(shí)現(xiàn) 、迭代實(shí)現(xiàn)）查詢二叉搜索樹中一個(gè)具有給點(diǎn)關(guān)鍵字的結(jié)點(diǎn)，返回該節(jié)點(diǎn)的位置。時(shí)間復(fù)雜度是O(h),h是樹的高度。
#遞歸實(shí)現(xiàn)
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)


#迭代實(shí)現(xiàn)
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


#求最大關(guān)鍵字元素
#迭代實(shí)現(xiàn)
def max_value1(root):
  while root != None and root.left != None:
    root = root.right
  if root is None:
    return root
  else:
    return root.val

#遞歸實(shí)現(xiàn)
def max_value2(root):
  if root == None:
    return root
  elif root.right == None:
    return root.val
  else:
    return max_value2(root.right)


#求最小關(guān)鍵字元素
#遞歸實(shí)現(xiàn)
def min_value1(root):
  if root is None:
    return root
  elif root.left is None:
    return root.val
  else:
    return min_value1(root.left)


#迭代實(shí)現(xiàn)
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，返回其所在結(jié)點(diǎn)的地址，查找的次數(shù)取決于樹的高度。

以上就是本文的全部內(nèi)容，希望對大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。

您可能感興趣的文章: