{"id":289,"date":"2011-11-01T13:52:31","date_gmt":"2011-11-01T05:52:31","guid":{"rendered":"http:\/\/wangkaixuan.tech\/?p=289"},"modified":"2020-06-06T13:53:47","modified_gmt":"2020-06-06T05:53:47","slug":"%e6%95%b0%e6%8d%ae%e7%bb%93%e6%9e%84_%e6%9f%a5%e6%89%be_%e9%9d%99%e6%80%81%e6%9f%a5%e6%89%be%e6%95%b0%e8%a1%a8_%e4%ba%8c%e5%8f%89%e6%8e%92%e5%ba%8f%e6%a0%91","status":"publish","type":"post","link":"http:\/\/www.wangkaixuan.tech\/?p=289","title":{"rendered":"\u6570\u636e\u7ed3\u6784_\u67e5\u627e_\u9759\u6001\u67e5\u627e\u6570\u8868_\u4e8c\u53c9\u6392\u5e8f\u6811"},"content":{"rendered":"\n<p>BinarySortTree.h<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>typedef int ElemType;\n\ntypedef enum\n{\n\tFALSE, TRUE\n} Status;\n\ntypedef struct BitNode\n{\n\tElemType data;\n\tBitNode *lchild, *rchild;\n\tBitNode()\n\t{\n\t\tlchild = rchild = NULL;\n\t}\n} *BiTree;\n\nStatus SearchBST(BiTree T, ElemType key, BiTree f, BiTree &amp;p) \/\/\u67e5\u627e\u5173\u952e\u5b57\n\/\/\u5728\u6839\u6307\u9488T\u6240\u6307\u7684\u4e8c\u53c9\u6392\u5e8f\u6811\u4e2d\u9012\u5f52\u7684\u67e5\u627e\u5176\u5173\u952e\u5b57\u7b49\u4e8ekey\u7684\u6570\u636e\u5143\u7d20\uff0c\u82e5\u67e5\u627e\u6210\u529f\n\/\/\u7528p\u8fd4\u56de\u5143\u7d20\u8282\u70b9\u5e76\u8fd4\u56deTRUE\uff0c\u5426\u5219\u6307\u9488p\u8fd4\u56de\u67e5\u627e\u8def\u5f84\u4e0a\u8bbf\u95ee\u7684\u6700\u540e\u4e00\u8282\u70b9\u5e76\u8fd4\u56deFALSE\n\/\/\u6307\u9488f\u6307\u5411T\u7684\u53cc\u4eb2\uff0c\u5176\u521d\u59cb\u8c03\u7528\u503c\u4e3aNULL\n{\n\tif (T == NULL) \/\/\u67e5\u627e\u4e0d\u6210\u529f\n\t{\n\t\tp = f;\n\t\treturn FALSE;\n\t}\n\telse if (key == T->data) \/\/\u67e5\u627e\u6210\u529f\n\t{\n\t\tp = T;\n\t\treturn TRUE;\n\t}\n\telse if (key &lt; T->data) \/\/\u5de6\u5b50\u6811\u4e2d\u67e5\u627e\n\t\treturn SearchBST(T->lchild, key, T, p);\n\telse\n\t\t\/\/\u53f3\u5b50\u6811\u67e5\u627e\n\t\treturn SearchBST(T->rchild, key, T, p);\n}\n\nStatus InsertBST(BiTree &amp;T, ElemType key)\n\/\/\u4e8c\u53c9\u6392\u5e8f\u6811\u4e2d\u4e0d\u5b58\u5728\u5173\u952e\u5b57\u7b49\u4e8ekey\u7684\u6570\u636e\u5143\u7d20\u65f6,\u63d2\u5165key\u5e76\u8fd4\u56deTRUE\n\/\/\u5426\u5219\u8fd4\u56deFALSE\n{\n\tBiTree p, insert;\n\tif (SearchBST(T, key, NULL, p) == FALSE) \/\/\u67e5\u627e\u4e0d\u6210\u529f\n\t{\n\t\tinsert = new BitNode; \/\/\u5f00\u8f9f\u8282\u70b9\n\t\tinsert->data = key;\n\t\tif (p == NULL) \/\/\u6ca1\u6709\u5143\u7d20\u7684\u60c5\u51b5\n\t\t\tT = insert;\n\t\t\/\/\u5229\u7528SearchBST()\u8fd4\u56de\u7684\u6307\u9488\u5c06\u5176\u7f00\u5728\u76f8\u5e94\u7684\u5b50\u6811\u4e0a\n\t\telse if (key &lt; p->data)\n\t\t\tp->lchild = insert;\n\t\telse\n\t\t\tp->rchild = insert;\n\t\treturn TRUE;\n\t}\n\treturn FALSE;\n}\n\nStatus Delete(BiTree &amp;p)\n\/\/\u4ece\u4e8c\u53c9\u6392\u5e8f\u6811\u4e2d\u5220\u9664\u8282\u70b9p\u5e76\u91cd\u63a5\u5b83\u7684\u5de6\u5b50\u6811\u548c\u53f3\u5b50\u6811\n{\n\tBiTree q, s;\n\tif (p->lchild == NULL) \/\/\u5de6\u5b50\u6811\u7a7a\u91cd\u63a5\u5176\u53f3\u5b50\u6811\n\t{\n\t\tq = p;\n\t\tp = p->rchild;\n\t\tdelete q;\n\t}\n\telse if (p->rchild == NULL) \/\/\u53f3\u5b50\u6811\u7a7a\u91cd\u63a5\u5176\u5de6\u5b50\u6811\n\t{\n\t\tq = p;\n\t\tp = p->lchild;\n\t\tdelete q;\n\t}\n\telse \/\/\u5de6\u53f3\u5b50\u6811\u5747\u975e\u7a7a\n\t{\n\t\tq = p;\n\t\ts = p->lchild;\n\t\twhile (s->rchild != NULL)\n\t\t{\n\t\t\tq = s;\n\t\t\ts = s->rchild;\n\t\t}\n\t\tp->data = s->data;\n\t\tif (q != p)\n\t\t\tq->rchild = s->lchild;\n\t\telse\n\t\t\tq->lchild = s->lchild;\n\t\tdelete s;\n\t}\n\treturn TRUE;\n}\n\nStatus DeleteBST(BiTree &amp;T, ElemType key)\n\/\/\u82e5\u4e8c\u53c9\u6392\u5e8f\u6811T\u4e2d\u5b58\u5728\u5173\u952e\u5b57\u7b49\u4e8ekey\u7684\u6570\u636e\u5143\u7d20\u65f6\uff0c\u5219\u5220\u9664\u8be5\u6570\u636e\u5143\u7d20\u8282\u70b9\u5e76\u8fd4\u56deTRUE\u5426\u5219\u8fd4\u56deFALSE\n{\n\tif (T == NULL) \/\/\u67e5\u627e\u4e0d\u6210\u529f\n\t\treturn FALSE;\n\telse\n\t{\n\t\tif (key == T->data)\n\t\t\treturn Delete(T);\n\t\telse if (key &lt; T->data)\n\t\t\treturn DeleteBST(T->lchild, key);\n\t\telse\n\t\t\treturn DeleteBST(T->rchild, key);\n\t}\n}\n\nStatus TraverseBST(BiTree T)\n{\n\tif (T == NULL)\n\t\treturn FALSE;\n\telse\n\t{\n\t\tcout &lt;&lt; T->data &lt;&lt; endl;\n\t\tTraverseBST(T->lchild);\n\t\tTraverseBST(T->rchild);\n\t}\n}\n<\/code><\/pre>\n\n\n\n<p>main.cpp<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>#include&lt;iostream>\nusing namespace std;\n\n#include\"BinarySortTree.h\"\n\nint main()\n{\n\tBiTree T = NULL;\n\tElemType key;\n\tshort choice;\n\twhile (1)\n\t{\n\t\tsystem(\"cls\");\n\t\tcout &lt;&lt; \"1 . InsertBST()\" &lt;&lt; endl &lt;&lt; \"2 . DeleteBST()\" &lt;&lt; endl\n\t\t\t\t&lt;&lt; \"3 . TraverseBST()\" &lt;&lt; endl;\n\t\tcin >> choice;\n\t\tsystem(\"cls\");\n\t\tswitch (choice)\n\t\t{\n\t\tcase 1:\n\t\t\tcin >> key;\n\t\t\tInsertBST(T, key);\n\t\t\tbreak;\n\t\tcase 2:\n\t\t\tcin >> key;\n\t\t\tDeleteBST(T, key);\n\t\t\tbreak;\n\t\tcase 3:\n\t\t\tTraverseBST(T);\n\t\t\tsystem(\"pause\");\n\t\t\tbreak;\n\t\t}\n\t}\n}\n<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"<p>BinarySortTree.h main.cpp<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[9],"tags":[],"class_list":["post-289","post","type-post","status-publish","format-standard","hentry","category-06-02-"],"_links":{"self":[{"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=\/wp\/v2\/posts\/289","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=289"}],"version-history":[{"count":0,"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=\/wp\/v2\/posts\/289\/revisions"}],"wp:attachment":[{"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=289"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=289"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=289"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}