python实现统一形式的二叉树前中后序非递归遍历

小鱼儿 2022-04-01 14:44 50阅读 0赞

对于二叉树的遍历，递归形式非常简单，可以很快写出来，而对于非递归的形式，在不熟的情况下，还是需要一番思考的，因为二叉树的非递归遍历并没有一个统一的形式方便理解和记忆，对于前序和中序非递归遍历，还算统一，而一般的非递归后序遍历，和前两者有很大的差异。

参考[python实现二叉树和它的七种遍历][python]，给出一般形式的非递归前中后序遍历：

#### 一般形式的非递归前中后序遍历 ####

def front_stack(self, root):
            """利用堆栈实现树的先序遍历"""
            if root == None:
                return
            myStack = []
            node = root
            while node or myStack:
                while node:                     #从根节点开始，一直找它的左子树
                    print (node.elem)
                    myStack.append(node)
                    node = node.lchild
                node = myStack.pop()            #while结束表示当前节点node为空
                node = node.rchild                  #开始查看它的右子树
    
    
        def middle_stack(self, root):
            """利用堆栈实现树的中序遍历"""
            myStack = []
            node = root
            while node or myStack:
                while node:                     #从根节点开始，一直找它的左子树
                    myStack.append(node)
                    node = node.lchild
                node = myStack.pop()            #while结束表示当前节点node为空
                print (node.elem)
                node = node.rchild                  #开始查看它的右子树
    
    
        def later_stack(self, root):
            """利用堆栈实现树的后序遍历"""
            if root == None:
                return
            myStack1 = []
            myStack2 = []
            node = root
            myStack1.append(node)
            while myStack1:             #这个while循环的功能是找出后序遍历的逆序，存在myStack2里面
                node = myStack1.pop()
                if node.lchild:
                    myStack1.append(node.lchild)
                if node.rchild:
                    myStack1.append(node.rchild)
                myStack2.append(node)
            while myStack2:                         #将myStack2中的元素出栈，即为后序遍历次序
                print(myStack2.pop().elem)

#### 非递归后序遍历不同的原因 ####

从代码中可以看出，前中序非递归遍历较为相似，只有节点访问的位置不一样，但也有差别，前者是在入栈前访问，后者是出栈后访问。

而后序遍历就大不一样了，它不能和上面的前中序一样，是因为它需要访问完右子树之后才访问当前节点，而在上面前序和中序里的栈，在访问右子树之前已经把当前节点pop出去了，不可能再访问到当前节点，因此不能简单像下面的递归版本一样把节点访问放在最后就可以了。

def later_recursive(self, root):
            """利用递归实现树的后序遍历"""
            if root == None:
                return
            self.later_digui(root.lchild)
            self.later_digui(root.rchild)
            print (root.elem)

上面的递归后序遍历中，因为在当前访问节点下，root一直被保存，不受访问左右子树的影响，因此，当前节点的访问直接放在最后即可。

#### 统一形式的非递归前中后序遍历 ####

下面给出一种统一形式的二叉树非递归遍历，它和递归版的一样，只要更改一行代码的位置即可。

但它的时间复杂度相较上面的方法会更高一些，因为它需要对节点进行两次遍历，第一次并不访问，第二次再访问，因此需要一个记录访问次数的flag，在空间复杂度上也会更大，但它统一的形式能更好的理解。

class Node(object):
        """节点类"""
        def __init__(self, elem=-1, lchild=None, rchild=None):
            self.elem = elem
            self.lchild = lchild
            self.rchild = rchild
    
    
    class Tree(object):
        """树类"""
        def __init__(self):
            self.root = Node()
            self.myQueue = []
    
        def add(self, elem):
            """为树添加节点，生成完全二叉树"""
            node = Node(elem)
            if self.root.elem == -1:  # 如果树是空的，则对根节点赋值
                self.root = node
                self.myQueue.append(self.root)
            else:
                treeNode = self.myQueue[0]  # 此结点的子树还没有齐。
                if treeNode.lchild == None:
                    treeNode.lchild = node
                    self.myQueue.append(treeNode.lchild)
                else:
                    treeNode.rchild = node
                    self.myQueue.append(treeNode.rchild)
                    self.myQueue.pop(0)  # 如果该结点存在右子树，将此结点丢弃。
    
        def front_recursive(self, root):
            """利用递归实现树的先序遍历"""
            if root == None:
                return
            print (root.elem)
            self.front_recursive(root.lchild)
            self.front_recursive(root.rchild)
    
        def middle_recursive(self, root):
            """利用递归实现树的中序遍历"""
            if root == None:
                return
            self.middle_recursive(root.lchild)
            print (root.elem)
            self.middle_recursive(root.rchild)
    
        def later_recursive(self, root):
            """利用递归实现树的后序遍历"""
            if root == None:
                return
            self.later_recursive(root.lchild)
            self.later_recursive(root.rchild)
            print (root.elem)
    
        def front_loop(self,root):
            """利用循环实现树的前序遍历"""
            stack = []
            stack.append((root,0))
            while stack:
                node, isVisit = stack.pop()
                if not node: continue
                if isVisit:
                    print (node.elem)
                else:
                    stack.append((node.rchild, 0))
                    stack.append((node.lchild, 0))
                    stack.append((node, 1))
    
        def middel_loop(self,root):
            """利用循环实现树的中序遍历"""
            stack = []
            stack.append((root,0))
            while stack:
                node, isVisit = stack.pop()
                if not node: continue
                if isVisit:
                    print (node.elem)
                else:
                    stack.append((node.rchild, 0))
                    stack.append((node, 1))
                    stack.append((node.lchild, 0))
    
        def later_loop(self,root):
            """利用循环实现树的后序遍历"""
            stack = []
            stack.append((root,0))
            while stack:
                node, isVisit = stack.pop()
                if not node: continue
                if isVisit:
                    print (node.elem)
                else:
                    stack.append((node, 1))
                    stack.append((node.rchild, 0))
                    stack.append((node.lchild, 0))
    
    if __name__ == '__main__':
        """主函数"""
        elems = range(10)           #生成十个数据作为树节点
        tree = Tree()               #新建一个树对象
        for elem in elems:
            tree.add(elem)          #逐个添加树的节点, 生成完全二叉树
    
        tree.front_recursive(tree.root)
        tree.front_loop(tree.root)

参考：[更简单的非递归遍历二叉树的方法][Link 1]

[python]: https://blog.csdn.net/Bone_ACE/article/details/46718683
[Link 1]: https://www.jianshu.com/p/49c8cfd07410