二叉树
定义
二叉树是每个结点最多有两个子树的树结构。它有五种基本形态：二叉树可以是空集；根可以有空的左子树或右子树；或者左、右子树皆为空。
二叉树的五种基本形态
由于python的基本变量类型中没有二叉树类型，因此要使用python实现二叉树的相关操作需要先自定义二叉树类
思路
定义二叉树节点类TreeNode，包含三个属性：值，左子节点，右子节点。
- val：表示本节点的值，字符、数字或其他类型都可以，在定义本节点时传入；
- left：表示本节点的左子节点，可以为空或节点，初值为None；
- right：表示本节点的右子树，可以为空或节点，初值为None；
代码
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
测试代码
#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()
