欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

python算法与数据结构-二叉树的遍历

程序员文章站 2024-03-08 19:30:48
...

python算法与数据结构-二叉树的遍历

python算法与数据结构-二叉树的遍历

广度优先遍历和深度优先遍历代码如下所示:

# coding=utf-8

class Node(object):
    #尽量不加3个引号的注释了容易报错

    def __init__(self, item):
        self.elem = item
        self.lchild = None
        self.rchild = None


class Tree(object):

      def __init__(self):
          self.root = None

      def add(self,item):
          node = Node(item)
          #有一种特殊情况,一上来根节点就是空的情况
          if self.root is None:
            self.root = node
            return
          queue = [self.root]
          #主要queue不为空,就一直循环
          while queue:
              cur_node = queue.pop(0)
              if cur_node.lchild is None:
                  cur_node.lchild = node
                  return
              else:
                  queue.append(cur_node.lchild)
              if cur_node.rchild is None:
                  cur_node.rchild = node
                  return
              else:
                  queue.append(cur_node.rchild)
      def breadth_travel(self):
             """广度遍历"""
             if self.root is None:
                 return
             queue = [self.root]
             while queue:
                  cur_node = queue.pop(0)
                  #换行符给去掉
                  print(cur_node.elem,end=" ")
                  if cur_node.lchild is not None:
                       queue.append(cur_node.lchild)
                  if cur_node.rchild is not None:
                       queue.append(cur_node.rchild)

      def preorder(self,node):
           #先序遍历 根左右
           if node is None:
               return
           print(node.elem,end=" ")
           self.preorder(node.lchild)
           self.preorder(node.rchild)
      def inorder(self,node):
           # 中序遍历 左中(根)右
           if node is None:
               return
           self.inorder(node.lchild)
           print(node.elem, end=" ")
           self.inorder(node.rchild)

      def postorder(self,node):
           # 后序遍历 左右中(根)
           if node is None:
               return
           self.postorder(node.lchild)
           self.postorder(node.rchild)
           print(node.elem, end=" ")



if __name__ == "__main__":
    tree = Tree()
    tree.add(0)
    tree.add(1)
    tree.add(2)
    tree.add(3)
    tree.add(4)
    tree.add(5)
    tree.add(6)
    tree.add(7)
    tree.add(8)
    tree.add(9)
    tree.breadth_travel()
    print(" ")
    tree.preorder(tree.root)
    print(" ")
    tree.inorder(tree.root)
    print(" ")
    tree.postorder(tree.root)
    print(" ")
相关标签: 算法 python