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

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

若不方便扫码，搜微信号：CDAshujufenxi

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

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

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

CDA考试动态

CDA报考指南

热门栏目

最新资讯

数据分析师会成为下一个失业高危职业吗？ ...

数据分析师的主要工作内容

数据分析师的能力要求

【分享】阿里P8大佬：2025年数据分析师还有前途吗？ ...

【干货】字节5年数分大咖：手把手教你构建数据分析 ...

【干货】7款超强大的AI数据分析工具，再也不用痛苦 ...

【干货】12种实用数据分析模型，强烈建议收藏！ ...

高薪or淘汰？数据分析师在AI时代的生存之道！ ...

想当数据分析师？这些日常工作你一定要知道！ ...

数据分析师会招小白吗

什么人适合做数据分析师

数据分析师的发展前景

数据分析的四个步骤

别再拍脑袋决策了！学会用数据分析发现问题，90%职 ...

excel数据分析怎么调出来

数据分析师所需技能与知识

想让PPT数据对比更吸睛？3种数据分析方法，让图表瞬 ...

数据分析师的专业背景要求

数据分析专业适合的学习路线

还在被数据分析师面试问题难倒？这10个高频考题+答 ...