单链表和二叉树的操作,单链表二叉树操作,#author: Ji
文章由Byrx.net分享于2019-03-23 08:03:11
单链表和二叉树的操作,单链表二叉树操作,#author: Ji
#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)
相关内容
- 批量下载51voa的文本和MP3,51voa文本mp3,[Python]代码My
- 加速器后台程序,,[Python]代码#!
- 快速多线程ping,多线程ping,[Python]代码#!
- 在VIM中使用GOOGLE进行搜索或者翻译,vimgoogle,[Python]代码
- secure crt 脚本,securecrt,[Python]代码#$
- hashlib穷举字典破解md5,sha1,hashlibsha1,初步完工,在U
- python求素数的一句话代码 lambda实现,pythonlambda,#在交互
- 用python计算(1+2+3+4……+100),python,[Python]代码n=
- python修改操作系统时间的代码,python操作系统,#-*- cod
- python根据出生年份计算生肖的代码,python出生年份,#计
评论关闭