Python实现二叉搜索树的方法

二叉搜索树(二叉排序树)它的每个节点的数据结构为1个父节点指针,1个左孩子指针,1个有孩子指针,还有就是自己的数据部分了,因为只有左右两孩子,所以才叫二叉树,在此基础上,该二叉树还满足另外一个条件:每个结点的左孩子都不大于该结点&&每个结点的右孩子都大于该结点.

class BinarySearchTree:

  def init(self):
    self.root = None
    self.size = 0

  def length(self):
    return self.size

  def len(self):
    return self.size

  def iter(self):
    return self.root.iter() 

class TreeNode:
  def init(self,key,val,left=None,right=None,
                    parent=None):
    self.key = key
    self.payload = val
    self.leftChild = left
    self.rightChild = right
    self.parent = parent

  def hasLeftChild(self):
    return self.leftChild

  def hasRightChild(self):
    return self.rightChild

  def isLeftChild(self):
    return self.parent and self.parent.leftChild == self

  def isRightChild(self):
    return self.parent and self.parent.rightChild == self

  def isRoot(self):
    return not self.parent

  def isLeaf(self):
    return not (self.rightChild or self.leftChild)

  def hasAnyChildren(self):
    return self.rightChild or self.leftChild

  def hasBothChildren(self):
    return self.rightChild and self.leftChild

  def replaceNodeData(self,key,value,lc,rc):
    self.key = key
    self.payload = value
    self.leftChild = lc
    self.rightChild = rc
    if self.hasLeftChild():
      self.leftChild.parent = self
    if self.hasRightChild():
      self.rightChild.parent = self 

def put(self,key,val):
  if self.root:
    self._put(key,val,self.root)
  else:
    self.root = TreeNode(key,val)
  self.size = self.size + 1

def _put(self,key,val,currentNode):
  if key < currentNode.key:
    if currentNode.hasLeftChild():
        self._put(key,val,currentNode.leftChild)
    else:
        currentNode.leftChild = TreeNode(key,val,parent=currentNode)
  else:
    if currentNode.hasRightChild():
        self._put(key,val,currentNode.rightChild)
    else:
        currentNode.rightChild = TreeNode(key,val,parent=currentNode) 

def setitem(self,k,v):
  self.put(k,v) 

def get(self,key):
  if self.root:
    res = self._get(key,self.root)
    if res:
        return res.payload
    else:
        return None
  else:
    return None

def _get(self,key,currentNode):
  if not currentNode:
    return None
  elif currentNode.key == key:
    return currentNode
  elif key < currentNode.key:
    return self._get(key,currentNode.leftChild)
  else:
    return self._get(key,currentNode.rightChild)

def getitem(self,key):
  return self.get(key) 

def contains(self,key):
  if self._get(key,self.root):
    return True
  else:
    return False 

if 'Northfield' in myZipTree:
  print("oom ya ya") 

以上就是Python实现二叉搜索树的方法的详细内容，更多请关注Gxl网其它相关文章！

查看更多关于Python实现二叉搜索树的方法的详细内容...