FilesExpand file tree

 master

/

binary_tree_traversal.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

72 lines (56 loc) · 1.39 KB

 master

/

binary_tree_traversal.py

Copy path

Top

File metadata and controls

• Code
• Blame

72 lines (56 loc) · 1.39 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

#! /usr/bin/env python

#coding:utf-8

"""

#问题

用递归方式遍历二叉树

"""

from collections import namedtuple

from sys import stdout

Node = namedtuple('Node', 'data, left, right')

tree = Node(1,

Node(2,

Node(4,

Node(7, None, None),

None),

Node(5, None, None)),

Node(3,

Node(6,

Node(8, None, None),

Node(9, None, None)),

None))

#前序（pre-order，NLR）

def preorder(node):

if node is not None:

print node.data,

preorder(node.left)

preorder(node.right)

#中序（in-order，LNR）

def inorder(node):

if node is not None:

inorder(node.left)

print node.data,

inorder(node.right)

#后序（post-order，LRN）

def postorder(node):

if node is not None:

postorder(node.left)

postorder(node.right)

print node.data,

#层序（level-order）

def levelorder(node, more=None):

if node is not None:

if more is None:

more = []

more += [node.left, node.right]

print node.data,

if more:

levelorder(more[0], more[1:])

print ' preorder: ',

preorder(tree)

print '\t\n inorder: ',

inorder(tree)

print '\t\n postorder: ',

postorder(tree)

print '\t\nlevelorder: ',

levelorder(tree)

print '\n'