[数据结构][Python]实现遍历二叉树(递归和非递归)

落日映苍穹つ 2022-01-22 03:31 219阅读 0赞

class Node(object):
        def __init__(self,value=None,left=None,right=None):
            self.value = value
            self.left = left
            self.right = right
    
    def pre_traverse(root):
        """
        前序遍历
        :param root:
        :return:
        """
        if root == None:
            return
        print(root.value)
        pre_traverse(root.left)
        pre_traverse(root.right)
    
    def mid_traverse(root):
        """
        中序遍历
        :param root:
        :return:
        """
        if root==None:
            return
        mid_traverse(root.left)
        print(root.value)
        mid_traverse(root.right)
    
    def after_traverse(root):
        """
        后序遍历
        :param root:
        :return:
        """
        if root==None:
            return
        after_traverse(root.left)
        after_traverse(root.right)
        print(root.value)
    
    root=Node('D',Node('B',Node('A'),Node('C')),Node('E',right=Node('G',Node('F'))))
    print('前序遍历：')
    pre_traverse(root)
    print('\n')
    print('中序遍历：')
    mid_traverse(root)
    print('\n')
    print('后序遍历：')
    after_traverse(root)
    print('\n')
    
    preList = list('DBACEGF')
    midList = list('ABCDEFG')
    afterList = []
    
    ##一直二叉树前序遍历和中序遍历，求后序遍历
    
    def find_tree(preList, midList, afterList):
        if len(preList) == 0:
            return
        if len(preList) == 1:
            afterList.append(preList[0])
            return
        root = preList[0]
        n = midList.index(root)
        find_tree(preList[1:n + 1], midList[:n], afterList)
        find_tree(preList[n + 1:], midList[n + 1:], afterList)
        afterList.append(root)
    find_tree(preList,midList,afterList)
    print(afterList)

前序遍历：
    D
    B
    A
    C
    E
    G
    F
    
    
    中序遍历：
    A
    B
    C
    D
    E
    F
    G
    
    
    后序遍历：
    A
    C
    B
    F
    G
    E
    D
    
    
    ['A', 'C', 'B', 'F', 'G', 'E', 'D']

非递归

class Tree():
        # 树类
        def __init__(self):
            self.root = Node()
    
        def add(self, data):
            # 为树加入节点
            node = Node(data)
            if self.root.data == -1:  # 如果树为空，就对根节点赋值
                self.root = node
            else:
                my_queue = []
                treeNode = self.root
                my_queue.append(treeNode)
                while my_queue:  # 对已有的节点进行层次遍历
                    treeNode = my_queue.pop(0)
                    if not treeNode.left:
                        treeNode.left = node
                        return
                    elif not treeNode.right:
                        treeNode.right = node
                        return
                    else:
                        my_queue.append(treeNode.left)
                        my_queue.append(treeNode.right)
    
        def pre_order_stack(self, root):  # 堆栈实现前序遍历（非递归）
            if not root:
                return
            myStack = []
            node = root
            while myStack or node:
                while node:  # 从根节点开始，一直寻找他的左子树
                    print(node.data)
                    myStack.append(node)
                    node = node.left
                node = myStack.pop()  # while结束表示当前节点node为空，即前一个节点没有左子树了
                node = node.right  # 开始查看它的右子树
    
        def in_order_stack(self, root):  # 堆栈实现中序遍历（非递归）
            if not root:
                return
            myStack = []
            node = root
            while myStack or node:  # 从根节点开始，一直寻找它的左子树
                while node:
                    myStack.append(node)
                    node = node.left
                node = myStack.pop()
                print(node.data)
                node = node.right
    
        def post_order_stack(self, root):  # 堆栈实现后序遍历（非递归）
            # 先遍历根节点，再遍历右子树，最后是左子树，这样就可以转化为和先序遍历一个类型了，最后只把遍历结果逆序输出就OK了。
            if not root:
                return
            myStack1 = []
            myStack2 = []
            node = root
            while myStack1 or node:
                while node:
                    myStack2.append(node)
                    myStack1.append(node)
                    node = node.right
                node = myStack1.pop()
                node = node.left
            while myStack2:
                print(myStack2.pop().data)
    
    
    datas = [2, 3, 4, 5, 6, 7, 8, 9]
    tree = Tree()  # 新建一个树对象
    for data in datas:
        tree.add(data)  # 逐个加入树的节点