单链表和二叉树的操作，单链表二叉树操作,#author: Jia

单链表和二叉树的操作，单链表二叉树操作,#author: Jia

#author: Jiang Hongfei <jianghongfei@gmail.com>class Node:    """Base Node type"""    Value = None    def __init__(self, value):        self.Value = value    def __str__(self):        return "Value = %s" % self.Valueclass Snode(Node):    """Node type in a singly link"""    Next = Noneclass Tnode(Node):    """Node type in a binary tree"""    Lchild = None    Rchild = None    def __str__(self):        return str(self.Value)def sprint(head):    """Print the Singly link consist by Snode instance"""    while head != None:        print(head)        head = head.Nextdef Reverse(head):    """Reverse a single list"""    newHead = None    while head != None:        temp = head        head = head.next        temp.next = newHead        newHead = temp    return newHeaddef createSinglyLink(start, end):    """Create a singly link, start from 'start', end with 'end'"""    head = p = Snode(start)    for i in range(start + 1, end):        p.Next = Snode(i)        p = p.Next    return headdef InOrderTraverse(head):    """Inorder to traverse a binary tree"""    p = head    stack = []    while p != None or len(stack) > 0:        if p != None:            stack.append(p)            p = p.Lchild        else:            p = stack.pop()            print(p)            p = p.Rchilddef PreOrderTraverse(head):    """Preorder to traverse a binary tree"""    p = head    stack = []    while p != None or len(stack) > 0:        if p != None:            print(p)            stack.append(p)            p = p.Lchild        else:            p = stack.pop()            p = p.Rchilddef PostOrderTraverse(head):    """Postorder to traverse a binary tree"""    p = head    stack = []    while p != None or len(stack) > 0:        if p != None:            stack.append(p)            p = p.Lchild        else:            while len(stack) > 0 and p == stack[-1].Rchild:                p = stack.pop()                print(p)            if len(stack) > 0:                p = stack[-1].Rchild            else:                p = None  def LevelTraverse(head):    """Level traverse a binary tree"""    stack = [head]    while len(stack) > 0:        p = stack.pop(0)        print(p)        if p.Lchild != None:            stack.append(p.Lchild)        if p.Rchild != None:            stack.append(p.Rchild)def CreateBinaryTree():    head = Tnode("-")    head.Lchild = Tnode("+")    head.Lchild.Lchild = Tnode("a")    head.Lchild.Rchild = Tnode("*")    head.Lchild.Rchild.Lchild = Tnode("b")    head.Lchild.Rchild.Rchild = Tnode("-")    head.Lchild.Rchild.Rchild.Lchild = Tnode("c")    head.Lchild.Rchild.Rchild.Rchild = Tnode("d")    head.Rchild = Tnode("/")    head.Rchild.Lchild = Tnode("e")    head.Rchild.Rchild = Tnode("f")    return headdef CreateTree():    head = Tnode(1)    head.Lchild = Tnode(2)    head.Rchild = Tnode(3)    head.Lchild.Lchild = Tnode(4)    head.Lchild.Rchild = Tnode(5)    head.Rchild.Lchild = Tnode(6)    head.Rchild.Rchild = Tnode(7)    head.Lchild.Lchild.Lchild = Tnode(8)    head.Lchild.Lchild.Rchild = Tnode(9)    head.Rchild.Lchild.Lchild = Tnode(10)    head.Rchild.Lchild.Rchild = Tnode(11)    return headif __name__ == '__main__':    head = CreateTree()    print('Pre traverse:')    PreOrderTraverse(head)    print('InOrderTraverse:')    InOrderTraverse(head)    print('Post Order Tranverse')    PostOrderTraverse(head)    print('level traverse:')    LevelTraverse(head)#该片段来自于http://byrx.net