【python】二叉树

二叉树

定义

二叉树是每个结点最多有两个子树的树结构。它有五种基本形态：二叉树可以是空集；根可以有空的左子树或右子树；或者左、右子树皆为空。

二叉树的五种基本形态

由于python的基本变量类型中没有二叉树类型，因此要使用python实现二叉树的相关操作需要先自定义二叉树类

思路

定义二叉树节点类TreeNode，包含三个属性：值，左子节点，右子节点。

• val：表示本节点的值，字符、数字或其他类型都可以，在定义本节点时传入；
• left：表示本节点的左子节点，可以为空或节点，初值为None；
• right：表示本节点的右子树，可以为空或节点，初值为None；

代码

class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

前序遍历

定义

前序遍历首先访问根结点然后遍历左子树，最后遍历右子树。在遍历左、右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树。

若二叉树为空则结束返回，否则：

1. 访问根结点。
2. 前序遍历左子树。
3. 前序遍历右子树 。

前序遍历数组=>二叉树

给定前序遍历的序列数组，由该数组生成一个二叉树
思路
递归

def make_a_Binary_Tree_by(li):
    if li[0]!=None:
        node = TreeNode(li.pop(0))
        node.left=make_a_Binary_Tree_by(li)
        node.right=make_a_Binary_Tree_by(li)
    else:
        return li.pop(0)
    return node

二叉树=>前序遍历数组

给一个二叉树，求出该二叉树的前序遍历序列
思路
递归

def preorder_traversal(root):
    li=[]
    if root!=None:
        li+=[root.val]
        li+=preorder_traversal(root.left)
        li+=preorder_traversal(root.right)
    else:
        return []
    return li

测试代码

#coding utf-8
#144. Binary Tree Preorder Traversal
class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
def make_a_Binary_Tree_by(li):
    if li[0]!=None:
        node = TreeNode(li.pop(0))
        node.left=make_a_Binary_Tree_by(li)
        node.right=make_a_Binary_Tree_by(li)
    else:
        return li.pop(0)
    return node
def preorder_traversal(root):
    li=[]
    if root!=None:
        li+=[root.val]
        li+=preorder_traversal(root.left)
        li+=preorder_traversal(root.right)
    else:
        return []
    return li
def main():
    l = [10, 7, 4,None,None, 9,None,None, 13, None, 15,None,None]
    root=make_a_Binary_Tree_by(l)
    print('\t\t',root.val)
    print('\t',root.left.val,'\t\t  ',root.right.val)
    print(' ',root.left.left.val,'   ',root.left.right.val,' ',root.right.left,'  ',root.right.right.val)
    print(preorder_traversal(root))
if __name__ == '__main__':
    main()