python实现树的深度优先遍历与广度优先遍历详解
本文实例讲述了python实现树的深度优先遍历与广度优先遍历。分享给大家供大家参考，具体如下：
广度优先(层次遍历)
从树的root开始，从上到下从左到右遍历整个树的节点
数和二叉树的区别就是，二叉树只有左右两个节点
广度优先顺序：A-B-C-D-E-F-G-H-I
代码实现
defbreadth_travel(self,root): """利用队列实现树的层次遍历""" ifroot==None: return queue=[] queue.append(root) whilequeue: node=queue.pop(0) printnode.elem, ifnode.lchild!=None: queue.append(node.lchild) ifnode.rchild!=None: queue.append(node.rchild)
深度优先
深度优先有三种算法：前序遍历，中序遍历，后序遍历
先序遍历在先序遍历中，我们先访问根节点，然后递归使用先序遍历访问左子树，再递归使用先序遍历访问右子树
根节点->左子树->右子树
#实现1 defpreorder(self,root): """递归实现先序遍历""" ifroot==None: return printroot.elem self.preorder(root.lchild) self.preorder(root.rchild)
#实现2 defdepth_tree(tree_node): iftree_nodeisnotNone: print(tree_node._data) iftree_node._leftisnoeNone: returndepth_tree(tree_node._left) iftree_node._rightisnotNone: returndepth_tree(tree_node._right)
中序遍历在中序遍历中，我们递归使用中序遍历访问左子树，然后访问根节点，最后再递归使用中序遍历访问右子树
左子树->根节点->右子树
definorder(self,root): """递归实现中序遍历""" ifroot==None: return self.inorder(root.lchild) printroot.elem self.inorder(root.rchild)
后序遍历在后序遍历中，我们先递归使用后序遍历访问左子树和右子树，最后访问根节点
左子树->右子树->根节点
defpostorder(self,root): """递归实现后续遍历""" ifroot==None: return self.postorder(root.lchild) self.postorder(root.rchild) printroot.elem
更多关于Python相关内容感兴趣的读者可查看本站专题：《Python数据结构与算法教程》、《Python加密解密算法与技巧总结》、《Python编码操作技巧总结》、《Python函数使用技巧总结》、《Python字符串操作技巧汇总》及《Python入门与进阶经典教程》
希望本文所述对大家Python程序设计有所帮助。
声明：本文内容来源于网络，版权归原作者所有，内容由互联网用户自发贡献自行上传，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任。如果您发现有涉嫌版权的内容，欢迎发送邮件至：czq8825#qq.com（发邮件时，请将#更换为@）进行举报，并提供相关证据，一经查实，本站将立刻删除涉嫌侵权内容。