{"id":620,"date":"2021-09-06T14:36:49","date_gmt":"2021-09-06T06:36:49","guid":{"rendered":"https:\/\/swordofmorning.com\/?p=620"},"modified":"2025-10-09T13:55:52","modified_gmt":"2025-10-09T05:55:52","slug":"pgexam-data-structure-03","status":"publish","type":"post","link":"https:\/\/swordofmorning.com\/index.php\/2021\/09\/06\/pgexam-data-structure-03\/","title":{"rendered":"\u8003\u7814\u6570\u636e\u7ed3\u6784 03 \u6811\u4e0e\u4e8c\u53c9\u6811 – \u57fa\u7840\u5185\u5bb9"},"content":{"rendered":"
\n
<\/path><\/path><\/path><\/path><\/path><\/path><\/path><\/path><\/path><\/path><\/path><\/defs>\u6811<\/text><\/g><\/use><\/use><\/use><\/use><\/svg><\/use><\/svg><\/g>\u4e8c<\/text><\/g>\u53c9<\/text><\/g>\u6811<\/text><\/g><\/use><\/use><\/use><\/use><\/svg><\/use><\/svg><\/g>\u6982<\/text><\/g>\u5ff5<\/text><\/g><\/g><\/g><\/g>\u64cd<\/text><\/g>\u4f5c<\/text><\/g><\/use><\/g>\u904d<\/text><\/g>\u5386<\/text><\/g><\/g><\/g><\/g>\u641c<\/text><\/g>\u7d22<\/text><\/g>\u4e8c<\/text><\/g>\u53c9<\/text><\/g>\u6811<\/text><\/g><\/g><\/g><\/g><\/g><\/g><\/g><\/g><\/g><\/g><\/g><\/g>\u5e94<\/text><\/g>\u7528<\/text><\/g><\/use><\/g>\u5e73<\/text><\/g>\u8861<\/text><\/g>\u4e8c<\/text><\/g>\u53c9<\/text><\/g>\u6811<\/text><\/g>\uff08<\/text><\/g><\/use><\/g><\/use><\/g><\/use><\/g>\uff09<\/text><\/g><\/g><\/g><\/g>\u54c8<\/text><\/g>\u592b<\/text><\/g>\u66fc<\/text><\/g>\u6811<\/text><\/g><\/g><\/g><\/g><\/g><\/g><\/g><\/g><\/g><\/g><\/g><\/g><\/g><\/g><\/g><\/g><\/g><\/g><\/g>\u6811<\/text><\/g>\u548c<\/text><\/g>\u68ee<\/text><\/g>\u6797<\/text><\/g><\/use><\/use><\/use><\/use><\/svg><\/use><\/svg><\/g>\u6982<\/text><\/g>\u5ff5<\/text><\/g><\/g><\/g><\/g>\u64cd<\/text><\/g>\u4f5c<\/text><\/g><\/use><\/g>\u4e0e<\/text><\/g>\u4e8c<\/text><\/g>\u53c9<\/text><\/g>\u6811<\/text><\/g>\u7684<\/text><\/g>\u8f6c<\/text><\/g>\u6362<\/text><\/g><\/g><\/g><\/g>\u904d<\/text><\/g>\u5386<\/text><\/g><\/g><\/g><\/g><\/g><\/g><\/g><\/g><\/g><\/g><\/g>\u5e94<\/text><\/g>\u7528<\/text><\/g>\uff1a<\/text><\/g>\u5e76<\/text><\/g>\u67e5<\/text><\/g>\u96c6<\/text><\/g><\/g><\/g><\/g><\/g><\/g><\/g><\/g><\/g><\/g><\/g><\/g><\/g><\/g><\/g><\/g><\/g><\/g><\/g><\/g><\/g><\/g><\/g><\/svg><\/use><\/use><\/use><\/g><\/g><\/g><\/svg><\/g><\/g><\/g><\/g><\/svg><\/mjx-container><\/div>\n<\/div>\n

<\/div><\/p>\n

\u4e00\u3001\u6811\u7684\u57fa\u672c\u6982\u5ff5<\/h2>\n

1.1 \u57fa\u672c\u672f\u8bed<\/h3>\n

  \u57fa\u672c\u6982\u5ff5\u5df2\u7ecf\u6e05\u6670\u660e\u4e86\uff0c\u4e0b\u9762\u56de\u987e\u4e0b\u5e38\u7528\u7684\u672f\u8bed\u3002<\/p>\n

    \n
  1. \u9ad8\u5ea6\u4e0e\u6df1\u5ea6\uff1a\u5bf9\u4e8e\u67d0\u4e2a\u8282\u70b9\u6765\u8bf4\uff0c\u5176\u6df1\u5ea6<\/strong>\u4ece\u6839\u8282\u70b9\u5411\u4e0b<\/strong>\u5230\u5f53\u524d\u8282\u70b9\u7d2f\u52a0\uff1b\u5176\u9ad8\u5ea6<\/strong>\u4ece\u5f53\u524d\u8282\u70b9\u5411\u4e0a<\/strong>\u7d2f\u52a0\u5230\u6839\u8282\u70b9\u3002\u4e8c\u8005\u540c\u4e00\u3002\u8fd9\u91cc\u5bf9\u7a7a\u6811\u7684\u9ad8\u5ea6\/\u6df1\u5ea6\u8bb0\u5f55\u67090\u548c-1\u4e24\u79cd\uff08\u53ea\u6709\u6839\u8282\u70b9\u7684\u6570\u5219\u662f1\u548c0\uff09\uff0c\u5177\u4f53\u60c5\u51b5\u5177\u4f53\u9009\u62e9\u3002<\/li>\n
  2. \u7236\u8282\u70b9\u4e0e\u5b50\u8282\u70b9\uff1a\u4e0d\u8a00\u81ea\u660e\u3002<\/li>\n
  3. \u8282\u70b9\u7684\u5ea6\uff1a\u4e00\u4e2a\u8282\u70b9\u7684\u5b50\u8282\u70b9\u6570\u3002<\/li>\n
  4. \u6811\u7684\u5ea6\uff1a\u6811\u4e2d\u6700\u5927\u7684\uff08\u8282\u70b9\u7684\uff09\u5ea6\u3002<\/li>\n
  5. \u5c42\u6b21\uff1a\u4e0d\u8a00\u81ea\u660e\u3002<\/li>\n
  6. \u6709\u5e8f\u6811\uff1a\u5bf9\u4e8e\u4efb\u610f\u5b50\u6811\uff0c\u5176\u6839\u8282\u70b9\u4e3ab\u3002b\u7684\u5de6\u5b50\u6811a\u7684\u6240\u6709\u8282\u70b9\u603b\u5c0f\u4e8eb\uff0cb\u7684\u53f3\u5b50\u6811c\u7684\u6240\u6709\u8282\u70b9\u603b\u5927\u4e8eb\u3002\u6392\u5e8f\u51c6\u5219\u81ea\u5b9a\u3002<\/li>\n
  7. \u8def\u5f84\u548c\u8def\u5f84\u957f\u5ea6\uff1a\u503c\u5f97\u6ce8\u610f\u7684\u662f\uff0c\u88ab\u8ba1\u7b97\u7684\u4e24\u4e2a\u8282\u70b9\u4e0d\u80fd\u8de8\u6811\u3002<\/li>\n
  8. \u68ee\u6797\uff1a\u4e00\u68f5\u6811\u6ca1\u6709\u4e86\u6839\u8282\u70b9\uff0c\u5219\u662f\u591a\u9897\u4e92\u4e0d\u76f8\u4ea4\u7684\u6811\uff0c\u5219\u662f\u68ee\u6797\u3002<\/li>\n<\/ol>\n

    1.2 \u6027\u8d28<\/h3>\n
      \n
    1. \u6811\u6570\u4e2d\u7684\u8282\u70b9\u6811\u7b49\u4e8e\u6240\u6709\u8282\u70b9\u7684\u5ea6\u6570+1\uff0c\u4eba\u8bdd\uff1a\u5b50\u8282\u70b9\u81ea\u5df1\u672c\u8eab\u7684\u8ba1\u6570\u603b\u662f\u88ab\u9012\u5f52\u5230\u7236\u8282\u70b9\u4e0a\u53bb\uff0c\u79f0\u4e3a\u201c\u5ea6\u201d\u3002<\/li>\n
    2. \u5ea6<\/strong>\u4e3am\u7684\u6811\u4e2d\u7b2ci\u5c42\u4e0a\u81f3\u591a\u6709mi-1<\/sup>\u4e2a\u8282\u70b9(i>=1)\uff0c\u4eba\u8bdd\uff1a\u6b32\u8bc1\u660e\uff0c\u5168\u653e\u7b2c\u4e8c\u5c42\u8bd5\u8bd5\u3002<\/li>\n
    3. \u9ad8\u5ea6<\/strong>\u4e3ah\u7684m\u53c9\u6811\u81f3\u591a\u6709(mh<\/sup>-1)\/(m-1)\u4e2a\u8282\u70b9\u3002<\/li>\n
    4. \u5177\u6709n\u4e2a\u8282\u70b9\u7684m\u53c9\u6811\u7684\u6700\u5c0f\u9ad8\u5ea6\u4e3alogm<\/sub>(n(m-1)+1)\u3002<\/li>\n<\/ol>\n

      \u4e8c\u3001\u4e8c\u53c9\u6811<\/h2>\n

      2.1 \u5b9a\u4e49\u4e0e\u4e3b\u8981\u7279\u6027<\/h3>\n

        \u4e8c\u53c9\u6811\u662f\u53e6\u4e00\u79cd\u6811\u5f62\u7ed3\u6784\uff0c\u5176\u7279\u663e\u662f\u6bcf\u4e2a\u8282\u70b9\u81f3\u591a\u53ea\u80fd\u6709\u4e24\u4e2a\u5b50\u6811\uff0c\u5e76\u4e14\u4e8c\u53c9\u6811\u6709\u5de6\u53f3\u4e4b\u5206\u3002<\/p>\n

        \u7279\u522b\u7684\u4e8c\u53c9\u6811\uff1a<\/strong><\/p>\n

        \n
      1. \u6ee1\u4e8c\u53c9\u6811\uff1a\u9ad8\u5ea6\u4e3ah\uff0c\u4e14\u8282\u70b9\u4e3a2h<\/sup>-1\u4e2a\u8282\u70b9\u7684\u4e8c\u53c9\u6811\uff0c\u5176\u4e2d\u6bcf\u4e00\u5c42\u90fd\u6709\u6700\u591a\u7684\u8282\u70b9\uff0c\u5904\u53f6\u8282\u70b9\u5916\u6bcf\u4e2a\u8282\u70b9\u7684\u5ea6\u5747\u4e3a2\u3002<\/li>\n
      2. \u5b8c\u5168\u4e8c\u53c9\u6811\uff1a\u4e0d\u6ee1\u7684\u6ee1\u4e8c\u53c9\u6811\u3002\u5728\u4e00\u9897\u4e8c\u53c9\u6811\u4e2d\uff0c\u82e5\u9664\u6700\u540e\u4e00\u5c42\u5916\u7684\u5176\u4f59\u5c42\u90fd\u662f\u6ee1\u7684\uff0c\u5e76\u4e14\u6700\u540e\u4e00\u5c42\u8981\u4e48\u662f\u6ee1\u7684\uff0c\u8981\u4e48\u5728\u53f3\u8fb9\u7f3a\u5c11\u8fde\u7eed\u82e5\u5e72\u8282\u70b9\uff0c\u5219\u6b64\u4e8c\u53c9\u6811\u4e3a\u5b8c\u5168\u4e8c\u53c9\u6811\u3002\u5177\u6709n\u4e2a\u8282\u70b9\u7684\u5b8c\u5168\u4e8c\u53c9\u6811\u7684\u6df1\u5ea6\u4e3alog2<\/sub>n+1\u3002\u6df1\u5ea6\u4e3ak\u7684\u5b8c\u5168\u4e8c\u53c9\u6811\uff0c\u81f3\u5c11\u67092k-1<\/sup>\u4e2a\u8282\u70b9\uff0c\u81f3\u591a\u67092k<\/sup>-1\u4e2a\u8282\u70b9\u3002<\/li>\n
      3. \u4e8c\u53c9\u6392\u5e8f\u6811\uff1a\u5bf9\u4e8e\u4efb\u610f\u5b50\u6811\uff0c\u5176\u5de6\u8282\u70b9\u603b\u5c0f\u4e8e\u53f3\u8282\u70b9\uff0c\u6392\u5e8f\u51c6\u5219\u81ea\u5b9a\u3002<\/li>\n
      4. \u5e73\u8861\u4e8c\u53c9\u6811\uff1a\u6811\u4e0a\u4efb\u610f\u4e00\u4e2a\u8282\u70b9\u5de6\u53f3\u5b50\u6811\u6df1\u5ea6\u5dee\u4e0d\u8d85\u8fc71\u3002<\/li>\n<\/ol>\n

        2.2 \u5b58\u50a8\u7ed3\u6784<\/h3>\n
        struct BinaryNode\n{\n    eleType ele;\n    BinaryNode* left;\n    BinaryNode* right;\n}\n<\/code><\/pre>\n
        2.3 \u904d\u5386<\/h3>\n
        2.3.1 \u5148\u5e8f\u904d\u5386<\/h4>\n
          \n
        1. \u8bbf\u95ee\u6839\u8282\u70b9<\/li>\n
        2. \u5148\u5e8f\u904d\u5386\u5de6\u5b50\u6811<\/li>\n
        3. \u5148\u5e8f\u904d\u5386\u53f3\u5b50\u6811<\/li>\n<\/ol>\n
          void preOrder(BinaryNode* node)\n{\n    if (node)\n    {\n        visit(node);\n        preOrder(node->left);\n        preOrder(node->right);\n    }\n}\n<\/code><\/pre>\n
          2.3.2 \u4e2d\u5e8f\u904d\u5386<\/h4>\n
            \n
          1. \u4e2d\u5e8f\u904d\u5386\u5de6\u5b50\u6811<\/li>\n
          2. \u8bbf\u95ee\u6839\u8282\u70b9<\/li>\n
          3. \u4e2d\u5e8f\u904d\u5386\u53f3\u5b50\u6811<\/li>\n<\/ol>\n
            void inOrder(BinaryNode* node)\n{\n    if (node)\n    {\n        inOrder(node->left);\n        visit(node);\n        inOrder(node->right);\n    }\n}\n<\/code><\/pre>\n
            2.3.3 \u540e\u5e8f\u904d\u5386<\/h4>\n
              \n
            1. \u540e\u5e8f\u904d\u5386\u5de6\u5b50\u6811<\/li>\n
            2. \u540e\u5e8f\u904d\u5386\u53f3\u5b50\u6811<\/li>\n
            3. \u8bbf\u95ee\u6839\u8282\u70b9<\/li>\n<\/ol>\n
              void postOrder(BinaryNode* node)\n{\n    if (node)\n    {\n        postOrder(node->left);\n        postOrder(node->right);\n        visit(node);\n    }\n}\n<\/code><\/pre>\n
              2.3.4 \u5c42\u6b21\u904d\u5386<\/h4>\n
              void levelOrder(BinaryNode* root)\n{\n    if (!root)  return;\n\n    \/\/ \u961f\u5217\n    std::deque<BinaryNode*> qu;\n\n    \/\/ \u5c06\u6839\u8282\u70b9\u653e\u5165\u961f\u5217\n    qu.push_back(root);\n\n    \/\/ while (\u961f\u5217\u4e0d\u7a7a)\n    while (!qu.empty())\n    {\n        \/\/ \u961f\u9996\u51fa\u5217\uff0c\u8bbf\u95ee\u4e4b\u3002\n        BinaryNode* head = qu.front();\n        qu.pop_front();\n        visit(head);\n\n        \/\/ \u82e5\u6709\u5de6\u8282\u70b9\uff0c\u538b\u5165\u961f\u5217\uff1b\n        if (head->left)  qu.push_back(head->left);\n\n        \/\/ \u82e5\u6709\u53f3\u8282\u70b9\uff0c\u538b\u5165\u961f\u5217\u3002\n        if (head->right)  qu.push_back(head->right);        \n    }\n}\n<\/code><\/pre>\n
              2.4 \u7531\u904d\u5386\u6784\u9020\u4e8c\u53c9\u6811<\/h3>\n
              2.4.1 \u7531\u540e\u5e8f\u548c\u4e2d\u5e8f\u904d\u5386\u6784\u9020\u4e8c\u53c9\u6811<\/h4>\n
                \u73b0\u5728\u6211\u4eec\u6709\u5982\u4e0b\u4f8b\u5b50\uff1a<\/p>\n
                \n
              • \u4e2d\u5e8f\uff1aBFDAEGC<\/li>\n
              • \u540e\u5e8f\uff1aFDBGECA<\/li>\n<\/ul>\n
                2.4.1.1 \u7b97\u6cd5\u63cf\u8ff0<\/h5>\n
                  \n
                1. \u901a\u8fc7\u540e\u5e8f\u904d\u5386\u786e\u5b9a\u6839\u8282\u70b9A\u3002<\/li>\n
                2. \u5728\u4e2d\u5e8f\u4e2d\u786e\u5b9aA\u7684\u5de6<\/strong>\u53f3<\/u>\u5b50\u6811\uff1a
                  \n\u4e2d\u5e8f\uff1aBFD<\/strong> A EGC<\/u>
                  \n\u540e\u5e8f\uff1aFDB<\/strong> GEC<\/u> A<\/li>\n
                3. \u5bf9\u6bcf\u4e2a\u5b50\u6811\u91cd\u590d\u4ee5\u4e0a\u76f4\u5230\u6bcf\u4e2a\u5b50\u6811\u53ea\u6709\u4e00\u4e2a\u6839\u8282\u70b9<\/li>\n<\/ol>\n
                    \u4e0a\u6811\u7684\u6700\u7ec8\u7ed3\u679c\uff1a
                  \n
                  \"\u56fe1\"
                  \u56fe1\uff1a\u7531\u4e2d\u5e8f\u548c\u540e\u5e8f\u786e\u5b9a\u5148\u5e8f<\/figcaption><\/figure><\/p >\n