{"id":360,"date":"2016-12-28T21:52:52","date_gmt":"2016-12-28T13:52:52","guid":{"rendered":"http:\/\/blog.messi.moe\/?p=360"},"modified":"2016-12-28T21:52:52","modified_gmt":"2016-12-28T13:52:52","slug":"binary-tree","status":"publish","type":"post","link":"https:\/\/blog.messi.moe\/?p=360","title":{"rendered":"Binary Tree"},"content":{"rendered":"<pre><code class=\"python\">class Node:\n    value=0\n    lchild=None\n    rchild=None\n    p=None \n    def __init__(self):\n        value=0\n        lchild=None\n        rchild=None\n        p=None  \n    def visit(self):\n        print self.value\n\ndef TreeSearch(root,k):\n    if root==None or k==root.value:\n        return root \n    if k&lt;root.value:\n        return TreeSearch(root.lchild, k)\n    else:\n        return TreeSearch(root.rchild, k)\n\ndef IterativeTreeSearch(root,k):\n    while root!=None and k!=root.value:\n        if k&lt;root.value:\n            root=root.lchild \n        else:\n            root=root.rchild \n    return root \n\ndef PreOrder(root):\n    if root:\n        PreOrder(root.lchild)\n        print root.value \n        PreOrder(root.rchild)\n\ndef TreeMin(root):\n    while root.lchild!=None:\n        root=root.lchild \n    return root \n\ndef TreeMax(root):\n    while root.rchild!=None:\n        root=root.rchild\n    return root \n\ndef TreeSuccessor(root):\n    if root.rchild!=None:\n        return TreeMin(root.rchild)\n    y=root.p\n    while (y!=None and root==y.right):\n        root=y \n        y=y.p\n    return y \n\ndef TreeInsert(root,z):\n    y=None \n    while root!=None:\n        y=root \n        if root.value&gt;z.value:\n            root=root.lchild \n        else:\n            root=root.rchild \n    z.p=y \n    if y==None:\n        root=z \n    else:\n        if z.value&lt;y.value:\n            y.lchild=z \n        else:\n            y.rchild=z \n\ndef Transplant(root,u,v):\n    if u.p==None:\n        root=v \n    else:\n        if u==u.p.lchild:\n            u.p.lchild=v \n        else:\n            u.p.lchild=v\n    if v!=None:\n        v.p=u.p \n    v.lchild=u.lchild \n    v.rchild=u.rchild \n    if u.lchild!=None:\n        u.lchild.p=v \n    if u.rchild!=None:\n        u.rchild.p=v\n\nA=Node()\nB=Node()\nC=Node()\nD=Node()\nE=Node()\nF=Node()\nA.value=6\nB.value=5\nC.value=2\nD.value=5\nE.value=7\nF.value=8\nA.lchild=B \nB.lchild=C \nB.rchild=D \nA.rchild=E \nE.rchild=F \nB.p=A \nC.p=B \nD.p=B \nE.p=A \nF.p=E \nprint TreeSearch(A, 7)\nprint IterativeTreeSearch(A, 7)\nprint TreeSuccessor(A)\nG=Node()\nG.value=10\nTreeInsert(A, G)\nPreOrder(A)\n<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"<pre><code class=\"python\">class Node:\n    value=0\n    lchild=None\n    rchild=None\n    p=None \n    def __init__(self):\n        value=0\n        lchild=None\n        rchild=None\n        p=None  \n    def visit(self):\n        print self.value\n\ndef TreeSearch(root,k):\n    if root==None or k==root.value:\n        return root \n    if k&lt;root.value:\n        return TreeSearch(root.lchild, k)\n    else:\n        return TreeSearch(root.rchild, k)\n\ndef IterativeTreeSearch(root,k):\n    while root!=None and k!=root.value:\n        if k&lt;root.value:\n            root=root.lchild \n        else:\n            root=root.rchild \n    return root \n\ndef PreOrder(root):\n    if root:\n        PreOrder(root.lchild)\n        print root.value \n        PreOrder(root.rchild)\n\ndef TreeMin(root):\n    while root.lchild!=None:\n        root=root.lchild \n    return root \n\ndef TreeMax(root):\n    while root.rchild!=None:\n        root=root.rchild\n    return root \n\ndef TreeSuccessor(root):\n    if root.rchild!=None:\n        return TreeMin(root.rchild)\n    y=root.p\n    while (y!=None and root==y.right):\n        root=y \n        y=y.p\n    return y \n\ndef TreeInsert(root,z):\n    y=None \n    while root!=None:\n        y=root \n        if root.value&gt;z.value:\n            root=root.lchild \n        else:\n            root=root.rchild \n    z.p=y \n    if y==None:\n        root=z \n    else:\n        if z.value&lt;y.value:\n            y.lchild=z \n        else:\n            y.rchild=z \n\ndef Transplant(root,u,v):\n    if u.p==None:\n        root=v \n    else:\n        if u==u.p.lchild:\n            u.p.lchild=v \n        else:\n            u.p.lchild=v\n    if v!=None:\n        v.p=u.p \n    v.lchild=u.lchild \n    v.rchild=u.rchild \n    if u.lchild!=None:\n        u.lchild.p=v \n    if u.rchild!=None:\n        u.rchild.p=v\n\nA=Node()\nB=Node()\nC=Node()\nD=Node()\nE=Node()\nF=Node()\nA.value=6\nB.value=5\nC.value=2\nD.value=5\nE.value=7\nF.value=8\nA.lchild=B \nB.lchild=C \nB.rchild=D \nA.rchild=E \nE.rchild=F \nB.p=A \nC.p=B \nD.p=B \nE.p=A \nF.p=E \nprint TreeSearch(A, 7)\nprint IterativeTreeSearch(A, 7)\nprint TreeSuccessor(A)\nG=Node()\nG.value=10\nTreeInsert(A, G)\nPreOrder(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\/360"}],"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=360"}],"version-history":[{"count":1,"href":"https:\/\/blog.messi.moe\/index.php?rest_route=\/wp\/v2\/posts\/360\/revisions"}],"predecessor-version":[{"id":361,"href":"https:\/\/blog.messi.moe\/index.php?rest_route=\/wp\/v2\/posts\/360\/revisions\/361"}],"wp:attachment":[{"href":"https:\/\/blog.messi.moe\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=360"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.messi.moe\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=360"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.messi.moe\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=360"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}