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

二叉树的先序中序后序遍历(非递归)

程序员文章站 2022-06-17 17:36:08
...

来自牛客网直通BAT算法精讲:



二叉树的先序中序后序遍历(非递归)

弹出栈顶并打印,先压右后压左

  1.     def preOrder(self):  
  2.         if not self.root:  
  3.             return  
  4.         stackNode = []  
  5.         stackNode.append(self.root)  
  6.         while stackNode:  
  7.             node = stackNode.pop()  
  8.             print node.value,  
  9.             if node.rightNode:  
  10.                 stackNode.append(node.rightNode)  
  11.             if node.leftNode:  
  12.                 stackNode.append(node.leftNode)  
  13.  


二叉树的先序中序后序遍历(非递归)

  1.     def midOrder(self):  
  2.         if not self.root:  
  3.             return  
  4.         stackNode = []  
  5.         node = None  
  6.         node = self.root  
  7.         while stackNode or node:  
  8.             while node:  
  9.                 stackNode.append(node)  
  10.                 node = node.leftNode  
  11.             node = stackNode.pop()  
  12.             print node.value,  
  13.             node = node.rightNode 


二叉树的先序中序后序遍历(非递归)

    def afterOrder(self,root):
        stk1=[]
        stk2=[]
        stk1.append(root)
        while stk1:
            node=stk1.pop()
            stk2.append(node)
            stk1.append(node.lchild)
            stk1.append(node.rchild)
        while stk2:
            print(stk2.pop())


二叉树的先序中序后序遍历(非递归)

 def afterOrder2(self,root):
         stk=[]
         stk.append(root)
         h=root
         c=None
         while stk:
             c=stk[-1]
             if c.lchid!=None and h!=c.lchid and H!=c.rchid:
                 stk.append(c.lcihld)
             elif c.rchid!=0 and h!=c.rchild:
                 stk.append(c.rchid)
             else:
                 node=stk.pop()
                 print(node)