Tree

定义

一棵二叉树的定义如下。key可以存储任意的对象，亦即每棵树也可以是其他树的子树。



In [3]:

    
class BinaryTree():
    def __init__(self, root_obj):
        self.key = root_obj
        self.left_child = None
        self.right_child = None
    
    def insert_left(self, new_node):
        # if the tree do not have a left child
        # then create a node: one tree without children
        if self.left_child is None:
            self.left_child = BinaryTree(new_node)
        # if there is a child, then concat the child
        # under the node we inserted
        else:
            t = BinaryTree(new_node)
            t.left_child = self.left_child
            self.left_child = t

    def insert_right(self, new_node):
        # if the tree do not have a right child
        # then create a node: one tree without children
        if self.right_child is None:
            self.right_child = BinaryTree(new_node)
        # if there is a child, then concat the child
        # under the node we inserted
        else:
            t = BinaryTree(new_node)
            t.right_child = self.right_child
            self.right_child = t
    
    def get_right_child(self):
        return self.right_child
    
    def get_left_child(self):
        return self.left_child
    
    def set_root(self, obj):
        self.key = obj
    
    def get_root(self):
        return self.key

r = BinaryTree('a')
print r.get_root()
print r.get_left_child()
r.insert_left('b')
print r.get_left_child().get_root()









    



a
None
b

遍历

前序
中序
后序



In [9]:

    
def preorder(tree):
    if tree:
        print tree.get_root()
        preorder(tree.get_left_child())
        preorder(tree.get_right_child())

def postorder(tree):
    if tree:
        postorder(tree.get_left_child())
        postorder(tree.get_right_child())
        print tree.get_root()

def inorder(tree):
    if tree:
        inorder(tree.get_left_child())
        print tree.get_root()
        inorder(tree.get_right_child())

r = BinaryTree('root')
r.insert_left('l1')
r.insert_left('l2')
r.insert_right('r1')
r.insert_right('r2')
r.get_left_child().insert_right('r3')


preorder(r)









    



root
l2
l1
r3
r2
r1

二叉堆实现优先队列

二叉堆是队列的一种实现方式。

二叉堆可以用完全二叉树来实现。所谓完全二叉树（complete binary tree），有定义如下：

A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible. 除叶节点外，所有层都是填满的，叶节点则按照从左至右的顺序填满。

完全二叉树的一个重要性质：

当以列表表示完全二叉树时，位置 p 的父节点，其 left child 位于 2p 位置，其 right child 位于 2p+1 的位置。

为了满足使用列表表示的性质，列表中第一个位置list[0]由 0 填充，树从list[1]开始。

Operations

BinaryHeap() creates a new, empty, binary heap.
insert(k) adds a new item to the heap.
findMin() returns the item with the minimum key value, leaving item in the heap.
delMin() returns the item with the minimum key value, removing the item from the heap.
isEmpty() returns true if the heap is empty, false otherwise.
size() returns the number of items in the heap.
buildHeap(list) builds a new heap from a list of keys.



In [ ]:

    
class BinHeap(object):
    def __init__(self):
        self.heap_list = [0]
        self.current_size = 0

二叉搜索树 Binary Search Trees

其性质与字典非常相近。

Operations

Map() Create a new, empty map.
put(key,val) Add a new key-value pair to the map. If the key is already in the map then replace the old value with the new value.
get(key) Given a key, return the value stored in the map or None otherwise.
del Delete the key-value pair from the map using a statement of the form del map[key].
len() Return the number of key-value pairs stored in the map.
in Return True for a statement of the form key in map, if the given key is in the map.



In [ ]:

    
class BinarySearchTree(object):
    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__()
    
    def put(self, key, val):
        if self.root:
            self._put(key, val, self.root)
        else:
            self.root = TreeNode(key, val)
        self.size += 1
    
    def _put(key, val, current_node):
        if key < current_node:
            if current_node.has_left_child():
                _put(key, val, current_node.left_child)
            else:
                current_node.left_child = TreeNode(key, val, parent=current_node)
        else:
            if current_node.has_right_child():
                _put(key, val, current_node.right_child)
            else:
                current_node.right_child = TreeNode(key, val, parent=current_node)
    
    def __setitem__(self, k, v):
        self.put(k, v)

class TreeNode(object):
    def __init__(self, key, val, left=None, right=None, parent=None):
        self.key = key
        self.payload = val
        self.left_child = left
        self.right_child = right
        self.parent = parent
    
    def has_left_child(self):
        return self.left_child
    
    def has_right_child(self):
        return self.right_child
    
    def is_root(self):
        return not self.parent
    
    def is_leaf(self):
        return not (self.right_child or self.left_child)
    
    def has_any_children(self):
        return self.right_child or self.left_child
    
    def has_both_children(self):
        return self.right_child and self.right_child
    
    def replace_node_data(self, key, value, lc, rc):
        self.key = key
        self.payload = value
        self.left_child = lc
        self.right_child = rc
        if self.has_left_child():
            self.left_child.parent = self
        if self.has_right_child():
            self.right_child.parent = self

平衡二叉搜索树 Balanced Binary Search Tree

又名 AVL 树。避免出现最坏情况下 O(n) 的复杂度。AVL 的搜索复杂度稳定在 O(logN)。

balanceFactor=height(leftSubTree)−height(rightSubTree)