与你交谈系列#3

from typing import any

class treenode:
    def __init__(self, data: any):
        self.data = data
        self.left = none
        self.right = none

# define all the nodes we need
root = treenode('r')
nodea = treenode('a')
nodeb = treenode('b')
nodec = treenode('c')
noded = treenode('d')

# connect all the nodes between each other
root.left = nodea
root.right = nodeb
nodea.left = nodec
nodea.right = noded

# what we've got
    r
   / \
  a   b
 / \ 
c   d

"""
preorder - is done by visiting the root node first, then recursively do a pre-order traversal of the left subtree, followed by a recursive pre-order traversal of the right subtree.

this traversal is "pre" order because the node is visited "before" the recursive pre-order traversal of the left and right subtrees.
"""

def pre_order(node):
    if node:
        print(node.value)
        pre_order(node.left)
        pre_order(node.right)

"""
postorder - works by recursively doing a post-order traversal of the left subtree and the right subtree, followed by a visit to the root node.

what makes this traversal "post" is that visiting a node is done "after" the left and right child nodes are called recursively.
"""

def post_order(node):
    if node:
        post_order(node.left)
        post_order(node.right)
        print(node.value)

"""
inOrder - does a recursive In-order Traversal of the left subtree, visits the root node, and finally, does a recursive In-order Traversal of the right subtree.

What makes this traversal "in" order, is that the node is visited in between the recursive function calls. The node is visited after the In-order Traversal of the left subtree, and before the In-order Traversal of the right subtree.
"""

def in_order(node):
    if node:
        in_order(node.left)
        print(node.value)
        in_order(node.right)