二叉樹
定義
二叉樹是每個(gè)結(jié)點(diǎn)最多有兩個(gè)子樹的樹結(jié)構(gòu)耍属。它有五種基本形態(tài)：二叉樹可以是空集峡谊；根可以有空的左子樹或右子樹恤煞；或者左趾撵、右子樹皆為空侄柔。
二叉樹的五種基本形態(tài)
由于python的基本變量類型中沒有二叉樹類型，因此要使用python實(shí)現(xiàn)二叉樹的相關(guān)操作需要先自定義二叉樹類
思路
定義二叉樹節(jié)點(diǎn)類TreeNode占调，包含三個(gè)屬性：值暂题，左子節(jié)點(diǎn)，右子節(jié)點(diǎn)究珊。
- val：表示本節(jié)點(diǎn)的值薪者，字符、數(shù)字或其他類型都可以剿涮，在定義本節(jié)點(diǎn)時(shí)傳入言津；
- left：表示本節(jié)點(diǎn)的左子節(jié)點(diǎn)，可以為空或節(jié)點(diǎn)取试，初值為None悬槽；
- right：表示本節(jié)點(diǎn)的右子樹，可以為空或節(jié)點(diǎn)瞬浓，初值為None初婆；
代碼
class TreeNode(object):
def __init__(self, x):
self.val = x
self.left = None
self.right = None
前序遍歷
定義
前序遍歷首先訪問根結(jié)點(diǎn)然后遍歷左子樹，最后遍歷右子樹。在遍歷左磅叛、右子樹時(shí)屑咳，仍然先訪問根結(jié)點(diǎn)，然后遍歷左子樹弊琴，最后遍歷右子樹乔宿。
若二叉樹為空則結(jié)束返回，否則：
- 訪問根結(jié)點(diǎn)访雪。
- 前序遍歷左子樹详瑞。
- 前序遍歷右子樹 。
前序遍歷數(shù)組=>二叉樹
給定前序遍歷的序列數(shù)組臣缀，由該數(shù)組生成一個(gè)二叉樹
思路
遞歸
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
二叉樹=>前序遍歷數(shù)組
給一個(gè)二叉樹坝橡，求出該二叉樹的前序遍歷序列
思路
遞歸
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()
