{"id":335,"date":"2016-12-12T21:34:40","date_gmt":"2016-12-12T13:34:40","guid":{"rendered":"http:\/\/blog.messi.moe\/?p=335"},"modified":"2016-12-12T21:34:40","modified_gmt":"2016-12-12T13:34:40","slug":"traversal-of-binary-tree","status":"publish","type":"post","link":"https:\/\/blog.messi.moe\/?p=335","title":{"rendered":"Traversal of Binary Tree"},"content":{"rendered":"<pre><code class=\"python\">class TreeNode(object):\n  value=None\n  lchild=None \n  rchild=None\n  visited=0\n  def __init__(self):\n    value=None\n    lchild=None \n    rchild=None \n    visited=0\n  def visit(self):\n    print self.value,\n    visited=1\n\nclass Queue(object):\n  items=[]\n  size=0\n  def __init__(self):\n    items=[]\n    size=0\n  def head(self):\n    if self.items!=[]:\n      return self.items[0]\n  def inqueue(self,item):\n    self.items.append(item)\n    self.size=len(self.items)\n  def outqueue(self):\n    for i in range(len(self.items)-1):\n      self.items[i]=self.items[i+1]\n    self.items.pop()\n    self.size=len(self.items)\n\ndef preOrder(root):\n  if root:\n    root.visit()\n    preOrder(root.lchild)\n    preOrder(root.rchild)\n\ndef postOrder(root):\n  if root:\n    preOrder(root.lchild)\n    preOrder(root.rchild)\n    root.visit()\n\ndef inOrder(root):\n  if root:\n    inOrder(root.lchild)\n    root.visit()\n    inOrder(root.rchild)\n\ndef DFS(root):\n  if root:\n    root.visited=1\n    print root.value,\n    if root.lchild:\n      if root.lchild.visited==0:\n        DFS(root.lchild)\n    if root.rchild:\n      if root.rchild.visited==0:\n        DFS(root.rchild)\n\ndef DFS2(root):\n  # Non-recurrsive\n  # Use a stack\n  s=[]\n  if root:\n    s.append(root)\n  while(s!=[]):\n    node=s[len(s)-1]\n    print node.value,\n    s.pop()\n    if node.rchild:\n      s.append(node.rchild)\n    if node.lchild:\n      s.append(node.lchild)\n  print \"\"\n\ndef BFS(root):\n  if root:\n    if root.visited==0:\n      root.visited=1\n      print root.value,\n    if root.lchild:\n      if root.lchild.visited==0:\n        root.lchild.visited=1\n        print root.lchild.value,\n    if root.rchild:\n      if root.rchild.visited==0:\n        root.rchild.visited=1\n        print root.rchild.value,\n    if root.lchild:\n      BFS(root.lchild)\n    if root.rchild:\n      BFS(root.rchild)\n\n\ndef BFS2(root):\n  # Non-recurrsive\n  # Use a quene\n  q=Queue()\n  if root:\n    q.inqueue(root)\n  while(q.size!=0):\n    node=q.head()\n    print node.value,\n    q.outqueue()\n    if node.lchild:\n      q.inqueue(node.lchild)\n    if node.rchild:\n      q.inqueue(node.rchild)\n  print \"\"\n\nA=TreeNode()\nB=TreeNode()\nC=TreeNode()\nD=TreeNode()\nE=TreeNode()\nF=TreeNode()\nA.value='A'\nB.value='B'\nC.value='C'\nD.value='D'\nE.value='E'\nF.value='F'\n\nA.lchild=B \nB.lchild=D \nA.rchild=C \nC.lchild=E \nC.rchild=F \n\nDFS2(A)\nBFS2(A)\n<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"<pre><code class=\"python\">class TreeNode(object):\n  value=None\n  lchild=None \n  rchild=None\n  visited=0\n  def __init__(self):\n    value=None\n    lchild=None \n    rchild=None \n    visited=0\n  def visit(self):\n    print self.value,\n    visited=1\n\nclass Queue(object):\n  items=[]\n  size=0\n  def __init__(self):\n    items=[]\n    size=0\n  def head(self):\n    if self.items!=[]:\n      return self.items[0]\n  def inqueue(self,item):\n    self.items.append(item)\n    self.size=len(self.items)\n  def outqueue(self):\n    for i in range(len(self.items)-1):\n      self.items[i]=self.items[i+1]\n    self.items.pop()\n    self.size=len(self.items)\n\ndef preOrder(root):\n  if root:\n    root.visit()\n    preOrder(root.lchild)\n    preOrder(root.rchild)\n\ndef postOrder(root):\n  if root:\n    preOrder(root.lchild)\n    preOrder(root.rchild)\n    root.visit()\n\ndef inOrder(root):\n  if root:\n    inOrder(root.lchild)\n    root.visit()\n    inOrder(root.rchild)\n\ndef DFS(root):\n  if root:\n    root.visited=1\n    print root.value,\n    if root.lchild:\n      if root.lchild.visited==0:\n        DFS(root.lchild)\n    if root.rchild:\n      if root.rchild.visited==0:\n        DFS(root.rchild)\n\ndef DFS2(root):\n  # Non-recurrsive\n  # Use a stack\n  s=[]\n  if root:\n    s.append(root)\n  while(s!=[]):\n    node=s[len(s)-1]\n    print node.value,\n    s.pop()\n    if node.rchild:\n      s.append(node.rchild)\n    if node.lchild:\n      s.append(node.lchild)\n  print \"\"\n\ndef BFS(root):\n  if root:\n    if root.visited==0:\n      root.visited=1\n      print root.value,\n    if root.lchild:\n      if root.lchild.visited==0:\n        root.lchild.visited=1\n        print root.lchild.value,\n    if root.rchild:\n      if root.rchild.visited==0:\n        root.rchild.visited=1\n        print root.rchild.value,\n    if root.lchild:\n      BFS(root.lchild)\n    if root.rchild:\n      BFS(root.rchild)\n\n\ndef BFS2(root):\n  # Non-recurrsive\n  # Use a quene\n  q=Queue()\n  if root:\n    q.inqueue(root)\n  while(q.size!=0):\n    node=q.head()\n    print node.value,\n    q.outqueue()\n    if node.lchild:\n      q.inqueue(node.lchild)\n    if node.rchild:\n      q.inqueue(node.rchild)\n  print \"\"\n\nA=TreeNode()\nB=TreeNode()\nC=TreeNode()\nD=TreeNode()\nE=TreeNode()\nF=TreeNode()\nA.value='A'\nB.value='B'\nC.value='C'\nD.value='D'\nE.value='E'\nF.value='F'\n\nA.lchild=B \nB.lchild=D \nA.rchild=C \nC.lchild=E \nC.rchild=F \n\nDFS2(A)\nBFS2(A)\n<\/code><\/pre>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[1],"tags":[],"_links":{"self":[{"href":"https:\/\/blog.messi.moe\/index.php?rest_route=\/wp\/v2\/posts\/335"}],"collection":[{"href":"https:\/\/blog.messi.moe\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blog.messi.moe\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blog.messi.moe\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/blog.messi.moe\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=335"}],"version-history":[{"count":1,"href":"https:\/\/blog.messi.moe\/index.php?rest_route=\/wp\/v2\/posts\/335\/revisions"}],"predecessor-version":[{"id":336,"href":"https:\/\/blog.messi.moe\/index.php?rest_route=\/wp\/v2\/posts\/335\/revisions\/336"}],"wp:attachment":[{"href":"https:\/\/blog.messi.moe\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=335"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.messi.moe\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=335"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.messi.moe\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=335"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}