Python 二叉树练习

Python 二叉树练习

 

class Node:

    def __init__(self, data = None, left = None, right = None):

        self.data = data

        self.left = left

        self.right = right

class BTree:

    def __init__(self, root = None):

        self.root = root

    def traverse(self, visit):

        def tr(node, visit):

            if node:                       

                tr(node.left, visit)                   

                tr(node.right, visit)

                visit(node.data)               

 

        def tr1(node, visit):

            stack = []

            while len(stack) > 0 or node:

                if node:                           

                    stack.append(node)                     

                    node = node.left

                else:

                    node = stack.pop() 

                    visit(node.data)

                    node = node.right                  

 

        def tr2(node, visit):

            pre = None

            stack = []

            while len(stack) > 0 or node:

                while node:                        

                    stack.append(node)                     

                    node = node.left

                node = stack.pop()

                if node.right == None or node.right == pre:

                    visit(node.data)

                    pre = node

                    node = None

                else:

                    stack.append(node)

                    node = node.right

 

 

        tr(self.root, visit)

        print("*******************")

        tr2(self.root, visit)

 

t = BTree(Node("ROOT", Node("Left", Node("left-left"), Node("left-right")), Node("Right", Node("right-left"), Node("right-right"))))

t.traverse(print)

 摘自 lqefn的专栏