三种二叉树遍历的算法（python实现）

刺骨的言语ヽ痛彻心扉 2022-05-19 07:40 160阅读 0赞

前序遍历（根节点-左孩子，右孩子）

#前序遍历
    class TreeNode:
        def __init__(self, x):
            self.val = x
            self.left = None
            self.right = None
    class Solution:
        def __init__(self):
            self.X = [] #按顺序储存节点的列表
        def qianxu(self,phead):
            root = phead
            # 终止判定
            if root != None:
                # 添加每一步根节点
                self.X.append(root.val)
                # 先向左搜寻
                left = root.left
                self.qianxu(left)
                # 再向右搜寻
                right = root.right
                self.qianxu(right)
            return self.X
    S = Solution()
    a1 = TreeNode(10)
    a2 = TreeNode(5)
    a3 = TreeNode(12)
    a4 = TreeNode(4)
    a5 = TreeNode(7)
    a1.left = a2
    a1.right = a3
    a2.left = a4
    a2.right = a5
    S.qianxu(a1)

中序遍历（左孩子-根节点-右孩子）

#中序遍历
    class TreeNode:
        def __init__(self, x):
            self.val = x
            self.left = None
            self.right = None
    class Solution:
        def __init__(self):
            self.X = [] # 储存遍历结果
            self.Y = [] # 储存运行到当前节点，经过的节点
        def zhongxu(self,phead):
            root = phead
            # 往左搜索到最左边一个
            while root != None:
                self.Y.append(root)
                root = root.left
            if len(self.Y) != 0:
                # 将经过节点列表的最后一个提取出来
                R = self.Y.pop(-1)
                # 将最后一个节点提取出来并保存
                self.X.append(R.val)
                root = R.right
                # 对该节点的右孩子进行访问
                # 如果没有右孩子，则直接访问它之前经过的节点
                # 如果有右孩子，则访问右孩子，并将右孩子当做下一步的根节点，递归，直到右子树完成搜索后，才开始回溯该节点的上一个
                self.zhongxu(root)
            return self.X
    S = Solution()
    a1 = TreeNode(10)
    a2 = TreeNode(5)
    a3 = TreeNode(12)
    a4 = TreeNode(4)
    a5 = TreeNode(7)
    a1.left = a2
    a1.right = a3
    a3.left = a4
    a3.right = a5
    S.zhongxu(a1)

后序遍历（左孩子-右孩子-父节点）

#后序遍历
    class TreeNode:
        def __init__(self, x):
            self.val = x
            self.left = None
            self.right = None
    class Solution:
        def __init__(self):
            self.X = [] #储存当前经历过的节点
            self.Y = [] #储存遍历结果
            self.pre = None #储存上一步的节点
        def houxu(self,phead):
            root = phead
            # 一直搜索到最左的节点
            while root!=None:
                self.X.append(root)
                root = root.left
            if len(self.X) != 0:
                # 提取的最后一个节点
                R = self.X[-1]
                # 如果当前节点的右孩子是空的，或者当前节点的右孩子是之前刚提取保存的节点
                # 两种情况分别是：叶节点，上一个节点已经遍历完右孩子
                if R.right == None or R.right == self.pre:
                    # 将该节点保存为上一个节点
                    self.pre = R
                    # 提取该节点
                    t = self.X.pop(-1)
                    # 保存该节点
                    self.Y.append(t.val)
                    # 这里需要注意：因此下一步需要提取上一层节点，所以这里传进去空字符，然后就会直接提取X的最后一个（上层节点）
                    self.houxu(None)   
                # 如果当前节点有未遍历的右孩子
                elif R.right != None:
                    self.pre = R
                    # 对右孩子进行递归（注意这里不能删去父节点）
                    self.houxu(R.right)
            return self.Y
    S = Solution()
    a1 = TreeNode(10)
    a2 = TreeNode(5)
    a3 = TreeNode(12)
    a4 = TreeNode(4)
    a5 = TreeNode(7)
    a1.left = a2
    a1.right = a3
    a3.left = a4
    a3.right = a5
    S.houxu(a1)