Python - 树遍历

Python - 树遍历 首页 / 数据结构入门教程 / Python - 树遍历

遍历是访问树的所有节点并且也可以打印其值的过程,因为所有节点都是通过边连接的,所以无涯教程总是从根节点开始,也就是说,不能随机访问树中的节点,无涯教程使用三种方式遍历树-

  • 前序遍历
  • 中序遍历
  • 后序遍历

前序遍历

在这种遍历方法中,首先访问左子树,然后访问根,然后再访问右子树。应该永远记住,每个节点都可能代表一个子树本身。

在下面的python程序中,使用Node类为根节点以及左右节点创建占位符,然后,创建一个插入函数以将数据添加到树中,最后,通过创建一个空列表并先添加左节点,然后再添加根节点或父节点来实现有序遍历逻辑,最后,添加左节点以完成顺序遍历。

class Node:

    def __init__(self, data):

        self.left=None
        self.right=None
        self.data=data
# 插入节点
    def insert(self, data):

        if self.data:
            if data < self.data:
                if self.left is None:
                    self.left=Node(data)
                else:
                    self.left.insert(data)
            elif data > self.data:
                if self.right is None:
                    self.right=Node(data)
                else:
                    self.right.insert(data)
        else:
            self.data=data

#打印树
    def PrintTree(self):
        if self.left:
            self.left.PrintTree()
        print( self.data),
        if self.right:
            self.right.PrintTree()

# 中序遍历
# Left -> Root -> Right
    def inorderTraversal(self, root):
        res=[]
        if root:
            res=self.inorderTraversal(root.left)
            res.append(root.data)
            res=res + self.inorderTraversal(root.right)
        return res

root=Node(27)
root.insert(14)
root.insert(35)
root.insert(10)
root.insert(19)
root.insert(31)
root.insert(42)
print(root.inorderTraversal(root))

执行以上代码后,将产生以下输出-

无涯教程网

[10, 14, 19, 27, 31, 35, 42] 

中序遍历

在这种遍历方法中,首先访问根节点,然后是左子树,最后是右子树。

在下面的python程序中,使用Node类为根节点以及左右节点创建占位符,然后,创建一个插入函数以将数据添加到树中, 最后,通过创建一个空列表并先添加根节点,然后再添加左节点来实现预遍历逻辑,最后,添加右节点以完成预遍历。 

class Node:

    def __init__(self, data):

        self.left=None
        self.right=None
        self.data=data
# 插入节点
    def insert(self, data):

        if self.data:
            if data < self.data:
                if self.left is None:
                    self.left=Node(data)
                else:
                    self.left.insert(data)
            elif data > self.data:
                if self.right is None:
                    self.right=Node(data)
                else:
                    self.right.insert(data)
        else:
            self.data=data

# 打印树
    def PrintTree(self):
        if self.left:
            self.left.PrintTree()
        print( self.data),
        if self.right:
            self.right.PrintTree()

#前序遍历
# Root -> Left ->Right
    def PreorderTraversal(self, root):
        res=[]
        if root:
            res.append(root.data)
            res=res + self.PreorderTraversal(root.left)
            res=res + self.PreorderTraversal(root.right)
        return res

root=Node(27)
root.insert(14)
root.insert(35)
root.insert(10)
root.insert(19)
root.insert(31)
root.insert(42)
print(root.PreorderTraversal(root))

执行以上代码后,将产生以下输出-

无涯教程网

[27, 14, 10, 19, 35, 31, 42]

后序遍历

在这种遍历方法中,根节点是最后访问的,首先,无涯教程先遍历左侧子树,然后遍历右侧子树,最后遍历根节点。

在下面的python程序中,使用Node类为根节点以及左右节点创建占位符,然后,创建一个插入函数以将数据添加到树中,最后,通过创建一个空列表并先添加左节点,再添加右节点,实现后遍历逻辑,最后,添加根节点或父节点以完成后顺序遍历。 

class Node:

    def __init__(self, data):

        self.left=None
        self.right=None
        self.data=data
# 插入节点
    def insert(self, data):

        if self.data:
            if data < self.data:
                if self.left is None:
                    self.left=Node(data)
                else:
                    self.left.insert(data)
            elif data > self.data:
                if self.right is None:
                    self.right=Node(data)
                else:
                    self.right.insert(data)
        else:
            self.data=data

# 打印树
    def PrintTree(self):
        if self.left:
            self.left.PrintTree()
        print( self.data),
        if self.right:
            self.right.PrintTree()

# 后序遍历
# Left ->Right -> Root
    def PostorderTraversal(self, root):
        res=[]
        if root:
            res=self.PostorderTraversal(root.left)
            res=res + self.PostorderTraversal(root.right)
            res.append(root.data)
        return res

root=Node(27)
root.insert(14)
root.insert(35)
root.insert(10)
root.insert(19)
root.insert(31)
root.insert(42)
print(root.PostorderTraversal(root))

执行以上代码后,将产生以下输出-

无涯教程网

[10, 19, 14, 31, 42, 35, 27]

祝学习愉快!(内容编辑有误?请选中要编辑内容 -> 右键 -> 修改 -> 提交!)

技术教程推荐

深入浅出区块链 -〔陈浩〕

DevOps实战笔记 -〔石雪峰〕

架构实战案例解析 -〔王庆友〕

MySQL 必知必会 -〔朱晓峰〕

数据分析思维课 -〔郭炜〕

零基础实战机器学习 -〔黄佳〕

徐昊 · TDD项目实战70讲 -〔徐昊〕

运维监控系统实战笔记 -〔秦晓辉〕

AI 应用实战课 -〔黄佳〕

好记忆不如烂笔头。留下您的足迹吧 :)