Python实现二叉树结构与进行二叉树遍历的方法详解-CDA数据分析师官网

Python实现二叉树结构与进行二叉树遍历的方法详解

2017-08-20

Python实现二叉树结构与进行二叉树遍历的方法详解

二叉树是最基本的数据结构,这里我们在Python中使用类的形式来实现二叉树并且用内置的方法来遍历二叉树,下面就让我们一起来看一下Python实现二叉树结构与进行二叉树遍历的方法详解.

二叉树的建立

使用类的形式定义二叉树，可读性更好

classBinaryTree:

def__init__(self, root):

self.key=root

self.left_child=None

self.right_child=None

definsert_left(self, new_node):

ifself.left_child==None:

self.left_child=BinaryTree(new_node)

else:

t=BinaryTree(new_node)

t.left_child=self.left_child

self.left_child=t

definsert_right(self, new_node):

ifself.right_child==None:

self.right_child=BinaryTree(new_node)

else:

t=BinaryTree(new_node)

t.right_child=self.right_child

self.right_child=t

defget_right_child(self):

returnself.right_child

defget_left_child(self):

returnself.left_child

defset_root_val(self, obj):

self.key=obj

defget_root_val(self):

returnself.key

r=BinaryTree('a')

print(r.get_root_val())

print(r.get_left_child())

r.insert_left('b')

print(r.get_left_child())

print(r.get_left_child().get_root_val())

r.insert_right('c')

print(r.get_right_child())

print(r.get_right_child().get_root_val())

r.get_right_child().set_root_val('hello')

print(r.get_right_child().get_root_val())

Python进行二叉树遍历

需求：
python代码实现二叉树的：
1. 前序遍历，打印出遍历结果
2. 中序遍历，打印出遍历结果
3. 后序遍历，打印出遍历结果
4. 按树的level遍历，打印出遍历结果
5. 结点的下一层如果没有子节点，以‘N'代替

方法：
使用defaultdict或者namedtuple表示二叉树
使用StringIO方法，遍历时写入结果，最后打印出结果
打印结点值时，如果为空，StringIO（）写入‘N '
采用递归访问子节点
代码

#!/usr/bin/env python3

# -*- coding: utf-8 -*-

# test tree as below:

''' 1 / \ / \ / \ / \ 2 3 / \ / \ / \ / \ 4 5 6 N / \ / \ / \ 7 N N N 8 9 / \ / \ / \ N N N N N N '''

fromcollectionsimportnamedtuple

fromioimportStringIO

#define the node structure

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

#initialize the tree

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))

#read and write str in memory

output=StringIO()

#read the node and write the node's value

#if node is None, substitute with 'N '

defvisitor(node):

ifnodeisnotNone:

output.write('%i '%node.data)

else:

output.write('N ')

#traversal the tree with different order

deftraversal(node, order):

ifnodeisNone:

visitor(node)

else:

op={

'N':lambda: visitor(node),

'L':lambda: traversal(node.left, order),

'R':lambda: traversal(node.right, order),

}

forxinorder:

op[x]()

#traversal the tree level by level

deftraversal_level_by_level(node):

ifnodeisnotNone:

current_level=[node]

whilecurrent_level:

next_level=list()

fornincurrent_level:

iftype(n)isstr:

output.write('N ')

else:

output.write('%i '%n.data)

ifn.leftisnotNone:

next_level.append(n.left)

else:

next_level.append('N')

ifn.rightisnotNone:

next_level.append(n.right)

else:

next_level.append('N ')

output.write('\n')

current_level=next_level

if__name__=='__main__':

fororderin['NLR','LNR','LRN']:

iforder=='NLR':

output.write('this is preorder traversal:')

traversal(tree, order)

output.write('\n')

eliforder=='LNR':

output.write('this is inorder traversal:')

traversal(tree, order)

output.write('\n')

else:

output.write('this is postorder traversal:')

traversal(tree, order)

output.write('\n')

output.write('traversal level by level as below:'+'\n')

traversal_level_by_level(tree)

print(output.getvalue())

CDA数据分析师考试相关入口一览（建议收藏）：

▷ 想报名CDA认证考试，点击>>> “CDA报名” 了解CDA考试详情；

▷ 想加入CDA考试题库，点击>>> “CDA题库” 了解CDA考试详情；

▷ 想学习CDA考试教材，点击>>> “CDA教材” 了解CDA考试详情；

▷ 想查询CDA考试成绩，点击>>> “CDA成绩” 了解CDA考试详情；

▷ 想了解CDA考试含金量，点击>>> “CDA含金量” 了解CDA考试详情；

▷ 想获取CDA考试时间/费用/条件/大纲/通过率，点击 >>>“CDA考试官网” 了解CDA考试详情；

python

数据分析咨询请扫描二维码

上一篇CDA认证再升一档！与国家共同推进大数据人才培养标准教育事业！

下一篇企业如何利用商品推荐的大数据来破除实体寒冰？

Python实现二叉树结构与进行二叉树遍历的方法详解

CDA考试动态

CDA报考指南

热门栏目

最新资讯

数据分析师教程《Python数据分析极简入门》第2节 6 ...

数据分析师教程《Python数据分析极简入门》第2节 5 ...

数据分析需要学哪些方面

数据分析适合在什么单位工作

数据分析是什么工作内容

数据分析师需要掌握什么技能

数据开发和数据分析区别

数据架构师是干什么的

数据分析师需要具备的能力

数据分析师需要具备的技能有哪些

数据分析师需要具备的技能和能力

数据分析师的发展前景

数据分析师教程《Python数据分析极简入门》第2节 4 ...

数据分析师的工作内容是什么

数据分析师必须掌握的技能有哪些

数据分析入门难吗

数据分析能干啥

数据分析行业的前景

数据分析的常用方法

什么是企业数字化转型