Python实现二叉树遍历的递归和非递归算法

刺骨的言语ヽ痛彻心扉 2022-02-19 06:43 272阅读 0赞

本文主要用python实现二叉树的4种遍历算法，除层次遍历外，前序、中序和后序遍历分别包含递归和非递归2种实现方式。

### 前序遍历 ###

# -----------前序遍历 ------------
        # 递归算法
        def pre_order_recursive(self, T):
            if T == None:
                return
            print(T.root, end=' ')
            self.pre_order_recursive(T.lchild)
            self.pre_order_recursive(T.rchild)
    
        # 非递归算法
        def pre_order_non_recursive(self, T):
            """借助栈实现前驱遍历
            """
            if T == None:
                return
            stack = []
            while T or len(stack) > 0:
                if T:
                    stack.append(T)
                    print(T.root, end=' ')
                    T = T.lchild
                else:
                    T = stack[-1]
                    stack.pop()
                    T = T.rchild

### 中序遍历 ###

# -----------中序遍历 ------------
        # 递归算法
        def mid_order_recursive(self, T):
            if T == None:
                return
            self.mid_order_recursive(T.lchild)
            print(T.root, end=' ')
            self.mid_order_recursive(T.rchild)
    
        # 非递归算法
        def mid_order_non_recursive(self, T):
            """借助栈实现中序遍历
            """
            if T == None:
                return
            stack = []
            while T or len(stack) > 0:
                if T:
                    stack.append(T)
                    T = T.lchild
                else:
                    T = stack.pop()
                    print(T.root, end=' ')
                    T = T.rchild

### 后序遍历 ###

# -----------后序遍历 ------------
        # 递归算法
        def post_order_recursive(self, T):
            if T == None:
                return
            self.post_order_recursive(T.lchild)
            self.post_order_recursive(T.rchild)
            print(T.root, end=' ')
    
        # 非递归算法
        def post_order_non_recursive(self, T):
            """借助两个栈实现后序遍历
            """
            if T == None:
                return
            stack1 = []
            stack2 = []
            stack1.append(T)
            while stack1:
                node = stack1.pop()
                if node.lchild:
                    stack1.append(node.lchild)
                if node.rchild:
                    stack1.append(node.rchild)
                stack2.append(node)
            while stack2:
                print(stack2.pop().root, end=' ')
            return

### 层次遍历 ###

# -----------层次遍历 ------------
        def level_order(self, T):
            """借助队列（其实还是一个栈）实现层次遍历
            """
            if T == None:
                return
            stack = []
            stack.append(T)
            while stack:
                node = stack.pop(0)  # 实现先进先出
                print(node.root, end=' ')
                if node.lchild:
                    stack.append(node.lchild)
                if node.rchild:
                    stack.append(node.rchild)

### 完整代码 ###

