二叉树实现以及遍历算法实现(python)

作者 : 开心源码 本文共1606个字,预计阅读时间需要5分钟 发布时间: 2022-05-11 共77人阅读

使用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;

广度优先遍历:

# 广度优先遍历 BFSdef 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;

执行结果:

image.png

大功告成。

附上1一律代码:

# coding=utf-8class 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;# 广度优先遍历 BFSdef 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);

说明
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是摆设,本站源码仅提供给会员学习使用!
7. 如遇到加密压缩包,请使用360解压,如遇到无法解压的请联系管理员
开心源码网 » 二叉树实现以及遍历算法实现(python)

发表回复