Using Python to implement tree traversal algorithm and type of tree traversal

树遍历意味着访问树中的每个节点。和线性数据结构单一的遍历方式不同，二叉树是分层式数据结构可以以不同的方式遍历。

树遍历结构特点

1、每个树的节点都承载一个数据

2、每个树下都有2个子树

树遍历有三种类型

1、中序遍历

先遍历左子树所有节点，在是根节点，最后访问右子树所有节点。

2、前序遍历

先遍历根节点，再访问左子树中的所有节点，最后访问右子树中的所有节点。

3、后序遍历

先访问左子树中的所有节点，再访问右子树中的所有节点，最后访问根节点。

Python实现树遍历

class Node:
   def __init__(self,item):
        self.left=None
        self.right=None
        self.val=item
#中序遍历
def inorder(root):
   if root:
        inorder(root.left)
        print(str(root.val)+"->",end='')
        inorder(root.right)
#前序遍历
def postorder(root):
   if root:
        postorder(root.left)
        postorder(root.right)
        print(str(root.val)+"->",end='')
#后序遍历
def preorder(root):
   if root:
        print(str(root.val)+"->",end='')
        preorder(root.left)
        preorder(root.right)
root=Node(1)
root.left=Node(2)
root.right=Node(3)
root.left.left=Node(4)
root.left.right=Node(5)
print("中序遍历")
inorder(root)
print("前序遍历")
preorder(root)
print("后序遍历")
postorder(root)

The above is the detailed content of Using Python to implement tree traversal algorithm and type of tree traversal. For more information, please follow other related articles on the PHP Chinese website!