二叉树的两种遍历方式-蒲公英云

二叉树的两种遍历方式

悠悠 2023-01-23 11:51 50阅读 0赞

# 二叉树的遍历可分为两种
''' 1.广度优先遍历 分层把元素放到 队列中，进行遍历 2.深度优先遍历 前序，中序，后序遍历，使用堆栈和递归的方式 '''
# 广度优先遍历一颗二叉树
def bfsTree(self):
    if sele.root =None:
        return None
    queue =[]
    queue.append(self.root)
    while queue:
        node=queue.pop(0)
        print(node.element,end =',')
        if node.lchild != None:
            queue.append(node.lchild)
        if node.rchild != None:
            queue.append(node.rchild)
    print()
# 深度优先遍历
# 1.递归实现先序遍历
def preorder(self,root):
    if not root:
        return
    print(root.element,end =',')
    self.preorder(root.lchild)
    self.preorder(root.rchild
# 2.递归实现中序遍历
def inorder(self,root):
    if not root:
        return 
    self.inorder(root.lchild)
    print(root.element,end=',')
    self.inorder(root.rchild)
# 3.递归实现后序遍历
def postorder(self,root):
    if not root:
        return 
    self.postorder(root.lchild)
    self.postorder(root.rchild)
    print(root.element,end = ',')
if __name__ == '__main__':
    binaryTree = Tree()
    for i in range(7):
        binaryTree.__add__(i+1)
    # 广度优先遍历
    print("广度优先：")
    binaryTree.breadth_travel()
    # 深度优先，先序遍历
    root = binaryTree.root
    binaryTree.preorder(root)
    print('深度优先--先序遍历')
    binaryTree.inorder(root)
    print('深度优先--中序遍历')
    binaryTree.postorder(root)
    print('深度优先--后序遍历')