class NodeTree:
        def __init__(self, root=None, lchild=None, rchild=None):
            """创建二叉树
            Argument:
                lchild: BinTree
                    左子树
                rchild: BinTree
                    右子树
    
            Return:
                Tree
            """
            self.root = root
            self.lchild = lchild
            self.rchild = rchild
    
    
    class BinTree:
    
        # -----------前序遍历 ------------
        # 递归算法
        def pre_order_recursive(self, T):
            if T == None:
                return
            print(T.root, end=' ')
            self.pre_order_recursive(T.lchild)
            self.pre_order_recursive(T.rchild)
    
        # 非递归算法
        def pre_order_non_recursive(self, T):
            """借助栈实现前驱遍历
            """
            if T == None:
                return
            stack = []
            while T or len(stack) > 0:
                if T:
                    stack.append(T)
                    print(T.root, end=' ')
                    T = T.lchild
                else:
                    T = stack[-1]
                    stack.pop()
                    T = T.rchild
    
        # -----------中序遍历 ------------
        # 递归算法
        def mid_order_recursive(self, T):
            if T == None:
                return
            self.mid_order_recursive(T.lchild)
            print(T.root, end=' ')
            self.mid_order_recursive(T.rchild)
    
        # 非递归算法
        def mid_order_non_recursive(self, T):
            """借助栈实现中序遍历
            """
            if T == None:
                return
            stack = []
            while T or len(stack) > 0:
                if T:
                    stack.append(T)
                    T = T.lchild
                else:
                    T = stack.pop()
                    print(T.root, end=' ')
                    T = T.rchild
    
        # -----------后序遍历 ------------
        # 递归算法
        def post_order_recursive(self, T):
            if T == None:
                return
            self.post_order_recursive(T.lchild)
            self.post_order_recursive(T.rchild)
            print(T.root, end=' ')
    
        # 非递归算法
        def post_order_non_recursive(self, T):
            """借助两个栈实现后序遍历
            """
            if T == None:
                return
            stack1 = []
            stack2 = []
            stack1.append(T)
            while stack1:
                node = stack1.pop()
                if node.lchild:
                    stack1.append(node.lchild)
                if node.rchild:
                    stack1.append(node.rchild)
                stack2.append(node)
            while stack2:
                print(stack2.pop().root, end=' ')
            return
    
        # -----------层次遍历 ------------
        def level_order(self, T):
            """借助队列（其实还是一个栈）实现层次遍历
            """
            if T == None:
                return
            stack = []
            stack.append(T)
            while stack:
                node = stack.pop(0)  # 实现先进先出
                print(node.root, end=' ')
                if node.lchild:
                    stack.append(node.lchild)
                if node.rchild:
                    stack.append(node.rchild)
    
        # ----------- 前序遍历序列、中序遍历序列 —> 重构二叉树 ------------
        def tree_by_pre_mid(self, pre, mid):
            if len(pre) != len(mid) or len(pre) == 0 or len(mid) == 0:
                return
            T = NodeTree(pre[0])
            index = mid.index(pre[0])
            T.lchild = self.tree_by_pre_mid(pre[1:index + 1], mid[:index])
            T.rchild = self.tree_by_pre_mid(pre[index + 1:], mid[index + 1:])
            return T
    
        # ----------- 后序遍历序列、中序遍历序列 —> 重构二叉树 ------------
        def tree_by_post_mid(self, post, mid):
            if len(post) != len(mid) or len(post) == 0 or len(mid) == 0:
                return
            T = NodeTree(post[-1])
            index = mid.index(post[-1])
            T.lchild = self.tree_by_post_mid(post[:index], mid[:index])
            T.rchild = self.tree_by_post_mid(post[index:-1], mid[index + 1:])
            return T
    
    
    if __name__ == '__main__':
        # ----------- 测试：前序、中序、后序、层次遍历 -----------
        # 创建二叉树
        nodeTree = NodeTree(1,
                            lchild=NodeTree(2,
                                            lchild=NodeTree(4,
                                                            rchild=NodeTree(7))),
                            rchild=NodeTree(3,
                                            lchild=NodeTree(5),
                                            rchild=NodeTree(6)))
        T = BinTree()
        print('前序遍历递归\t')
        T.pre_order_recursive(nodeTree)  # 前序遍历-递归
        print('\n')
        print('前序遍历非递归\t')
        T.pre_order_non_recursive(nodeTree)  # 前序遍历-非递归
        print('\n')
        print('中序遍历递归\t')
        T.mid_order_recursive(nodeTree)  # 中序遍历-递归
        print('\n')
        print('中序遍历非递归\t')
        T.mid_order_non_recursive(nodeTree)  # 中序遍历-非递归
        print('\n')
        print('后序遍历递归\t')
        T.post_order_recursive(nodeTree)  # 后序遍历-递归
        print('\n')
        print('后序遍历非递归\t')
        T.post_order_non_recursive(nodeTree)  # 后序遍历-非递归
        print('\n')
        print('层次遍历\t')
        T.level_order(nodeTree)  # 层次遍历
        print('\n')
    
        print('==========================================================================')
    
        # ----------- 测试：由遍历序列构造二叉树 -----------
        T = BinTree()
        pre = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I']
        mid = ['B', 'C', 'A', 'E', 'D', 'G', 'H', 'F', 'I']
        post = ['C', 'B', 'E', 'H', 'G', 'I', 'F', 'D', 'A']
    
        newT_pre_mid = T.tree_by_pre_mid(pre, mid)  # 由前序序列、中序序列构造二叉树
        T.post_order_recursive(newT_pre_mid)  # 获取后序序列
        print('\n')
    
        newT_post_mid = T.tree_by_post_mid(post, mid)  # 由后序序列、中序序列构造二叉树
        T.pre_order_recursive(newT_post_mid)  # 获取前序序列

**运行结果**

前序遍历递归	
    1 2 4 7 3 5 6 
    
    前序遍历非递归	
    1 2 4 7 3 5 6 
    
    中序遍历递归	
    4 7 2 1 5 3 6 
    
    中序遍历非递归	
    4 7 2 1 5 3 6 
    
    后序遍历递归	
    7 4 2 5 6 3 1 
    
    后序遍历非递归	
    7 4 2 5 6 3 1 
    
    层次遍历	
    1 2 3 4 5 6 7 
    
    ==========================================================================
    C B E H G I F D A 
    
    A B C D E F G H I