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

实现二叉树的先序、中序、后序遍历,包括递归方式和非递归方式

程序员文章站 2022-05-16 10:09:31
...
class TreeNode:
    
    def __init__(self,x):
        self.value = x
        self.right = None
        self.left = None
        
def createTree(root):
    
    data = input("input data")
    if data == "#"
        root = None
    else:
        root = TreeNode(element)
        root.left = createTree(root.left)
        root.right = createTree(root.right)
    
    return  root

"""
    前序遍历
"""
def preOrderRecur(head):
    
    if head == None:
        return 
    print(head.value + ' ')
    preOrderRecur(head.left)
    preOrderRecur(head.right)
    
"""
    中序遍历
"""
def inOrderRecur(head):
    
    if head == None:
        return
    inOrderRecur(head.left)
    print(head.value + ' ' )
    inOrderRecur(head.right)
    
"""
    后序遍历
"""
def posOrderRecur(head):
    
    if head == None:
        return
    posOrderRecur(head.left)
    posOrderRecur(head.right)
    print(head.value + ' ')


"""
    非递归方式
"""
 
def preOrderUnRecur(head):
    print("pre-order:")
    if head!=None:
        stack = []
        stack.append(head)
        while len(stack)!=0:
            head = stack.pop()
            print(head.value + " ")
            if head.right!=None:
                stack.push(head.right)
            if head.left!=None:
                stack.push(head.left)
    print(" ")
    
    
def inOrderUnRecur(head):
    """
    先把所有左子树全都压入栈中
    """
    print("in-order:")
    if head!=None:
        stack = []
        while len(stack)!=0 or head!=None:
            if head!= None:
                stack.push(head)
                head = head.left
            else:
                head = stack.pop()
                print(head.value + " ")
                head = head.right
                
    print(" ")
    
def posOrderUnRecur(head):
    
    print("pos-order:")
    if head!=None:
        s1 = []
        s2 = []
        s1.push(head)
        while len(s1)!=0:
            head = s1.pop()
            s2.push(head)
            
            if head.left!=None:
                s1.push(head.left)
            if head.right!=None:
                s1.push(head.right)
                
        while s2.isEmpty() is not True:
            print(s2.pop().value + " ")
            
    print(" ")