二叉树python实现

2 years ago

source link: https://liangyaorong.github.io/blog/2017/%E4%BA%8C%E5%8F%89%E6%A0%91python%E5%AE%9E%E7%8E%B0/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

二叉树python实现

# coding:utf-8

class Binary_Tree(object):
    def __init__(self, val=None):
        self.root = val
        self.left = None
        self.right = None


def insert_node(tree, val):
    '''插入节点'''
    val_node = Binary_Tree(val)
    if tree.root is None:
        tree.root = val
    else:
        if tree.root < val:
            if tree.right:
                insert_node(tree.right, val)
            else:
                tree.right = val_node
        if tree.root > val:
            if tree.left:
                insert_node(tree.left, val)
            else:
                tree.left = val_node
    return tree


def build_tree(tree, val_list):
    '''根据列表创建二叉树'''
    for val in val_list:
        insert_node(tree, val)
    return tree


def pre_order_print(tree, pre_list = []):
    '''前序遍历'''
    if tree is not None:
        pre_list.append(tree.root)
        pre_order_print(tree.left, pre_list)
        pre_order_print(tree.right, pre_list)
    return pre_list


def in_order_print(tree, in_list = []):
    '''中序遍历'''
    if tree is not None:
        in_order_print(tree.left, in_list)
        in_list.append(tree.root)
        in_order_print(tree.right, in_list)
    return in_list


def post_order_print(tree, post_list = []):
    '''后序遍历'''
    if tree is not None:
        post_order_print(tree.left, post_list)
        post_order_print(tree.right, post_list)
        post_list.append(tree.root)
    return post_list


def find_min(tree):
    '''查找最小值'''
    while tree.left is not None:
        tree = tree.left
    return tree.root


def find_max(tree):
    '''查找最大值'''
    while tree.right is not None:
        tree = tree.right
    return tree.root


def find_val(tree, val):
    '''查找特定值'''
    find = False
    while tree is not None:

        if tree.root > val:
            tree = tree.left
        elif tree.root < val:
            tree = tree.right
        elif tree.root == val:
            find = True
            print "finding %s successfully" % val
            break
    if find is False:
        print "can not find %s" % val
    return find


if __name__ == '__main__':
    bt = Binary_Tree()
    bt = build_tree(bt, [4,6,5,9,1,12,7,10])
    find_val(bt, 18)

Recommend