![\"img\"](\"https:\/\/picture.chentaiyang.space\/202304251440546.jpeg\")
<\/p>\n<\/p>\n
<\/p>\n
\u6811(Tree)\u662f n(n\u22650) \u4e2a\u7ed3\u70b9\u7684\u6709\u9650\u96c6<\/p>\n
![\"img\"](\"https:\/\/picture.chentaiyang.space\/202304251440550.png\")
<\/p>\n
<\/p>\n
![\"img\"](\"https:\/\/picture.chentaiyang.space\/202304251440555.png\")
<\/p>\n
<\/p>\n
\u6709\u5e8f\u6811\uff1a\u6811\u4e2d\u7ed3\u70b9\u7684\u5404\u5b50\u6811\u4ece\u5de6\u81f3\u53f3\u6709\u6b21\u5e8f\uff08\u6700\u5de6\u8fb9\u7684\u4e3a\u7b2c\u4e00\u4e2a\u5b69\u5b50\uff09<\/p>\n
\u65e0\u5e8f\u6811\uff1a\u6811\u4e2d\u7ed3\u70b9\u7684\u5404\u5b50\u6811\u65e0\u6b21\u5e8f<\/p>\n
![\"img\"](\"https:\/\/picture.chentaiyang.space\/202304251440553.png\")
<\/p>\n
<\/p>\n
\u68ee\u6797\uff1a<\/p>\n
\u6811\u4e00\u5b9a\u662f\u68ee\u6797\uff0c\u68ee\u6797\u4e0d\u4e00\u5b9a\u662f\u6811<\/p>\n
<\/p>\n
\u4e8c\u53c9\u6811\u7684\u7ed3\u6784\u6700\u7b80\u5355\uff0c\u89c4\u5f8b\u6027\u6700\u5f3a\uff1b\u6240\u6709\u6811\u90fd\u80fd\u8f6c\u4e3a\u552f\u4e00\u5bf9\u5e94\u7684\u4e8c\u53c9\u6811\uff0c\u4e0d\u5931\u4e00\u822c\u6027\uff1b\u666e\u901a\u6811\uff08\u591a\u53c9\u6811\uff09\u82e5\u4e0d\u8f6c\u5316\u4e3a\u4e8c\u53c9\u6811\uff0c\u5219\u8fd0\u7b97\u5f88\u96be\u5b9e\u73b0<\/p>\n
<\/p>\n
\u4e8c\u53c9\u6811\u662f n(\u22650) \u4e2a\u7ed3\u70b9\u7684\u6709\u9650\u96c6\uff0c\u5b83\u6216\u8005\u662f\u7a7a\u96c6 (n = 0)\uff0c\u6216\u8005\u7531\u4e00\u4e2a\u6839\u8282\u70b9\u53ca\u4e24\u68f5\u4e92\u4e0d\u76f8\u4ea4\u7684\u5206\u522b\u79f0\u4f5c\u8fd9\u4e2a\u6839\u7684\u5de6\u5b50\u6811\u548c\u53f3\u5b50\u6811\u7684\u4e8c\u53c9\u6811\u7ec4\u6210<\/p>\n
<\/p>\n
\u7279\u70b9\uff1a<\/p>\n
<\/p>\n
\u6ce8\uff1a\u4e8c\u53c9\u6811\u4e0d\u662f<\/strong>\u6811\u7684\u7279\u6b8a\u60c5\u51b5\uff0c\u5b83\u4eec\u662f\u4e24\u4e2a\u6982\u5ff5<\/p>\n \u5177\u6709\u4e24\u4e2a\u7ed3\u70b9\u7684\u4e8c\u53c9\u6811\u6709\u4e24\u79cd\u72b6\u6001<\/p>\n <\/p>\n \u5177\u6709\u4e24\u4e2a\u7ed3\u70b9\u7684\u6811\u53ea\u6709\u4e00\u79cd\u72b6\u6001<\/p>\n \u5373\u4e8c\u53c9\u6811\u7684\u6bcf\u4e2a\u7ed3\u70b9\u7684\u4f4d\u7f6e\u6216\u8005\u8bf4\u6b21\u5e8f\u90fd\u662f\u56fa\u5b9a\u7684\uff0c\u53ef\u4ee5\u662f\u7a7a\uff0c\u4f46\u662f\u4e0d\u53ef\u4ee5\u8bf4\u5b83\u6ca1\u6709\u4f4d\u7f6e\uff0c\u800c\u6811\u7684\u7ed3\u70b9\u4f4d\u7f6e\u662f\u76f8\u5bf9\u4e8e\u522b\u7684\u7ed3\u70b9\u6765\u8bf4\uff0c\u6ca1\u6709\u522b\u7684\u7ed3\u70b9\u65f6\uff0c\u5b83\u5c31\u65e0\u6240\u8c13\u5de6\u53f3\u4e86<\/p>\n <\/p>\n <\/p>\n \u5c06\u6570\u636e\u6587\u4ef6\u8f6c\u6362\u6210\u7531 0\u30011\u7ec4\u6210\u7684\u4e8c\u8fdb\u5236\u4e32\uff0c\u79f0\u4e4b\u4e3a\u7f16\u7801<\/p>\n <\/p>\n \u4ee5\u4e8c\u53c9\u6811\u8868\u793a\u8868\u8fbe\u5f0f\u7684\u9012\u5f52\u5b9a\u4e49\u5982\u4e0b\uff1a<\/p>\n \u7136\u540e\u5bf9\u4e8c\u53c9\u6811\u8fdb\u884c\u540e\u5e8f\u904d\u5386<\/strong><\/p>\n <\/p>\n <\/p>\n \u57fa\u672c\u64cd\u4f5c\uff1a<\/p>\n CreateBinaryTree(&T, definition)<\/p>\n <\/p>\n PreOrderTraverse(T)<\/p>\n <\/p>\n InorderTraverse(T)<\/p>\n <\/p>\n PostOrderTraverse(T)<\/p>\n <\/p>\n \u6027\u8d281\uff1a\u5728\u4e8c\u53c9\u6811\u7684\u7b2c i \u5c42\u4e0a\u81f3\u591a\u6709 2^(i-1) \u4e2a\u7ed3\u70b9 ( i \u2265 1) \u7b2c i \u5c42\u81f3\u5c11\u6709 1 \u4e2a\u7ed3\u70b9<\/p>\n \u6027\u8d282\uff1a\u6df1\u5ea6\u4e3ak\u7684\u4e8c\u53c9\u6811\u81f3\u591a\u6709 2^k – 1 \u4e2a\u7ed3\u70b9( k\u22651 )\uff1b\u6700\u5c11\u6709 k \u4e2a\u7ed3\u70b9<\/p>\n \u6027\u8d283\uff1a\u5bf9\u4efb\u4f55\u4e00\u68f5\u4e8c\u53c9\u6811 T \uff0c\u5982\u679c\u5176\u53f6\u5b50\u6570\u4e3a n0\uff0c\u5ea6\u4e3a 2 \u7684\u7ed3\u70b9\u6570\u4e3a n2\uff0c\u5219 n0 = n2 +1<\/p>\n <\/p>\n \u5b9a\u4e49\uff1a\u4e00\u68f5\u6df1\u5ea6\u4e3a k \u4e14\u6709 2^k – 1 \u4e2a\u7ed3\u70b9\u7684\u4e8c\u53c9\u6811\u79f0\u4e3a\u6ee1\u4e8c\u53c9\u6811<\/strong><\/p>\n \u7279\u70b9\uff1a<\/p>\n <\/p>\n \u5b9a\u4e49\uff1a\u6df1\u5ea6\u4e3a k \u7684\u5177\u6709 n \u4e2a\u7ed3\u70b9\u7684\u4e8c\u53c9\u6811\uff0c\u5f53\u4e14\u4ec5\u5f53\u5176\u6bcf\u4e00\u4e2a\u7ed3\u70b9\u90fd\u4e0e\u6df1\u5ea6\u4e3a k \u7684\u6ee1\u4e8c\u53c9\u6811\u4e2d\u7f16\u53f7\u4e3a 1~n \u7684\u7ed3\u70b9\u4e00\u4e00\u5bf9\u5e94\u65f6\uff0c\u79f0\u4e4b\u4e3a\u5b8c\u5168\u4e8c\u53c9\u6811<\/p>\n \u6ee1\u4e8c\u53c9\u6811\u4e00\u5b9a\u662f\u5b8c\u5168\u4e8c\u53c9\u6811\uff0c\u5b8c\u5168\u4e8c\u53c9\u6811\u4e0d\u4e00\u5b9a\u662f\u6ee1\u4e8c\u53c9\u6811<\/p>\n \u5373\u5728\u6ee1\u4e8c\u53c9\u6811\u4e2d\uff0c\u4ece\u6700\u540e\u4e00\u4e2a\u7ed3\u70b9\u5f00\u59cb\uff0c\u8fde\u7eed<\/strong>\u53bb\u6389\u4efb\u610f\u7ed3\u70b9\uff0c\u5373\u662f\u4e00\u68f5\u5b8c\u5168\u4e8c\u53c9\u6811\uff1b\u5fc5\u987b\u8fde\u7eed\u53bb\u6389<\/strong><\/p>\n <\/p>\n \u7279\u70b9\uff1a<\/p>\n <\/p>\n \u6027\u8d284\uff1a\u5177\u6709 n \u4e2a\u7ed3\u70b9\u7684\u5b8c\u5168\u4e8c\u53c9\u6811\u7684\u6df1\u5ea6\u4e3a log(2, n)\uff08\u53d6\u6574\uff09 +1<\/p>\n <\/p>\n \u6027\u8d285\uff1a\u5982\u679c\u5bf9\u4e00\u68f5\u5177\u6709 n \u4e2a\u7ed3\u70b9\u7684\u5b8c\u5168\u4e8c\u53c9\u3010\u6811\u6df1\u5ea6\u4e3a log(2, n)\uff08\u53d6\u6574\uff09 +1\u3011\u7684\u7ed3\u70b9\u6309\u5c42\u5e8f\u7f16\u53f7\uff08\u4ece\u7b2c1\u5c42\u5230\u7b2c log(2, n)\uff08\u53d6\u6574\uff09 +1 \u5c42\uff0c\u6bcf\u5c42\u4ece\u5de6\u5230\u53f3\uff09\uff0c\u5219\u5bf9\u4efb\u4e00\u7ed3\u70b9 i \uff081\u2264 i \u2264 n\uff09\uff0c\u6709\uff1a<\/p>\n <\/p>\n <\/p>\n \u6309\u6ee1\u4e8c\u53c9\u6811<\/strong>\u7684\u7ed3\u70b9\u5c42\u6b21\u7f16\u53f7\uff0c\u4f9d\u6b21\u5b58\u653e\u4e8c\u53c9\u6811\u4e2d\u7684\u6570\u636e\u5143\u7d20<\/p>\n <\/p>\n \u7c7bC\u8bed\u8a00<\/p>\n <\/p>\n \u5982\u679c\u65e2\u4e0d\u662f\u6ee1\u4e8c\u53c9\u6811\u4e5f\u4e0d\u662f\u5b8c\u5168\u4e8c\u53c9\u6811<\/p>\n <\/p>\n \u4e8c\u53c9\u6811\u987a\u5e8f\u5b58\u50a8\u7684\u7f3a\u70b9\uff1a<\/p>\n \u7279\u70b9\uff1a\u7ed3\u70b9\u95f4\u5173\u7cfb\u8574\u542b\u5728\u5176\u5b58\u50a8\u4f4d\u7f6e\u4e2d\uff0c\u6d6a\u8d39\u7a7a\u95f4\uff0c\u9002\u4e8e\u5b58\u6ee1\u4e8c\u53c9\u6811\u548c\u5b8c\u5168\u4e8c\u53c9\u6811<\/strong><\/p>\n <\/p>\n \u4e8c\u53c9\u94fe\u8868<\/strong><\/p>\n \u5982\u56fe\uff1a<\/p>\n \u5728n\u4e2a\u7ed3\u70b9\u7684\u4e8c\u53c9\u94fe\u8868\u4e2d\uff0c\u6709 n + 1 \u4e2a\u7a7a\u6307\u9488\u57df<\/p>\n \u5206\u6790\uff1a\u5fc5\u67092n\u4e2a\u94fe\u57df\u3002\u9664\u6839\u7ed3\u70b9\u5916\uff0c\u6bcf\u4e2a\u7ed3\u70b9\u6709\u4e14\u4ec5\u6709\u4e00\u4e2a\u53cc\u4eb2\uff0c\u6240\u4ee5\u4f1a\u6709 n-1 \u4e2a\u7ed3\u70b9\u7684\u94fe\u57df\u5b58\u653e\u6307\u9488\uff0c\u6307\u5411\u975e\u7a7a\u5b50\u5973\u7ed3\u70b9\u3002\u5373\u7a7a\u6307\u9488\u6570\u76ee = 2n -(n – 1) = n + 1<\/p>\n <\/p>\n \u4e09\u53c9\u94fe\u8868<\/strong><\/p>\n \u4ec5\u591a\u4e86\u4e00\u4e2a\u6307\u9488\u57df\u6307\u5411\u53cc\u4eb2\u7ed3\u70b9<\/p>\n <\/p>\n \u904d\u5386\u5b9a\u4e49\uff1a\u987a\u7740\u67d0\u4e00\u6761\u641c\u7d22\u8def\u5f84\u5de1\u8bbf\u4e8c\u53c9\u6811\u4e2d\u7684\u7ed3\u70b9\uff0c\u4f7f\u5f97\u67d0\u4e00\u4e2a\u7ed3\u70b9\u5747\u88ab\u8bbf\u95ee\u4e00\u6b21\uff0c\u800c\u4e14\u4ec5\u88ab\u8bbf\u95ee\u4e00\u6b21\uff08\u53c8\u79f0\u5468\u6e38\uff09<\/p>\n \u904d\u5386\u76ee\u7684\uff1a\u5f97\u5230\u6811\u4e2d\u6240\u6709\u7ed3\u70b9\u7684\u4e00\u4e2a\u7ebf\u6027\u6392\u5217<\/p>\n \u904d\u5386\u7528\u9014\uff1a\u5b83\u662f\u6811\u7ed3\u6784\u63d2\u5165\u3001\u5220\u9664\u3001\u4fee\u6539\u3001\u67e5\u627e\u548c\u6392\u5e8f\u8fd0\u7b97\u7684\u524d\u63d0\uff0c\u662f\u4e8c\u53c9\u6811\u4e00\u5207\u8fd0\u7b97\u7684\u57fa\u7840\u548c\u6838\u5fc3<\/p>\n <\/p>\n \u82e5\u4e8c\u53c9\u6811\u4e3a\u7a7a\uff0c\u5219\u7a7a\u64cd\u4f5c\uff1b\u5426\u5219\uff1a<\/p>\n <\/p>\n \u82e5\u4e8c\u53c9\u6811\u4e3a\u7a7a\uff0c\u5219\u7a7a\u64cd\u4f5c\uff1b\u5426\u5219<\/p>\n <\/p>\n \u82e5\u4e8c\u53c9\u6811\u4e3a\u7a7a\uff0c\u5219\u7a7a\u64cd\u4f5c\uff1b\u5426\u5219\uff1a<\/p>\n <\/p>\n \u904d\u5386\u7b97\u6cd5\u7684\u5206\u6790\uff1a<\/p>\n \u4e09\u79cd\u7b97\u6cd5\u65f6\u95f4\u590d\u6742\u5ea6\uff1aO(n)\uff0c\u7a7a\u95f4\u590d\u6742\u5ea6\uff1aO(n)<\/p>\n <\/p>\n \u4e8c\u53c9\u6811\u4e2d\u5e8f\u904d\u5386\u7684\u975e\u9012\u5f52\u7b97\u6cd5\u7684\u5173\u952e\uff1a\u5728\u4e2d\u5e8f\u904d\u5386\u8fc7\u67d0\u7ed3\u70b9\u7684\u6574\u4e2a\u5de6\u5b50\u6811\u540e\uff0c\u5982\u4f55\u627e\u5230\u8be5\u7ed3\u70b9\u7684\u6839<\/strong>\u4ee5\u53ca\u53f3\u5b50\u6811<\/strong><\/p>\n \u57fa\u672c\u601d\u60f3\uff1a<\/p>\n <\/p>\n \u5bf9\u4e8e\u4e00\u68f5\u4e8c\u53c9\u6811\uff0c\u4ece\u6839\u8282\u70b9\u5f00\u59cb\uff0c\u6309\u4ece\u4e0a\u5230\u4e0b\u3001\u4ece\u5de6\u5230\u53f3\u7684\u987a\u5e8f\u8bbf\u95ee\u6bcf\u4e00\u4e2a\u7ed3\u70b9\uff0c\u6bcf\u4e2a\u7ed3\u70b9\u4ec5\u4ec5\u8bbf\u95ee\u4e00\u6b21<\/p>\n \u5c42\u6b21\u904d\u5386\u7ed3\u679c\uff1aabfcdgeh<\/p>\n <\/p>\n \u7b97\u6cd5\u601d\u8def\uff1a\u4f7f\u7528\u4e00\u4e2a\u961f\u5217<\/strong><\/p>\n <\/p>\n \u7b97\u6cd5\u601d\u8def\uff1a<\/p>\n <\/p>\n \u7b97\u6cd5\u601d\u8def\uff1a<\/p>\n <\/p>\n \u7b97\u6cd5\u601d\u8def\uff1a<\/p>\n <\/p>\n \u7b97\u6cd5\u601d\u8def\uff1a<\/p>\n <\/p>\n <\/p>\n \u6784\u5efa\u5982\u56fe\u4e8c\u53c9\u6811<\/p>\n \u8fd0\u884c\u622a\u56fe\uff1a<\/p>\n <\/p>\n \u5229\u7528\u4e8c\u53c9\u94fe\u8868\u4e2d\u7684\u7a7a\u6307\u9488\u57df\uff1a<\/p>\n \u4e3a\u4e86\u533a\u5206leftChild\u548crightChild\u6307\u9488\u5230\u5e95\u662f\u6307\u5411\u5b69\u5b50\u7684\u6307\u9488\uff0c\u8fd8\u662f\u6307\u5411\u524d\u9a71\u6216\u8005\u540e\u7ee7\u7684\u6307\u9488\uff0c\u5bf9\u4e8c\u53c9\u94fe\u8868\u4e2d\u6bcf\u4e2a\u7ed3\u70b9\u589e\u8bbe\u4e24\u4e2a\u6807\u5fd7\u57df LeftTag\u548crightTag\uff0c\u5e76\u7ea6\u5b9a\uff1a<\/p>\n <\/p>\n \u4f8b\uff1a<\/p>\n <\/p>\n \u7279\u70b9\uff1a\u627e\u53cc\u4eb2\u5bb9\u6613\uff0c\u627e\u5b69\u5b50\u96be<\/p>\n <\/p>\n \u7279\u70b9\uff1a\u627e\u5b69\u5b50\u5bb9\u6613\uff0c\u627e\u53cc\u4eb2\u96be<\/p>\n <\/p>\n \u4e5f\u53ef\u4ee5\u5c06\u53cc\u4eb2\u8868\u793a\u6cd5\u548c\u5b69\u5b50\u94fe\u8868\u7ed3\u5408<\/p>\n \u8fd9\u79cd\u6211\u4eec\u79f0\u4e3a\u5e26\u53cc\u4eb2\u7684\u5b69\u5b50\u94fe\u8868<\/p>\n <\/p>\n \u53c8\u79f0\u4e8c\u53c9\u6811\u8868\u793a\u6cd5\uff0c\u4e8c\u53c9\u94fe\u8868\u8868\u793a\u6cd5<\/p>\n \u5b9e\u73b0\uff1a\u7528\u4e8c\u53c9\u94fe\u8868\u4f5c\u6811\u7684\u5b58\u50a8\u7ed3\u6784\uff0c\u94fe\u8868\u4e2d\u6bcf\u4e2a\u7ed3\u70b9\u7684\u4e24\u4e2a\u6307\u9488\u57df\u5206\u522b\u6307\u5411\u5176\u7b2c\u4e00\u4e2a\u5b69\u5b50\u7ed3\u70b9<\/strong>\u548c\u4e0b\u4e00\u4e2a\u5144\u5f1f\u7ed3\u70b9<\/strong><\/p>\n <\/p>\n \u5c06\u6811\u8f6c\u6362\u4e3a\u4e8c\u53c9\u6811\u8fdb\u884c\u5904\u7406\uff0c\u5229\u7528\u4e8c\u53c9\u6811\u7684\u7b97\u6cd5\u6765\u5b9e\u73b0\u5bf9\u6811\u7684\u64cd\u4f5c<\/p>\n \u7531\u4e8e\u6811\u548c\u4e8c\u53c9\u6811\u90fd\u53ef\u4ee5\u7528\u4e8c\u53c9\u94fe\u8868\u4f5c\u5b58\u50a8\u7ed3\u6784\uff0c\u5219\u4ee5\u4e8c\u53c9\u94fe\u8868\u4f5c\u5a92\u4ecb<\/strong>\u53ef\u4ee5\u5bfc\u51fa\u6811\u4e0e\u4e8c\u53c9\u6811\u4e4b\u95f4\u7684\u4e00\u4e2a\u5bf9\u5e94\u5173\u7cfb<\/p>\n \u6811\u53d8\u4e8c\u53c9\u6811\uff1a\u5144\u5f1f\u76f8\u8fde\u7559\u957f\u5b50<\/strong><\/p>\n <\/p>\n \u4e8c\u53c9\u6811\u53d8\u6811\uff1a\u5de6\u5b69\u53f3\u53f3\u8fde\u53cc\u4eb2\uff0c\u53bb\u6389\u539f\u6765\u53f3\u5b69\u7ebf<\/strong><\/p>\n <\/p>\n \u68ee\u6797\u53d8\u4e8c\u53c9\u6811\uff1a\u6811\u53d8\u4e8c\u53c9\u6839\u76f8\u8fde<\/strong><\/p>\n <\/p>\n \u4e8c\u53c9\u6811\u53d8\u68ee\u6797\uff1a\u53bb\u6389\u5168\u90e8\u53f3\u5b69\u7ebf\uff0c\u5b64\u7acb\u4e8c\u53c9\u518d\u8fd8\u539f<\/strong><\/p>\n <\/p>\n \u82e5\u6811\u4e0d\u4e3a\u7a7a\uff0c\u5219\u5148\u8bbf\u95ee\u6839\u7ed3\u70b9\uff0c\u7136\u540e\u4f9d\u6b21\u5148\u6839\u904d\u5386\u5404\u68f5\u5b50\u6811<\/p>\n \u548c\u4e8c\u53c9\u6811\u524d\u5e8f\u904d\u5386\u4e00\u6837<\/p>\n <\/p>\n \u82e5\u6811\u4e0d\u7a7a\uff0c\u5219\u5148\u4f9d\u6b21\u540e\u6839\u904d\u5386\u5404\u68f5\u5b50\u6811\uff0c\u7136\u540e\u8bbf\u95ee\u6839\u7ed3\u70b9<\/p>\n <\/p>\n \u82e5\u6811\u4e0d\u7a7a\uff0c\u5219\u81ea\u4e0a\u800c\u4e0b\u81ea\u5de6\u81f3\u53f3\u8bbf\u95ee\u6811\u4e2d\u6bcf\u4e2a\u7ed3\u70b9<\/p>\n \u548c\u4e8c\u53c9\u6811\u5c42\u6b21\u904d\u5386\u4e00\u6837\u4f7f\u7528\u961f\u5217<\/strong><\/p>\n <\/p>\n <\/p>\n \u5c06\u68ee\u6797\u770b\u4f5c\u7531\u4e09\u90e8\u5206\u6784\u6210\uff1a<\/p>\n <\/p>\n \u5148\u6839\u904d\u5386<\/strong><\/p>\n \u82e5\u68ee\u6797\u4e0d\u7a7a\uff0c\u5219\uff1a<\/p>\n <\/p>\n \u4e2d\u5e8f\u904d\u5386<\/strong><\/p>\n \u82e5\u68ee\u6797\u4e0d\u7a7a\uff0c\u5219\uff1a<\/p>\n \u5373\uff1a\u4f9d\u6b21\u4ece\u5de6\u81f3\u53f3\u5bf9\u68ee\u6797\u4e2d\u7684\u6bcf\u4e00\u68f5\u6811\u8fdb\u884c\u540e\u6839\u904d\u5386<\/p>\n <\/p>\n \u8def\u5f84\uff1a\u4ece\u6811\u4e2d\u4e00\u4e2a\u7ed3\u70b9\u5230\u53e6\u4e00\u4e2a\u7ed3\u70b9\u4e4b\u95f4\u7684\u5206\u652f<\/strong>\u6784\u6210\u8fd9\u4e24\u4e2a\u7ed3\u70b9\u95f4\u7684\u8def\u5f84<\/p>\n \u7ed3\u70b9\u7684\u8def\u5f84\u957f\u5ea6\uff1a\u4e24\u7ed3\u70b9\u95f4\u8def\u5f84\u4e0a\u7684\u5206\u652f\u6570<\/strong><\/p>\n <\/p>\n \u6811\u7684\u8def\u5f84\u957f\u5ea6\uff1a\u4ece\u6811\u6839<\/strong>\u5230\u6bcf\u4e00\u4e2a\u7ed3\u70b9\u7684\u8def\u5f84\u957f\u5ea6\u4e4b\u548c<\/strong>\u3002\u8bb0\u4f5c\uff1aTL<\/p>\n \u7ed3\u70b9\u6570\u76ee\u76f8\u540c\u7684\u4e8c\u53c9\u6811\u4e2d\uff0c\u5b8c\u5168\u4e8c\u53c9\u6811<\/strong>\u662f\u8def\u5f84\u957f\u5ea6\u6700\u77ed\u7684\u4e8c\u53c9\u6811<\/p>\n <\/p>\n \u6743(weight)\uff1a\u5c06\u6811\u4e2d\u7ed3\u70b9\u8d4b\u7ed9\u4e00\u4e2a\u6709\u7740\u67d0\u79cd\u542b\u4e49\u7684\u6570\u503c\uff0c\u5219\u8fd9\u4e2a\u6570\u503c\u79f0\u4e3a\u8be5\u7ed3\u70b9\u7684\u6743<\/strong><\/p>\n <\/p>\n \u7ed3\u70b9\u7684\u5e26\u6743\u8def\u5f84\u957f\u5ea6\uff1a\u4ece\u6839<\/strong>\u8282\u70b9\u5230\u8be5\u8282\u70b9\u4e4b\u95f4\u7684\u8def\u5f84\u957f\u5ea6<\/strong>\u4e0e\u8be5\u7ed3\u70b9\u7684\u6743<\/strong>\u7684\u4e58\u79ef<\/strong><\/p>\n <\/p>\n \u6811\u7684\u5e26\u6743\u8def\u5f84\u957f\u5ea6\uff1a\u6811\u4e2d\u6240\u6709\u53f6\u5b50<\/strong>\u7ed3\u70b9\u7684\u5e26\u6743\u8def\u5f84\u957f\u5ea6\u4e4b\u548c\uff0c\u8bb0\u4e3aWPL<\/strong><\/p>\n <\/p>\n \u54c8\u592b\u66fc\u6811\uff1a\u6700\u4f18\u6811\uff0c\u5e26\u6743\u8def\u5f84\u957f\u5ea6\uff08WPL\uff09\u6700\u77ed\u7684\u6811<\/p>\n \u6ce8\uff1a\u201c\u5e26\u6743\u8def\u5f84\u957f\u5ea6\u6700\u77ed\u201d\u662f\u5728\u201c\u5ea6\u76f8\u540c\u201d\u7684\u6811\u4e2d\u6bd4\u8f83\u800c\u5f97\u7684\u7ed3\u679c\uff0c\u56e0\u6b64\u6709\u6700\u4f18\u4e8c\u53c9\u6811\u3001\u6700\u4f18\u4e09\u53c9\u6811\u4e4b\u79f0\u7b49\u7b49<\/p>\n \u56e0\u6b64\u54c8\u592b\u66fc\u6811\u53c8\u79f0\u6700\u4f18\u4e8c\u53c9\u6811<\/p>\n <\/p>\n <\/p>\n \u6784\u9020\u7b97\u6cd5\uff1a<\/p>\n \u5305\u542bn\u68f5\u6811\u7684\u68ee\u6797\u8981\u7ecf\u8fc7n-1\u6b21\u5408\u5e76\u624d\u80fd\u5f62\u6210\u54c8\u592b\u66fc\u6811\uff0c\u5171\u4ea7\u751fn-1\u4e2a\u65b0\u7ed3\u70b9<\/p>\n \u5305\u542bn\u4e2a\u53f6\u5b50\u7ed3\u70b9\u7684\u54c8\u592b\u66fc\u6811\u4e2d\u5171\u67092n-1\u4e2a\u7ed3\u70b9<\/p>\n <\/p>\n \u603b\u7ed3\uff1a<\/p>\n \u53ef\u89c1\uff1a\u54c8\u592b\u66fc\u6811\u4e2d\u5171\u6709n+n-1 = 2n-1<\/strong>\u4e2a\u7ed3\u70b9\uff0c\u4e14\u5176\u6240\u6709\u7684\u5206\u652f\u7ed3\u70b9\u7684\u5ea6\u5747\u4e0d\u4e3a1<\/p>\n <\/p>\n \u91c7\u7528\u987a\u5e8f\u5b58\u50a8\u7ed3\u6784\u2014\u2014\u4e00\u7ef4\u7ed3\u6784\u6570\u7ec4<\/p>\n <\/p>\n <\/p>\n <\/p>\n \u4e24\u4e2a\u95ee\u9898\uff1a<\/p>\n 1.\u4e3a\u4ec0\u4e48\u54c8\u592b\u66fc\u7f16\u7801\u80fd\u591f\u4fdd\u8bc1\u662f\u524d\u7f00\u7f16\u7801\uff1f<\/p>\n \u56e0\u4e3a\u6ca1\u6709\u4e00\u7247\u6811\u53f6\u662f\u53e6\u4e00\u7247\u6811\u53f6\u7684\u7956\u5148\uff0c\u6240\u4ee5\u6bcf\u4e2a\u53f6\u7ed3\u70b9\u7684\u7f16\u7801\u5c31\u4e0d\u53ef\u80fd\u662f\u5176\u5b83\u53f6\u7ed3\u70b9\u7f16\u7801\u7684\u524d\u7f00<\/p>\n <\/p>\n 2.\u4e3a\u4ec0\u4e48\u54c8\u592b\u66fc\u7f16\u7801\u80fd\u591f\u4fdd\u8bc1\u5b57\u7b26\u7f16\u7801\u603b\u957f\u6700\u77ed\uff1f<\/p>\n \u56e0\u4e3a\u54c8\u592b\u66fc\u6811\u7684\u5e26\u6743\u8def\u5f84\u957f\u5ea6\u6700\u77ed\uff0c\u6545\u5b57\u7b26\u7f16\u7801\u7684\u603b\u957f\u6700\u77ed<\/p>\n <\/p>\n <\/p>\n \u660e\u6587<\/p>\n <\/p>\n <\/p>\n <\/p>\n \u5b8c\u6574\u4ee3\u7801\uff1a\n
![\"img\"](\"https:\/\/picture.chentaiyang.space\/202304251440552.png\")
<\/p>\n![\"img\"](\"https:\/\/picture.chentaiyang.space\/202304251440558.png\")
<\/p>\n![\"img\"](\"https:\/\/picture.chentaiyang.space\/202304251440831.png\")
<\/p>\n5.2 \u6848\u4f8b\u5f15\u5165<\/h2>\n
5.2.1 \u6570\u636e\u538b\u7f29\u95ee\u9898<\/h3>\n
![\"img\"](\"https:\/\/picture.chentaiyang.space\/202304251440834.png\")
<\/p>\n5.2.2 \u5229\u7528\u4e8c\u53c9\u6811\u6c42\u89e3\u8868\u8fbe\u5f0f\u7684\u503c<\/h3>\n
\n
![\"img\"](\"https:\/\/picture.chentaiyang.space\/202304251440841.png\")
<\/p>\n5.3 \u6811\u548c\u4e8c\u53c9\u6811\u7684\u62bd\u8c61\u6570\u636e\u7c7b\u578b\u5b9a\u4e49<\/h2>\n
![\"img\"](\"https:\/\/picture.chentaiyang.space\/202304251440114.png\")
<\/p>\n\n
\n
\n
\n
5.4 \u4e8c\u53c9\u6811\u7684\u6027\u8d28\u548c\u5b58\u50a8\u7ed3\u6784<\/h2>\n
5.4.1 \u4e8c\u53c9\u6811\u7684\u6027\u8d28<\/h3>\n
\u6ee1\u4e8c\u53c9\u6811<\/h4>\n
\n
\u5b8c\u5168\u4e8c\u53c9\u6811<\/h4>\n
![\"img\"](\"https:\/\/picture.chentaiyang.space\/202304251440125.png\")
<\/p>\n\n
![\"img\"](\"https:\/\/picture.chentaiyang.space\/202304251440426.png\")
<\/p>\n5.4.2 \u4e8c\u53c9\u6811\u7684\u5b58\u50a8\u7ed3\u6784<\/h3>\n
![\"img\"](\"https:\/\/picture.chentaiyang.space\/202304251440424.jpeg\")
<\/p>\n\u987a\u5e8f\u5b58\u50a8\u7ed3\u6784<\/h4>\n
![\"img\"](\"https:\/\/picture.chentaiyang.space\/202304251440823.png\")
<\/p>\n\/\/ \u4e8c\u53c9\u6811\u7684\u987a\u5e8f\u5b58\u50a8\u8868\u793a\n#define MAXSQTREESIZE 100\n\ntypedef TelEmeType sequenBinaryTree[MAXSQTREESIZE];\nsequenBinaryTree bt;\n<\/code><\/pre>\n![\"img\"](\"https:\/\/picture.chentaiyang.space\/202304251440825.png\")
<\/p>\n![\"img\"](\"https:\/\/picture.chentaiyang.space\/202304251440826.png\")
<\/p>\n\u94fe\u5f0f\u5b58\u50a8<\/h4>\n
![\"img\"](\"https:\/\/picture.chentaiyang.space\/202304251440832.png\")
<\/p>\ntypedef struct BinaryNode {\n\tchar data;\t\t\t\t\t\t\t\/\/ \u6570\u636e\u57df\n\tstruct BinaryNode* leftChild;\t\t\/\/ \u5de6\u5b69\u5b50\n\tstruct BinaryNode* rightChild;\t\t\/\/ \u53f3\u5b69\u5b50\n}binaryNode, * linkBinaryTree;\n<\/code><\/pre>\n![\"img\"](\"https:\/\/picture.chentaiyang.space\/202304251440846.png\")
<\/p>\n![\"img\"](\"https:\/\/picture.chentaiyang.space\/202304251440088.png\")
<\/p>\n5.5 \u904d\u5386\u4e8c\u53c9\u6811\u548c\u7ebf\u7d22\u4e8c\u53c9\u6811<\/h2>\n
5.5.1 \u904d\u5386\u4e8c\u53c9\u6811<\/h3>\n
\n
![\"img\"](\"https:\/\/picture.chentaiyang.space\/202304251440635.png\")
<\/p>\n\u5148\u5e8f\u904d\u5386<\/h4>\n
\n
![\"img\"](\"https:\/\/picture.chentaiyang.space\/202304251440630.png\")
<\/p>\n\/*******************************************************************************************************************************\n * @description\uff1a\u5148\u5e8f\u904d\u5386\n * @param\uff1atree\t\u94fe\u5f0f\u6811\n *\/\nvoid preOrderTraverse(linkBinaryTree tree) \n{\n\tif (tree == NULL) {\n\t\treturn;\n\t}\n\tprintf(\"%c\", tree->data);\t\t\t\/\/ \u6839\n\tpreOrderTraverse(tree->leftChild);\t\/\/ \u5de6\n\tpreOrderTraverse(tree->rightChild);\t\/\/ \u53f3\n}\n<\/code><\/pre>\n\u4e2d\u5e8f\u904d\u5386<\/h4>\n
\n
![\"img\"](\"https:\/\/picture.chentaiyang.space\/202304251440633.png\")
<\/p>\n\/*******************************************************************************************************************************\n * @description\uff1a\u4e2d\u5e8f\u904d\u5386\n * @param\uff1atree\t\u94fe\u5f0f\u6811\n *\/\nvoid inOrderTraverse(linkBinaryTree tree)\n{\n\tif (tree == NULL) {\n\t\treturn;\n\t}\n\tinOrderTraverse(tree->leftChild);\t\/\/ \u5de6\n\tprintf(\"%c\", tree->data);\t\t\t\/\/ \u6839\n\tinOrderTraverse(tree->rightChild);\t\/\/ \u53f3\n}\n<\/code><\/pre>\n\u540e\u5e8f\u904d\u5386<\/h4>\n
\n
![\"img\"](\"https:\/\/picture.chentaiyang.space\/202304251440643.png\")
<\/p>\n\/*******************************************************************************************************************************\n * @description\uff1a\u540e\u5e8f\u904d\u5386\n * @param\uff1atree\t\u94fe\u5f0f\u6811\n *\/\nvoid postOrderTraverse(linkBinaryTree tree)\n{\n\tif (tree == NULL) {\n\t\treturn;\n\t}\n\tpostOrderTraverse(tree->leftChild);\t\t\/\/ \u5de6\n\tpostOrderTraverse(tree->rightChild);\t\/\/ \u53f3\n\tprintf(\"%c\", tree->data);\t\t\t\t\/\/ \u6839\n}\n<\/code><\/pre>\n![\"img\"](\"https:\/\/picture.chentaiyang.space\/202304251440652.png\")
<\/p>\n\u4e2d\u5e8f\u904d\u5386\u975e\u9012\u5f52\u7b97\u6cd5<\/h4>\n
\n
status inOrderTraverse(Bitree T)\n{\n BiTree p;\n initStack(S);\n p = T;\n while(p || !StackEmpty(S)){\n if(p){\n Push(S, p);\n p = p->leftChild;\n }\n else{\n Pop(S, p);\n printf(\"&c\", q->data);\n p = q->rightCild;\n }\n }\n return OK;\n}\n<\/code><\/pre>\n\u5c42\u6b21\u904d\u5386<\/h4>\n
![\"img\"](\"https:\/\/picture.chentaiyang.space\/202304251440650.png\")
<\/p>\n\n
\n
void levelOrder(BTNode* b)\n{\n BTNode* p;\n SqQueue* qu;\n initQueue(qu);\t\t\t\t\t\t\/\/ \u521d\u59cb\u5316\u961f\u5217\n enQueue(qu, b);\t\t\t\t\t\t\/\/ \u6839\u8282\u70b9\u6307\u9488\u8fdb\u5165\u961f\u5217\n while(!QueueEmpty(qu)){\t\t\t\t\/\/ \u961f\u4e0d\u4e3a\u7a7a\u5219\u5faa\u73af\n deQueue(qu, p);\t\t\t\t\t\/\/ \u51fa\u961f\u7ed3\u70b9p\n printf(\"%c\", p->data);\t\t\t\/\/ \u8bbf\u95ee\u7ed3\u70b9p\n if(p->leftData!=NULL){\n enQueue(qu, p->leftCild);\t\/\/ \u6709\u5de6\u5b69\u5b50\u65f6\u5c06\u5176\u8fdb\u961f\n }\n if(p->rightChild!=NULL){\n enQueue(qu, p->rightChild);\t\/\/ \u6709\u53f3\u5b69\u5b50\u65f6\u5c06\u5176\u8fdb\u961f\n }\n }\n}\n<\/code><\/pre>\n\u5148\u5e8f\u904d\u5386\u5efa\u7acb\u4e8c\u53c9\u6811<\/h4>\n
\n
\/*******************************************************************************************************************************\n * @description\uff1a\u5148\u5e8f\u904d\u5386\u521b\u5efa\u4e8c\u53c9\u6811\n * @return\uff1a\n *\/\nstatus preCreateBinaryTree(linkBinaryTree* tree)\n{\n\tchar ch;\n\tprintf(\"\u8f93\u5165\u5148\u5e8f\u5e8f\u5217\uff0c\u4ee5#\u8868\u793a\u7a7a\u7ed3\u70b9\uff1a\");\n\tscanf(\"%c\", &ch);\n\tif (ch == '#') {\n\t\t*tree = NULL;\n\t}\n\telse {\n\t\t*tree = (linkBinaryTree)malloc(sizeof(binaryNode));\n\t\tif (*tree == NULL) {\n\t\t\texit(OVERFLOW);\n\t\t}\n\t\t(*tree)->data = ch;\t\t\/\/ \u751f\u6210\u6839\u7ed3\u70b9\n\t\tpreCreateBinaryTree(&(*tree)->leftChild);\t\/\/ \u6784\u9020\u5de6\u5b50\u6811\n\t\tpreCreateBinaryTree(&(*tree)->rightChild);\t\/\/ \u6784\u9020\u53f3\u5b50\u6811\n\t}\n\treturn OK;\n}\n<\/code><\/pre>\n\u590d\u5236\u4e8c\u53c9\u6811<\/h4>\n
\n
\n
\/*******************************************************************************************************************************\n * @description\uff1a \u590d\u5236\u4e8c\u53c9\u6811\n * @param\uff1atree\n * @param\uff1acopyTree\n * @return\uff1a\n *\/\nstatus copyBinaryTree(linkBinaryTree tree, linkBinaryTree* copyTree)\n{\n\tif (copyTree == NULL) {\n\t\ttree = NULL;\n\t}\n\telse {\n\t\t*copyTree = (linkBinaryTree)malloc(sizeof(binaryNode));\n\t\tif (*copyTree == NULL) {\n\t\t\texit(OVERFLOW);\n\t\t}\n\t\t(*copyTree)->data = tree->data;\n\t\tcopyBinaryTree(tree->leftChild, &((*copyTree)->leftChild));\n\t\tcopyBinaryTree(tree->rightChild, &((*copyTree)->rightChild));\n\t}\n\treturn OK;\n}\n<\/code><\/pre>\n\u8ba1\u7b97\u4e8c\u53c9\u6811\u6df1\u5ea6<\/h4>\n
\n
\/*******************************************************************************************************************************\n * @description\uff1a\u8ba1\u7b97\u4e8c\u53c9\u6811\u6df1\u5ea6\n * @param\uff1atree\n * @return\uff1a\n *\/\nint depthBinaryTree(linkBinaryTree tree)\n{\n\tint depth = 0;\n\tif (tree != NULL) {\n\t\tint leftDepth = depthBinaryTree(tree->leftChild);\n\t\tint rightDepth = depthBinaryTree(tree->rightChild);\n\t\tdepth = leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;\n\t}\n\treturn depth;\n}\n<\/code><\/pre>\n\u8ba1\u7b97\u7ed3\u70b9\u603b\u6570<\/h4>\n
\n
\/*******************************************************************************************************************************\n * @description\uff1a\u6c42\u7ed3\u70b9\u603b\u6570\n * @param\uff1atree\n * @return\uff1a\n *\/\nint countBinaryTree(linkBinaryTree tree)\n{\n\tint count = 0;\n\tif (tree != NULL) {\n\t\tcount = 1 + countBinaryTree(tree->leftChild) + countBinaryTree(tree->rightChild);\n\t}\n\treturn count;\n}\n<\/code><\/pre>\n\u8ba1\u7b97\u53f6\u5b50\u7ed3\u70b9\u603b\u6570<\/h4>\n
\/*******************************************************************************************************************************\n * @description\uff1a\u6c42\u53f6\u5b50\u7ed3\u70b9\u7684\u603b\u6570\n * @param\uff1atree\n * @return\uff1a\n *\/\nint countLeafBinaryTree(linkBinaryTree tree)\n{\n\tif (tree != NULL) {\n\t\tif (tree->leftChild == NULL && tree->rightChild == NULL) {\n\t\t\treturn 1;\n\t\t}\n\t\telse {\n\t\t\treturn countLeafBinaryTree(tree->leftChild) + countLeafBinaryTree(tree->rightChild);\n\t\t}\n\t}\n return 0;\n}\n<\/code><\/pre>\n\u6d4b\u8bd5\u4ee3\u7801<\/h4>\n
![\"img\"](\"https:\/\/picture.chentaiyang.space\/202304251440094.png\")
<\/p>\nvoid BinaryTreeMain()\n{\n\tlinkBinaryTree tree = NULL;\n\n\t\/**\n\t* \u5148\u5e8f\u904d\u5386\u987a\u5e8f\u4e3a\uff1aABCDEGF\n\t* \u8f93\u5165\uff1aABC##DE#G##F###\n\t*\/\n\tprintf(\"\\n\u8f93\u5165\u5148\u5e8f\u5e8f\u5217\uff0c\u4ee5#\u8868\u793a\u7a7a\u7ed3\u70b9\uff1a\");\n\tpreCreateBinaryTree(&tree);\n\tprintf(\"\\n\u4e8c\u53c9\u6811\u4e2d\u7684\u5143\u7d20\u4e3a\uff1a\");\n\tprintBinaryTree(tree);\n\n\tprintf(\"\\n\\n\u5148\u5e8f\u904d\u5386\uff1a\");\n\tpreOrderTraverse(tree);\n\tprintf(\"\\n\\n\u4e2d\u5e8f\u904d\u5386\uff1a\");\n\tinOrderTraverse(tree);\n\tprintf(\"\\n\\n\u540e\u5e8f\u904d\u5386\uff1a\");\n\tpostOrderTraverse(tree);\n\n\tprintf(\"\\n\\n\u4e8c\u53c9\u6811\u7684\u6df1\u5ea6\u4e3a\uff1a%d\", depthBinaryTree(tree));\n\tprintf(\"\\n\\n\u4e8c\u53c9\u6811\u7684\u7ed3\u70b9\u603b\u6570\u4e3a\uff1a%d\", countBinaryTree(tree));\n\tprintf(\"\\n\\n\u4e8c\u53c9\u6811\u7684\u53f6\u5b50\u7ed3\u70b9\u6570\u4e3a\uff1a%d\\n\", countLeafBinaryTree(tree));\n}\n<\/code><\/pre>\n![\"img\"](\"https:\/\/picture.chentaiyang.space\/202304251440095.png\")
<\/p>\n5.5.2 \u7ebf\u7d22\u4e8c\u53c9\u6811<\/h3>\n
\n
![\"img\"](\"https:\/\/picture.chentaiyang.space\/202304251440611.png\")
<\/p>\n\n
typedef struct threadedBinaryTreeNode {\n\tchar data;\t\t\t\t\t\t\t\t\t\/\/ \u6570\u636e\u57df\n\tint leftTag;\t\t\t\t\t\t\t\t\/\/ \u5de6\u6807\u5fd7\n\tstruct threadedBinaryTreeNode* leftChild;\t\/\/ \u5de6\u5b69\u5b50\n\tint rightTag;\t\t\t\t\t\t\t\t\/\/ \u53f3\u6807\u5fd7\n\tstruct threadedBinaryTreeNode* rightChild;\t\/\/ \u53f3\u5b69\u5b50\n}threadedBinaryTreeNode, * threadedBinaryTree;;\n<\/code><\/pre>\n![\"img\"](\"https:\/\/picture.chentaiyang.space\/202304251440615.png\")
<\/p>\n![\"img\"](\"https:\/\/picture.chentaiyang.space\/202304251440616.png\")
<\/p>\n![\"img\"](\"https:\/\/picture.chentaiyang.space\/202304251440624.png\")
<\/p>\n5.6 \u6811\u548c\u68ee\u6797<\/h2>\n
5.6.1 \u6811\u7684\u5b58\u50a8\u7ed3\u6784<\/h3>\n
\u53cc\u4eb2\u8868\u793a\u6cd5<\/h4>\n
![\"img\"](\"https:\/\/picture.chentaiyang.space\/202304251440629.png\")
<\/p>\n#define MAX_TREE_SIZE 100\n\ntypedef struct {\n\tchar data;\t\t\/\/ \u6570\u636e\u57df\n\tint parent;\t\t\/\/ \u53cc\u4eb2\u4f4d\u7f6e\n}parentTreeNode;\n\ntypedef struct {\n\tparentTreeNode nodes[MAX_TREE_SIZE];\/\/ \u53cc\u4eb2\u8868\u793a\u6cd5\u7684\u8282\u70b9\n\tint r;\t\t\t\t\t\t\t\t\/\/ \u6839\u7684\u4f4d\u7f6e\n\tint num;\t\t\t\t\t\t\t\/\/ \u8282\u70b9\u6570\n}parentTree;\n<\/code><\/pre>\n\u5b69\u5b50\u94fe\u8868<\/h4>\n
![\"img\"](\"https:\/\/picture.chentaiyang.space\/202304251440634.png\")
<\/p>\ntypedef struct childTreeNode {\n\tchar data;\t\t\t\t\t\/\/ \u6570\u636e\u57df\n\tstruct childTreeNode* next;\t\/\/ \u7b2c\u4e00\u4e2a\u5b69\u5b50\n}*childPtr;\n\n\ntypedef struct {\n\tchar data;\t\t\t\t\/\/ \u6570\u636e\u57df\n\tchildPtr firstChild;\t\/\/ \u7b2c\u4e00\u4e2a\u5b69\u5b50\n}childLink;\n\n\ntypedef struct {\n\tchildLink nodes[MAX_TREE_SIZE];\t\/\/ \u5b69\u5b50\u8868\u793a\u6cd5\u7684\u8282\u70b9\n\tint r;\t\t\t\t\t\t\t\/\/ \u6839\u7684\u4f4d\u7f6e\n\tint num;\t\t\t\t\t\t\/\/ \u8282\u70b9\u6570\n}childTree;\n<\/code><\/pre>\n![\"img\"](\"https:\/\/picture.chentaiyang.space\/202304251440489.png\")
<\/p>\n\u5b69\u5b50\u5144\u5f1f\u8868\u793a\u6cd5<\/h4>\n
![\"img\"](\"https:\/\/picture.chentaiyang.space\/202304251440493.png\")
<\/p>\ntypedef struct childSiblingTreeNode {\n\tchar data;\t\t\t\t\t\t\t\t\t\/\/ \u6570\u636e\u57df\n\tstruct childSiblingTreeNode* firstChild;\t\/\/ \u7b2c\u4e00\u4e2a\u5b69\u5b50\n\tstruct childSiblingTreeNode* nextSibling;\t\/\/ \u4e0b\u4e00\u4e2a\u5144\u5f1f\n}childSiblingTreeNode, * childSiblingTree;\n<\/code><\/pre>\n5.6.2 \u68ee\u6797\u4e0e\u4e8c\u53c9\u6811\u7684\u8f6c\u6362<\/h3>\n
![\"img\"](\"https:\/\/picture.chentaiyang.space\/202304251440495.png\")
<\/p>\n\u6811\u8f6c\u6362\u6210\u4e8c\u53c9\u6811<\/h4>\n
\n
![\"img\"](\"https:\/\/picture.chentaiyang.space\/202304251440497.png\")
<\/p>\n\/*******************************************************************************************************************************\n * @description\uff1a\u5c06\u6811\u8f6c\u6362\u4e3a\u4e8c\u53c9\u6811\n * @param\uff1atree\n * @param\uff1abinaryTree\n * @return\uff1a\n *\/\nstatus convertTreeToBinaryTree(childSiblingTree tree, linkBinaryTree* binaryTree) {\n\tif (tree == NULL) {\n\t\treturn ERROR;\n\t}\n\t\/\/ \u7533\u8bf7\u6839\u8282\u70b9\n\t*binaryTree = (linkBinaryTree)malloc(sizeof(binaryNode));\n\tif (*binaryTree == NULL) {\n\t\treturn OVERFLOW;\n\t}\n\t\/\/ \u6839\u8282\u70b9\u8d4b\u503c\n\t(*binaryTree)->data = tree->data;\n\n\tif (tree->firstChild != NULL) {\n\t\tconvertTreeToBinaryTree(tree->firstChild, binaryTree);\n\t}\n\telse {\n\t\t(*binaryTree)->leftChild = NULL;\n\t}\n\n\tif (tree->nextSibling != NULL) {\n\t\tconvertTreeToBinaryTree(tree->nextSibling, binaryTree);\n\t}\n\telse {\n\t\t(*binaryTree)->rightChild = NULL;\n\t}\n\treturn OK;\n}\n<\/code><\/pre>\n\u4e8c\u53c9\u6811\u8f6c\u6362\u6210\u6811<\/h4>\n
\n
![\"img\"](\"https:\/\/picture.chentaiyang.space\/202304251440509.png\")
<\/p>\n\/*******************************************************************************************************************************\n * @description\uff1a\u5c06\u4e8c\u53c9\u6811\u8f6c\u6362\u4e3a\u6811\n * @param\uff1abinaryTree\n * @param\uff1atree\n * @return\uff1a\n *\/\nstatus convertBinaryTreeToTree(linkBinaryTree binaryTree, childSiblingTree* tree) {\n\tif (binaryTree == NULL) {\n\t\treturn ERROR;\n\t}\n\t\/\/ \u7533\u8bf7\u6839\u8282\u70b9\n\t*tree = (childSiblingTree)malloc(sizeof(childSiblingTreeNode));\n\tif (*tree == NULL) {\n\t\treturn OVERFLOW;\n\t}\n\t\/\/ \u6839\u8282\u70b9\u8d4b\u503c\n\t(*tree)->data = binaryTree->data;\n\n\tif (binaryTree->leftChild != NULL) {\n\t\tconvertBinaryTreeToTree(binaryTree->leftChild, &((*tree)->firstChild));\n\t}\n\telse {\n\t\t(*tree)->firstChild = NULL;\n\t}\n\n\tif (binaryTree->rightChild != NULL) {\n\t\tconvertBinaryTreeToTree(binaryTree->rightChild, &((*tree)->nextSibling));\n\t}\n\telse {\n\t\t(*tree)->nextSibling = NULL;\n\t}\n\treturn OK;\n}\n<\/code><\/pre>\n\u68ee\u6797\u8f6c\u6362\u4e3a\u4e8c\u53c9\u6811<\/h4>\n
\n
![\"img\"](\"https:\/\/picture.chentaiyang.space\/202304251440516.png\")
<\/p>\n\u4e8c\u53c9\u6811\u8f6c\u6362\u6210\u68ee\u6797<\/h4>\n
\n
![\"img\"](\"https:\/\/picture.chentaiyang.space\/202304251440314.png\")
<\/p>\n5.6.3 \u6811\u548c\u68ee\u6797\u7684\u904d\u5386<\/h3>\n
\u6811\u7684\u5148\u6839\u904d\u5386<\/h4>\n
\/*******************************************************************************************************************************\n * @description\uff1a\u6811\u7684\u5148\u6839\u904d\u5386\n * @param\uff1atree\n *\/\nvoid preOrderTraverseTree(childSiblingTree tree) {\n\tif (tree == NULL) {\n\t\treturn;\n\t}\n\tprintf(\"%c\", tree->data);\n\tpreOrderTraverseTree(tree->firstChild);\n\tpreOrderTraverseTree(tree->nextSibling);\n}\n<\/code><\/pre>\n\u6811\u7684\u540e\u6839\u904d\u5386<\/h4>\n
\/*******************************************************************************************************************************\n * @description\uff1a\u6811\u7684\u540e\u6839\u904d\u5386\n * @param\uff1atree\n *\/\nvoid postOrderTraverseTree(childSiblingTree tree) {\n\tif (tree == NULL) {\n\t\treturn;\n\t}\n\tpostOrderTraverseTree(tree->firstChild);\n\tprintf(\"%c\", tree->data);\n\tpostOrderTraverseTree(tree->nextSibling);\n}\n<\/code><\/pre>\n\u6811\u7684\u5c42\u6b21\u904d\u5386<\/h4>\n
![\"img\"](\"https:\/\/picture.chentaiyang.space\/202304251440341.png\")
<\/p>\n\/*******************************************************************************************************************************\n * @description\uff1a\u6811\u7684\u5c42\u6b21\u904d\u5386\n * @param\uff1atree\n *\/\nvoid levelOrderTraverseTree(childSiblingTree tree) {\n\tif (tree == NULL) {\n\t\treturn;\n\t}\n\t\/\/ \u7533\u8bf7\u961f\u5217\n\tsuquenQueue queue;\n\tinitSequenQueue(&queue);\n\t\/\/ \u6839\u8282\u70b9\u5165\u961f\n\tenSequenQueue(&queue, tree);\n\t\/\/ \u961f\u5217\u4e0d\u4e3a\u7a7a\n\twhile (queue.front != queue.base) {\n\t\t\/\/ \u51fa\u961f\n\t\tchildSiblingTree node;\n\t\tdeSequenQueue(&queue, &node);\n\t\t\/\/ \u8bbf\u95ee\n\t\tprintf(\"%c\", node->data);\n\t\t\/\/ \u5b69\u5b50\u8282\u70b9\u5165\u961f\n\t\tif (node->firstChild != NULL) {\n\t\t\tenSequenQueue(&queue, node->firstChild);\n\t\t}\n\t\t\/\/ \u5144\u5f1f\u8282\u70b9\u5165\u961f\n\t\tif (node->nextSibling != NULL) {\n\t\t\tenSequenQueue(&queue, node->nextSibling);\n\t\t}\n\t}\n}\n<\/code><\/pre>\n\u68ee\u6797\u7684\u904d\u5386<\/h4>\n
\n
\n
\n
![\"img\"](\"https:\/\/picture.chentaiyang.space\/202304251440345.png\")
<\/p>\n5.7 \u54c8\u592b\u66fc\u6811\u53ca\u5176\u5e94\u7528<\/h2>\n
5.7.1 \u54c8\u592b\u66fc\u6811\u7684\u57fa\u672c\u6982\u5ff5<\/h3>\n
![\"img\"](\"https:\/\/picture.chentaiyang.space\/202304251440344.png\")
<\/p>\n![\"img\"](\"https:\/\/picture.chentaiyang.space\/202304251440356.png\")
<\/p>\n![\"img\"](\"https:\/\/picture.chentaiyang.space\/202304251440360.png\")
<\/p>\n![\"img\"](\"https:\/\/picture.chentaiyang.space\/202304251440871.png\")
<\/p>\n5.7.2 \u54c8\u592b\u66fc\u6811\u7684\u6784\u9020\u7b97\u6cd5<\/h3>\n
![\"img\"](\"https:\/\/picture.chentaiyang.space\/202304251440878.png\")
<\/p>\n\n
![\"img\"](\"https:\/\/picture.chentaiyang.space\/202304251440888.png\")
<\/p>\n![](\"https:\/\/picture.chentaiyang.space\/202305041317520.png\")
<\/p>\n\n
\u7b97\u6cd5\u7684\u5b9e\u73b0<\/h4>\n
typedef struct {\n\tint weight;\t\t\/\/ \u6743\u503c\n\tint parent;\t\t\/\/ \u7236\u7ed3\u70b9\n\tint leftchild;\t\/\/ \u5de6\u5b69\u5b50\n\tint rightchild; \/\/ \u53f3\u5b69\u5b50\n}HTNode, * HuffmanTree;\n<\/code><\/pre>\n\n
\n
\n
\n
\n
\/*******************************************************************************************************************************\n * @description\uff1a\u9009\u62e9HT[1...n]\u4e2dparent\u4e3a0\u4e14weight\u6700\u5c0f\u7684\u4e24\u4e2a\u7ed3\u70b9\uff0c\u5176\u5e8f\u53f7\u5206\u522b\u4e3as1\u548cs2\n * @param\uff1aHT\n * @param\uff1an\n * @param\uff1as1\n * @param\uff1as2\n *\/\nstatic void select(HuffmanTree HT, int n, int* s1, int* s2)\n{\n\tint min1 = 0, min2 = 0;\n\tfor (int i = 1; i <= n; i++) {\n\t\tif (HT[i].parent == 0) {\n\t\t\tif (min1 == 0) {\n\t\t\t\tmin1 = i;\n\t\t\t}\n\t\t\telse if (min2 == 0) {\n\t\t\t\tmin2 = i;\n\t\t\t}\n\t\t\telse {\n\t\t\t\tif (HT[i].weight < HT[min1].weight) {\n\t\t\t\t\tmin2 = min1;\n\t\t\t\t\tmin1 = i;\n\t\t\t\t}\n\t\t\t\telse if (HT[i].weight < HT[min2].weight) {\n\t\t\t\t\tmin2 = i;\n\t\t\t\t}\n\t\t\t}\n\t\t}\n\t}\n\t*s1 = min1;\n\t*s2 = min2;\n}\n\n\n\n\n\n\n\/*******************************************************************************************************************************\n * @description\uff1a\u6784\u9020Huffman\u6811\n * @param\uff1aHT\n * @param\uff1aw\n * @param\uff1an\n *\/\nvoid createHuffmanTree(HuffmanTree HT, int* w, int n)\n{\n\tif (n <= 1) {\n\t\treturn;\n\t}\n\tint m = 2 * n - 1;\t\/\/ \u7ed3\u70b9\u603b\u6570\n\tHT = (HuffmanTree)malloc((m + 1) * sizeof(HTNode));\n\n\t\/\/ \u521d\u59cb\u5316\n\tfor (int i = 1; i <= m; i++) {\n\t\tHT[i].parent = 0;\n\t\tHT[i].leftchild = 0;\n\t\tHT[i].rightchild = 0;\n\t}\n\n\t\/\/ \u7ed9\u524dn\u4e2a\u7ed3\u70b9\u8d4b\u6743\u503c\n\tfor (int i = 1; i <= n; i++) {\n\t\tHT[i].weight = w[i - 1];\n\t}\n\n\t\/\/ \u5408\u5e76\u4ea7\u751fn-1\u4e2a\u7ed3\u70b9\u2014\u2014\u6784\u9020Huffman\u6811\n\tfor (int i = n + 1; i <= m; i++) {\n\t\t\/\/ \u5728HT[1...i-1]\u4e2d\u9009\u62e9parent\u4e3a0\u4e14weight\u6700\u5c0f\u7684\u4e24\u4e2a\u7ed3\u70b9\uff0c\u5176\u5e8f\u53f7\u5206\u522b\u4e3as1\u548cs2\n\t\tint s1, s2;\n\t\tselect(HT, i - 1, &s1, &s2);\n\t\tHT[s1].parent = i;\n\t\tHT[s2].parent = i;\n\t\tHT[i].leftchild = s1;\n\t\tHT[i].rightchild = s2;\n\t\tHT[i].weight = HT[s1].weight + HT[s2].weight;\n\n\t}\n}\n<\/code><\/pre>\n5.7.3 \u54c8\u592b\u66fc\u7f16\u7801<\/h3>\n
\n
\n
![\"img\"](\"https:\/\/picture.chentaiyang.space\/202304251440893.png\")
<\/p>\n\u7f16\u7801\u7684\u5b9e\u73b0<\/h4>\n
![\"img\"](\"https:\/\/picture.chentaiyang.space\/202304251440064.png\")
<\/p>\n\/*******************************************************************************************************************************\n * @description\uff1a\u4ece\u53f6\u5b50\u5230\u6839\u9006\u5411\u6c42\u6bcf\u4e2a\u5b57\u7b26\u7684\u54c8\u592b\u66fc\u7f16\u7801\n * @param\uff1aHT\n * @param\uff1aHC\n * @param\uff1an\n *\/\nvoid HuffmanCoding(HuffmanTree HT, HuffmanCode* HC, int n)\n{\n\t*HC = (HuffmanCode)malloc((n + 1) * sizeof(char*));\n\tchar* cd = (char*)malloc(n * sizeof(char));\n\tcd[n - 1] = '\\0';\n\tfor (int i = 1; i <= n; i++) {\n\t\tint start = n - 1;\n\t\tint c = i;\n\t\tint p = HT[i].parent;\n\t\twhile (p != 0) {\n\t\t\t--start;\n\t\t\tif (HT[p].leftchild == c) {\n\t\t\t\tcd[start] = '0';\n\t\t\t}\n\t\t\telse {\n\t\t\t\tcd[start] = '1';\n\t\t\t}\n\t\t\tc = p;\n\t\t\tp = HT[p].parent;\t\/\/ \u7ee7\u7eed\u5411\u4e0a\u56de\u6eaf\n\t\t}\n\t\t(*HC)[i] = (char*)malloc((n - start) * sizeof(char));\n\t\tstrcpy((*HC)[i], &cd[start]);\n\t}\n\tfree(cd);\n}\n<\/code><\/pre>\n5.8 \u6848\u4f8b\u5206\u6790\u4e0e\u5b9e\u73b0<\/h2>\n
5.8.1 \u6587\u4ef6\u7684\u7f16\u7801\u4e0e\u89e3\u7801<\/h3>\n
![\"img\"](\"https:\/\/picture.chentaiyang.space\/202304251440899.png\")
<\/p>\n![\"img\"](\"https:\/\/picture.chentaiyang.space\/202305041317338.png\")
<\/p>\n\u7f16\u7801<\/h4>\n
\n
\u89e3\u7801<\/h4>\n
\n
5.9 \u5199\u5728\u6700\u540e<\/h2>\n