{"id":277,"date":"2011-09-21T13:27:00","date_gmt":"2011-09-21T05:27:00","guid":{"rendered":"http:\/\/wangkaixuan.tech\/?p=277"},"modified":"2020-06-06T13:29:05","modified_gmt":"2020-06-06T05:29:05","slug":"%e6%95%b0%e6%8d%ae%e7%bb%93%e6%9e%84_%e6%a0%91_%e4%ba%8c%e5%8f%89%e6%a0%91%e7%9a%84%e7%ba%bf%e7%b4%a2%e5%8c%96_c%e5%ae%9e%e7%8e%b0","status":"publish","type":"post","link":"http:\/\/www.wangkaixuan.tech\/?p=277","title":{"rendered":"\u6570\u636e\u7ed3\u6784_\u6811_\u4e8c\u53c9\u6811\u7684\u7ebf\u7d22\u5316_C++\u5b9e\u73b0"},"content":{"rendered":"\n

head.h<\/p>\n\n\n\n

#include<iostream>\n#define LINK 0\/\/\u5b9a\u4e49\u8282\u70b9\u7c7b\u578b\uff1a\u6307\u9488\n#define THREAD 1\/\/\u5b9a\u4e8e\u8282\u70b9\u7c7b\u578b\uff1a\u7ebf\u7d22\nusing namespace std;\n\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\u4e8c\u53c9\u6811\u6811\u8282\u70b9\u7c7b\nclass BitNode\n{\npublic:\n\tBitNode();\n\tchar ch;\n\tBitNode *lchild, *rchild;\n\tint LTag, RTag;\n};\n\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\u4e8c\u53c9\u6811\u8282\u70b9\u7c7b\u7684\u6784\u9020\u51fd\u6570\nBitNode::BitNode()\n{\n\tlchild = rchild = NULL;\n\tLTag = RTag = LINK;\n}\n\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/BiTree_Thread\u7c7b\nclass BiTree_Thread\n{\npublic:\n\tBiTree_Thread();\n\tvoid PreOrderCreatBiTree();\n\tvoid InOrderTraverse_Thread();\nprivate:\n\tvoid ReMove();\n\tvoid InOrderThreading();\n\tvoid InThreading(BitNode*&);\n\tvoid Creat(BitNode*&);\n\tvoid ReMoveBiTree(BitNode*&);\n\tBitNode *root, *pre, *p, *start;\n\tchar ch;\n};\n\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/BiTree_Thread\u7c7b\u7684\u6784\u9020\u51fd\u6570\nBiTree_Thread::BiTree_Thread()\n{\n\troot = pre = p = start = NULL;\n}\n\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\u5148\u5e8f\u5efa\u7acb\u4e8c\u53c9\u6811\u63a5\u53e3\u51fd\u6570\nvoid BiTree_Thread::PreOrderCreatBiTree()\n{\n\tcout << \"PreOrderCreatBiTree Called !\" << endl << endl;\n\tcout << \"Please Input The BiTree In PreOrder :\" << endl << endl;\n\tReMove(); \/\/\u79fb\u9664\u539f\u5148\u7684\u6811\n\tCreat(root); \/\/\u5efa\u7acb\u65b0\u6811\n\tcin.clear(); \/\/\u89e3\u9664cin\u7684\u5f02\u5e38\u72b6\u6001\n}\n\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\u5148\u5e8f\u9012\u5f52\u5efa\u7acb\u4e8c\u53c9\u6811\nvoid BiTree_Thread::Creat(BitNode *&t)\n{\n\tif (cin >> ch)\n\t{\n\t\tif (ch != '#')\n\t\t{\n\t\t\tt = new BitNode; \/\/\u5f00\u8f9f\u65b0\u8282\u70b9\n\t\t\tt->ch = ch;\n\t\t\tCreat(t->lchild); \/\/\u9012\u5f52\u5efa\u7acb\u5176\u5de6\u5b50\u6811\n\t\t\tCreat(t->rchild); \/\/\u9012\u5f52\u5efa\u7acb\u5176\u53f3\u5b50\u6811\n\t\t}\n\t\telse\n\t\t\tt = NULL;\n\t}\n}\n\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\u4e2d\u5e8f\u7ebf\u7d22\u5316\u904d\u5386\u4e8c\u53c9\u6811\u63a5\u53e3\u51fd\u6570\nvoid BiTree_Thread::InOrderTraverse_Thread()\n{\n\tcout << \"InOrderTraverse_Thread Called !\" << endl << endl;\n\tif (root == NULL) \/\/\u82e5\u6811\u7a7a\n\t{\n\t\tcout << \"BiTree Is Empty !\" << endl << endl;\n\t\tPreOrderCreatBiTree(); \/\/\u65b0\u5efa\u4e00\u68f5\u4e8c\u53c9\u6811\n\t}\n\tif (start == NULL) \/\/\u82e5\u672a\u88ab\u7ebf\u7d22\u5316\n\t\tInOrderThreading(); \/\/\u4e2d\u5e8f\u7ebf\u7d22\u5316\n\tp = start->lchild; \/\/p\u8f6c\u5230root\u8282\u70b9\n\twhile (p != start) \/\/\u5faa\u73af\u904d\u5386\u4e4b\n\t{\n\t\twhile (p->LTag == LINK) \/\/\u5982\u679c\u6307\u5411\u5de6\u5b69\u5b50\u7684\u662f\u6307\u9488\n\t\t{\n\t\t\tp = p->lchild; \/\/\u8f6c\u5230\u5176\u5de6\u5b69\u5b50\n\t\t}\n\t\tcout << p->ch << endl; \/\/\u8bbf\u95ee\u8282\u70b9\n\t\twhile (p->RTag == THREAD && p->rchild != start) \/\/\u5f53\u6307\u5411\u53f3\u5b69\u5b50\u7684\u662f\u7ebf\u7d22\u65f6\n\t\t{\n\t\t\tp = p->rchild; \/\/\u8f6c\u5411\u53f3\u5b69\u5b50\n\t\t\tcout << p->ch << endl; \/\/\u8bbf\u95ee\u4e4b\n\t\t}\n\t\tp = p->rchild; \/\/\u8f6c\u5411\u53f3\u5b69\u5b50\n\t}\n}\n\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\u4e2d\u5e8f\u7ebf\u7d22\u5316\u4e3b\u7a0b\u5e8f\nvoid BiTree_Thread::InOrderThreading()\n{\n\tstart = new BitNode; \/\/\u5f00\u8f9f\u4e00\u4e2a\u989d\u5916\u7684\u8282\u70b9\u4f5c\u4e3a\u7ebf\u7d22\u5316\u904d\u5386\u7684\u8d77\u70b9\u548c\u7ec8\u70b9\n\tstart->LTag = LINK; \/\/\u5de6\u6807\u5fd7\u8bbe\u4e3a\u6307\u9488\n\tstart->RTag = THREAD; \/\/\u53f3\u6807\u5fd7\u521d\u59cb\u5316\u4e3a\u7ebf\u7d22\n\tstart->rchild = start; \/\/\u8d77\u70b9\u7684\u53f3\u5b69\u5b50\u56de\u6307\u5411\u5176\u81ea\u8eab\n\tif (root == NULL) \/\/\u82e5\u4e0d\u5b58\u5728\u4e00\u9897\u4e8c\u53c9\u6811\n\t{\n\t\tstart->lchild = start; \/\/\u5de6\u6307\u9488\u56de\u6307\n\t}\n\telse \/\/\u5426\u5219\n\t{\n\t\tstart->lchild = root; \/\/\u8d77\u59cb\u70b9\u6307\u5411\u4e8c\u53c9\u6811\u7684\u6839\u8282\u70b9\n\t\tpre = start; \/\/\u521d\u59cb\u5316pre\u6307\u5411\u8d77\u59cb\u70b9\n\t\tInThreading(root); \/\/\u4ece\u6839\u8282\u70b9\u5f00\u59cb\u7ebf\u7d22\u5316\n\t\tpre->RTag = THREAD; \/\/\u5904\u7406\u7ebf\u7d22\u5316\u7684\u6700\u540e\u4e00\u4e2a\u8282\u70b9\n\t\tpre->rchild = start;\n\t\tstart->rchild = pre;\n\t}\n}\n\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\u4e2d\u5e8f\u7ebf\u7d22\u5316\u9012\u5f52\u90e8\u5206\nvoid BiTree_Thread::InThreading(BitNode *&p)\n{\n\tif (p) \/\/\u82e5\u8282\u70b9\u5b58\u5728\n\t{\n\t\tInThreading(p->lchild); \/\/\u7ebf\u7d22\u5316\u5176\u5de6\u5b50\u6811\n\t\tif (p->lchild == NULL) \/\/\u5904\u7406p\u6307\u5411\u7684\u8282\u70b9\u7684\u524d\u9a71\n\t\t{\n\t\t\tp->LTag = THREAD;\n\t\t\tp->lchild = pre;\n\t\t}\n\t\tif (pre->rchild == NULL) \/\/\u5904\u7406pre\u6307\u5411\u7684\u8282\u70b9\u7684\u540e\u7ee7\n\t\t{\n\t\t\tpre->RTag = THREAD;\n\t\t\tpre->rchild = p;\n\t\t}\n\t\tpre = p; \/\/pre\u7d27\u8ddfp\n\t\tInThreading(p->rchild); \/\/\u7ebf\u7d22\u5316\u5176\u53f3\u5b50\u6811\n\t}\n}\n\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\u79fb\u9664\u4e8c\u53c9\u6811\u4e3b\u8c03\u51fd\u6570\nvoid BiTree_Thread::ReMove()\n{\n\tif (root != NULL) \/\/\u5982\u679c\u6811\u4e0d\u7a7a\n\t{\n\t\tReMoveBiTree(root); \/\/\u79fb\u9664\u6574\u68f5\u6811\n\t\tif (start != NULL) \/\/\u5982\u679c\u5df2\u7ecf\u88ab\u7ebf\u7d22\u5316\n\t\t{\n\t\t\tdelete start; \/\/\u5220\u9664start\u8282\u70b9\n\t\t\tstart = NULL; \/\/\u7f6estart\u4e3aNULL\n\t\t}\n\t\troot = NULL; \/\/\u7f6eroot\u4e3aNULL\n\t}\n}\n\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\u79fb\u9664\u4e8c\u53c9\u6811\u88ab\u8c03\u51fd\u6570\nvoid BiTree_Thread::ReMoveBiTree(BitNode *&t)\n{\n\tif (t != NULL) \/\/\u6b64\u6761\u4ef6\u7528\u4e8e\u672a\u7ebf\u7d22\u5316\u7684\u4e8c\u53c9\u6811\n\t{\n\t\tif (t->LTag != THREAD) \/\/\u6b64\u6761\u4ef6\u7528\u4e8e\u7ebf\u7d22\u5316\u7684\u4e8c\u53c9\u6811\n\t\t\tReMoveBiTree(t->lchild); \/\/\u9012\u5f52\u79fb\u9664\u5176\u5de6\u5b50\u6811\n\t\tif (t->RTag != THREAD) \/\/\u6b64\u6761\u4ef6\u7528\u4e8e\u7ebf\u7d22\u5316\u7684\u4e8c\u53c9\u6811\n\t\t\tReMoveBiTree(t->rchild); \/\/\u9012\u5f52\u79fb\u9664\u5176\u53f3\u5b50\u6811\n\t\tdelete t; \/\/\u5220\u9664\u8282\u70b9\n\t}\n}\n<\/code><\/pre>\n\n\n\n
main.cpp<\/p>\n\n\n\n
#include<iostream>\n#include\"head.h\"\nusing namespace std;\n\nint main()\n{\n\tBiTree_Thread t;\n\tchar choice;\n\twhile (1)\n\t{\n\t\tcout << \"Your Choice , Please ?\" << endl << endl\n\t\t\t\t<< \"1 . PreOrderCreatBiTree\" << endl\n\t\t\t\t<< \"2 . InOrderTraverse_Thread\" << endl << \"9 . Quit\" << endl\n\t\t\t\t<< endl;\n\t\tcin >> choice;\n\t\tswitch (choice)\n\t\t{\n\t\tcase '1':\n\t\t\tt.PreOrderCreatBiTree();\n\t\t\tbreak;\n\t\tcase '2':\n\t\t\tt.InOrderTraverse_Thread();\n\t\t\tbreak;\n\t\tcase '9':\n\t\t\treturn 0;\n\t\t\tbreak;\n\t\tdefault:\n\t\t\tcout << \"No Such Choice !\" << endl << endl;\n\t\t\tbreak;\n\t\t}\n\t}\n\treturn 0;\n}\n<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"
head.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-277","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\/277","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=277"}],"version-history":[{"count":0,"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=\/wp\/v2\/posts\/277\/revisions"}],"wp:attachment":[{"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=277"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=277"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=277"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}