python单链表、二叉树的操作方法面试题,python单链,class Node:
python单链表、二叉树的操作方法面试题,python单链,class Node:
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 head if __name__ == '__main__': head = CreateTree() print('Pre traverse:') PreOrderTraverse(head) print('InOrderTraverse:') InOrderTraverse(head) print('Post Order Tranverse') PostOrderTraverse(head) print('level traverse:') LevelTraverse(head)
编橙之家文章,
相关内容
- python多线程测试hosts主机操作,pythonhosts,python多线程测
- python方法实现短网址的代码,python实现代码,python方法实
- PyQt写的浏览单web页面的browser,pyqtbrowser,Python PyQt写
- python遍历数据库表及其相关表操作,python数据库,pytho
- python方法恢复整理修改过java包,pythonjava,python方法恢复
- python子网掩码格式转换工具源代码,python子网掩码,py
- 用Python方法对Cursor进行扩展,pythoncursor扩展,用Python方法
- 最简易的python计算器实现源代码,python计算器源代码
- tornado web url路由配置扩展,tornadourl,tornado web
- 教你用python随机生成固定长度字符串的方法,python字符
评论关闭