Python 非递归实现前序中序、中序后序遍历还原二叉树

偏执的太偏执、 2022-05-19 14:39 314阅读 0赞

通过前序中序遍历非递归还原二叉树的原理是：在二叉树遍历中，前序遍历的次序是根左右，根据这个结论可以得出前序遍历中第一个结点一定是二叉树的根结点，再在中序遍历的结果中查询这个根结点，根结点左边的就是左子树，根结点右边的就是右子树，然后从前往后循环访问前序遍历，先还原结点的左子树，再还原结点的右子树，用栈数据结构保存构造左子树过程中访问过的节点，依次还原出二叉树。

通过中序后序遍历非递归还原二叉树的原理是跟上面类似，二叉树遍历中后序遍历的次序是左右根，即后序遍历中最后一个结点一定是二叉树的根结点，然后从后往前循环访问后序遍历，先还原右子树，再还原左子树，用栈保存构造右子树过程中访问过的结点，重新还原出二叉树。

例如：

![70][]

前序遍历：\{1, 2, 4, 3, 5, 6, 7 \}

中序遍历：\{2, 4, 1, 5, 3, 7, 6 \}

后序遍历：\{4, 2, 5, 7, 6, 3, 1 \}

代码如下

import queue
    '''
    二叉树结点
    '''  
    class TreeNode:
        def __init__(self,val=None,left=None,right=None):
            self.val = val
            self.left = left
            self.right = right
        def settag(self,tag=None):
            self.tag = tag
    
    def visit(treenode):
        print(str(treenode.val),end=' ')
    '''
    根据前序中序遍历非递归构造二叉树
    '''
    def ConstructTreeByPreInOrder(preorder,inorder):
        print('ConstructTreeByPreInOrder:',end=' ')
        treesize = len(preorder)
        root = TreeNode(preorder[0])
        isvisited = []
        for i in range(treesize):
            isvisited.append(0)
        stactnode = queue.LifoQueue()
        rootindex = inorder.index(preorder[0])
        isvisited[rootindex] = 1
        cur = root
        j = 1
        while(j<treesize):
            if(rootindex>0 and isvisited[rootindex-1]!=1):#构造左子树
                cur.left = TreeNode(preorder[j])
                rootindex = inorder.index(preorder[j])
                isvisited[rootindex] = 1
                j+=1
                stactnode.put(cur)
                cur = cur.left
            elif(rootindex<treesize and isvisited[rootindex+1]!=1):#构造右子树
                cur.right = TreeNode(preorder[j])
                rootindex = inorder.index(preorder[j])
                j+=1
                isvisited[rootindex] = 1
                cur = cur.right
            else:
                cur = stactnode.get()
                rootindex = inorder.index(cur.val)  
        PostOrderWithoutRecursion(root) #后序遍历输出构造的二叉树
    '''
    根据中序后序遍历非递归构造二叉树
    '''
    def ConstructTreeByInPostOrder(inorder,postorder): 
        print('\nConstructTreeByInPostOrder:',end=' ')
        treesize = len(postorder)
        root = TreeNode(postorder[treesize-1])
        isvisited = []
        for i in range(treesize):
            isvisited.append(0)
        stactnode = queue.LifoQueue()
        rootindex = inorder.index(postorder[treesize-1])
        isvisited[rootindex] = 1
        cur = root
        j = treesize-2
        while(j>=0):
            if(rootindex<treesize-1 and isvisited[rootindex+1]!=1):#构造右子树
                cur.right = TreeNode(postorder[j])
                rootindex = inorder.index(postorder[j])
                isvisited[rootindex] = 1
                j-=1
                stactnode.put(cur)
                cur = cur.right
            elif(rootindex>0 and isvisited[rootindex-1]!=1):#构造左子树
                cur.left = TreeNode(postorder[j])
                rootindex = inorder.index(postorder[j])
                j-=1
                isvisited[rootindex] = 1
                cur = cur.left
            else:
                cur = stactnode.get()
                rootindex = inorder.index(cur.val)  
        PreOrderWithoutRecursion(root) #前序遍历输出构造的二叉树

测试代码

if __name__=='__main__':
        preorder = [1, 2, 4, 3, 5, 6, 7]
        inorder = [2, 4, 1, 5, 3, 7, 6]
        postorder = [4, 2, 5, 7, 6, 3, 1]
        ConstructTreeByPreInOrder(preorder, inorder)
        ConstructTreeByInPostOrder(inorder, postorder)

输出结果

ConstructTreeByPreInOrder: 4 2 5 7 6 3 1 
    ConstructTreeByInPostOrder: 1 2 4 3 5 6 7

[70]: /images/20220519/1abee5a077d24d029e4f4f1c1507336b.png