二叉树实现以及遍历算法实现（python）
用python实现一个二叉树，以下是实现的二叉树的图形样本：
新規 Microsoft Visio 绘图.jpg
代码很简单，不再做过多解释，以下是代码：
class Node:
def __init__(self,value=None,left=None,right=None):
self.value=value
self.left=left
self.right=right
treeHeader = Node('A',Node('B',Node('E',Node('H'),Node('I'))),Node('C',Node('F'),Node('G',Node('J'))));这样一个简单的二叉树就实现了。接下来该实现广度优先遍历和深度优先遍历算法了。
先看一下这两种遍历方法的区别。
深度优先遍历：从根节点出发，沿着左子树方向进行纵向遍历，直到找到叶子节点为止。然后回溯到前一个节点，进行右子树节点的遍历，直到遍历完所有可达节点为止。
广度优先遍历：从根节点出发，在横向遍历二叉树层段节点的基础上纵向遍历二叉树的层次。
从实现的角度考虑，深度优先遍历可以采用递归，而广度优先就需要借助于先进先出的数据结构来实现了。
实现代码：
深度优先遍历：
# 深度优先遍历 DFS(先序)
def depth(treeNode):
node = treeNode;
print node.value;
if node.left != None:
depth(node.left);
if node.right != None:
depth(node.right);
return;广度优先遍历：
# 广度优先遍历 BFS
def breadth(treeNode):
node = treeNode;
listTmp = [node];
while True:
if len(listTmp) != 0:
nodeTmp = listTmp.pop(0);
print nodeTmp.value;
else:
break;
if nodeTmp.left != None:
listTmp.append(nodeTmp.left);
if nodeTmp.right != None:
listTmp.append(nodeTmp.right);
return;执行结果：
大功告成。
附上1全部代码：
# coding=utf-8
class Node:
def __init__(self,value=None,left=None,right=None):
self.value=value
self.left=left
self.right=right
# 深度优先遍历 DFS(先序)
def depth(treeNode):
node = treeNode;
print node.value;
if node.left != None:
depth(node.left);
if node.right != None:
depth(node.right);
return;
# 广度优先遍历 BFS
def breadth(treeNode):
node = treeNode;
listTmp = [node];
while True:
if len(listTmp) != 0:
nodeTmp = listTmp.pop(0);
print nodeTmp.value;
else:
break;
if nodeTmp.left != None:
listTmp.append(nodeTmp.left);
if nodeTmp.right != None:
listTmp.append(nodeTmp.right);
return;
treeHeader = Node('A',Node('B',Node('E',Node('H'),Node('I'))),Node('C',Node('F'),Node('G',Node('J'))));
print "DFS:"
depth(treeHeader);
print "BFS:"
breadth(treeHeader);本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录