Python二叉树的遍历操作示例【前序遍历,中序遍历,后序遍历,层序遍历】
程序员文章站
2022-05-21 17:10:35
本文实例讲述了python二叉树的遍历操作。分享给大家供大家参考,具体如下:
# coding:utf-8
"""
@ encoding: utf-8
@...
本文实例讲述了python二叉树的遍历操作。分享给大家供大家参考,具体如下:
# coding:utf-8 """ @ encoding: utf-8 @ author: lixiang @ email: lixiang_cn@foxmail.com @ python_version: 2 @ time: 2018/4/11 0:09 @ more_info: 二叉树是有限个元素的集合,该集合或者为空、或者有一个称为根节点(root)的元素及两个互不相交的、分别被称为左子树和右子树的二叉树组成。 1 二叉树的每个结点至多只有二棵子树(不存在度大于2的结点),二叉树的子树有左右之分,次序不能颠倒。 2 二叉树的第i层至多有2^{i-1}个结点 3 深度为k的二叉树至多有2^k-1个结点; 4 对任何一棵二叉树t,如果其终端结点数为n0,度为2的结点数为n2,则n0=n2+1 5 度是二叉树分支树,对于二叉树而言有0,1,2三种取值 不管是前中后序遍历,都是在当前规则下,无路可走时,输出根结点。 """ class treenode(object): def __init__(self, x, left=none, right=none): self.val = x self.left = left self.right = right def pre_traverse(root): """ 根左右 :param root: :return: """ if not root: return print root.val, pre_traverse(root.left) pre_traverse(root.right) def mid_travese(root): """ 左根右 :param root: :return: """ if not root: return mid_travese(root.left) print root.val, mid_travese(root.right) def after_travese(root): """ 左右根 :param root: :return: """ if not root: return after_travese(root.left) after_travese(root.right) print root.val, def level_travese(root): if not root: return queue = [] queue.append(root) while queue: cur = queue.pop(0) print cur.val, if cur.left: queue.append(cur.left) if cur.right: queue.append(cur.right) def depth(root): if not root: return 0 left = depth(root.left) right = depth(root.right) return max(left, right) + 1 if __name__ == '__main__': """ tree是一个表示树根节点的对象 前序遍历 1 2 4 5 8 9 11 3 6 7 10 中序遍历 4 2 8 5 11 9 1 6 3 10 7 后序遍历 4 8 11 9 5 2 6 10 7 3 1 层序遍历 1 2 3 4 5 6 7 8 9 10 11 深度 5 """ tree = treenode(1, treenode(2, treenode(4), treenode(5, treenode(8), treenode(9, left=treenode(11)))), treenode(3, treenode(6), treenode(7, left=treenode(10)))) print("\n前序遍历") pre_traverse(tree) print("\n中序遍历") mid_travese(tree) print("\n后序遍历") after_travese(tree) print("\n层序遍历") level_travese(tree) print("\n深度") print(depth(tree))
运行结果:
前序遍历
1 2 4 5 8 9 11 3 6 7 10
中序遍历
4 2 8 5 11 9 1 6 3 10 7
后序遍历
4 8 11 9 5 2 6 10 7 3 1
层序遍历
1 2 3 4 5 6 7 8 9 10 11
深度
5
更多关于python相关内容感兴趣的读者可查看本站专题:《python数据结构与算法教程》、《python编码操作技巧总结》、《python函数使用技巧总结》、《python字符串操作技巧汇总》及《python入门与进阶经典教程》
希望本文所述对大家python程序设计有所帮助。
上一篇: 四款攀升高性能定制电脑主机十一大促
下一篇: Set的交集、差集踩坑记录
推荐阅读
-
Java实现的二叉树常用操作【前序建树,前中后递归非递归遍历及层序遍历】
-
Python实现二叉树前序、中序、后序及层次遍历示例代码
-
Python利用前序和中序遍历结果重建二叉树的方法
-
Python实现输入二叉树的先序和中序遍历,再输出后序遍历操作示例
-
PHP实现二叉树深度优先遍历(前序、中序、后序)和广度优先遍历(层次)实例详解
-
[PHP] 算法-根据前序和中序遍历结果重建二叉树的PHP实现
-
Python实现二叉树前序、中序、后序及层次遍历示例代码
-
求二叉树的层序遍历 python版本
-
【算法】二叉树的前序、中序、后序、层序遍历和还原。
-
PHP基于非递归算法实现先序、中序及后序遍历二叉树操作示例