关于我们

质量为本、客户为根、勇于拼搏、务实创新

< 返回新闻公共列表

python中如何遍历树(python实现树的遍历)

发布时间:2022-07-02 07:50:37

  

  各种遍历顺序如下图所示:

  树的深度

[code]# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution(object):
    def maxdepth(self, root):
        if root is None:
            return 0
        return max(self.maxdepth(root.left), self.maxdepth(root.right))+1[/code]

  深度优先

  深度优先遍历有三种方式:前序遍历、中序遍历和后序遍历

  所说的前序、中序、后序,是指根节点的先后顺序。

  前序遍历:根节点 -> 左子树 -> 右子树

[code]# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution(object):
    def preorder(self, root):
        if root is None:
            return ''
        print root.val
        if root.lef:
            self.preorder(root.left)
        if root.right:
            self.preorder(root.right)[/code]

  中序遍历:左子树 -> 根节点 -> 右子树

[code]# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution(object):
    def midorder(self, root):
        if root is None:
            return ''
        if root.lef:
            self.midorder(root.left)
        print root.val
        if root.right:
            self.midorder(root.right)[/code]

  后序遍历:左子树 -> 右子树 -> 根节点

[code]# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution(object):
    def endorder(self, root):
        if root is None:
            return ''
        if root.lef:
            self.endorder(root.left)
        if root.right:
            self.endorder(root.right)
        print root.val[/code]

  广度优先

  广度优先遍历,即层次遍历,优先遍历兄弟节点

  层次遍历:根节点 -> 左节点 -> 右节点

[code]# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution(object):
  def graorder(self, root):
    if root is None:
      return ''
    queue = [root]
    while queue:
      res = []
      for item in queue:
        print item.val,
        if item.left:
          res.append(item.left)
        if item.right:
          res.apppend(item.right)
      queue = res[/code]

  比较两棵树是否相同

[code]# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution(object):
    def issame(self, root1, root2):
        if root1 is None and root2 is None:
            return True
        elif root1 and root2:
            return root1.val==root2.val and issame(root1.left, root2.left) and issame(root1.right, root2.right)
        else:
            return False[/code]




相关推荐

【2022年的云计算虚拟化市场现状和发展(云计算未来市场) >>点击查看详情<<

【习近平向“全球发展:共同使命与行动价值”智库媒体高端论坛致贺信 >>点击查看详情<<

/template/Home/Redyun/PC/Static