遍历是访问树的所有节点并且也可以打印其值的过程,因为所有节点都是通过边连接的,所以无涯教程总是从根节点开始,也就是说,不能随机访问树中的节点,无涯教程使用三种方式遍历树-
在这种遍历方法中,首先访问左子树,然后访问根,然后再访问右子树。应该永远记住,每个节点都可能代表一个子树本身。
在下面的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]
祝学习愉快!(内容编辑有误?请选中要编辑内容 -> 右键 -> 修改 -> 提交!)