{"id":636,"date":"2021-09-09T14:46:37","date_gmt":"2021-09-09T06:46:37","guid":{"rendered":"https:\/\/swordofmorning.com\/?p=636"},"modified":"2025-10-09T13:55:51","modified_gmt":"2025-10-09T05:55:51","slug":"pgexam-data-structure-04","status":"publish","type":"post","link":"https:\/\/swordofmorning.com\/index.php\/2021\/09\/09\/pgexam-data-structure-04\/","title":{"rendered":"\u8003\u7814\u6570\u636e\u7ed3\u6784 04 Binary Search Tree"},"content":{"rendered":"<p><div class=\"has-toc have-toc\"><\/div><\/p>\n<h2>\u4e00\u3001\u4e8c\u53c9\u6811\u8282\u70b9<\/h2>\n<p>&emsp;&emsp;\u8fd9\u91cc\u9700\u8981\u6ce8\u610f\u7684\u662f\uff0c\u5982\u679c\u4ee5\u6a21\u677f\u65b9\u6cd5\u6784\u9020\u4e8c\u53c9\u6811\uff0c\u63a8\u8350\u5c06\u5185\u90e8\u8282\u70b9\u7c7b\u4e5f\u58f0\u660e\u4e00\u4e2a\u6a21\u677f\uff0c\u5426\u5219\u7c7b\u5916\u51fd\u6570\uff08\u58f0\u660e\u5728h\u6587\u4ef6\uff0c\u5b9e\u73b0\u5728cpp\u6587\u4ef6\uff09\u7684\u8fd4\u56de\u7c7b\u578b\u4e0d\u80fd\u662fNode*\uff0c\u4f7f\u7528\u6a21\u677f\u540e\u5219\u53ef\u4ee5\u4f7f\u7528BinaryTree\\&lt;elemTYpe>::Node\\&lt;elemType>*\u3002<\/p>\n<ul>\n<li>\u5b8c\u6574\u9879\u76ee\uff1a<a href=\"https:\/\/github.com\/SwordofMorning\/pgExamBinaryTree\" title=\"pgExamBinaryTree\" target=\"_blank\"  rel=\"nofollow\" >pgExamBinaryTree<\/a><\/li>\n<\/ul>\n<pre><code class=\"language-cpp\">template&lt;typename elemType&gt;\nclass BinaryTree\n{\nprivate:\n    \/* ===== Member 00 : \u4e8c\u53c9\u6811\u8282\u70b9 ===== *\/\n    template&lt;typename elemType&gt;\n    class Node\n    {\n    public:\n        elemType element;\n        Node* left;\n        Node* right;\n\n        \/\/ \u6784\u9020\u51fd\u6570\n        Node(const elemType&amp; p_ele, Node* p_lt, Node* p_rt)\n            : element(p_ele), left(p_lt), right(p_rt) { }\n\n        Node(elemType&amp;&amp; p_ele, Node* p_lt, Node* p_rt)\n            : element(p_ele), left(p_lt), right(p_rt) { }\n    };\n\n    \/* ===== Member 01 : \u6839\u8282\u70b9 ===== *\/\n    Node&lt;elemType&gt;* root;\n}<\/code><\/pre>\n<h2>\u4e8c\u3001\u67e5\u627e<\/h2>\n<p>&emsp;&emsp;\u904d\u5386\u5728pgExam03\u4e2d\u5df2\u7ecf\u5199\u8fc7\uff0c\u8fd9\u91cc\u4e0d\u518d\u8d58\u8ff0\u3002<\/p>\n<h3>2.1 \u6309\u503c\u67e5\u627e<\/h3>\n<pre><code class=\"language-cpp\">template&lt;typename elemType&gt;\nBinaryTree&lt;elemType&gt;::Node&lt;elemType&gt;* BinaryTree&lt;elemType&gt;::FindVal(const elemType&amp; ele, Node&lt;elemType&gt;* node)\n{\n    \/\/ \u7a7a\u8282\u70b9\n    if (!node) return nullptr;\n\n    \/\/ \u662f\u5f53\u524d\u8282\u70b9\n    if (node-&gt;element == ele) return node;\n\n    \/\/ \u67e5\u5de6\u5b50\u6811\n    Node&lt;elemType&gt;* lt = nullptr;\n    lt = this-&gt;FindVal(ele, node-&gt;left);\n\n    if (lt) return lt;\n\n    \/\/ \u67e5\u53f3\u5b50\u6811\n    Node&lt;elemType&gt;* rt = nullptr;\n    rt = this-&gt;FindVal(ele, node-&gt;right);\n\n    if (rt) return rt;\n\n    \/\/ \u65e0\u7ed3\u679c\n    return nullptr;\n}<\/code><\/pre>\n<h3>2.2 \u67e5\u627e\u6700\u503c<\/h3>\n<pre><code class=\"language-cpp\">\/* ===== Function 08 : \u67e5\u627e\u6700\u5c0f\u503c ===== *\/\ntemplate&lt;typename elemType&gt;\nBinaryTree&lt;elemType&gt;::Node&lt;elemType&gt;* BinaryTree&lt;elemType&gt;::FindMin(Node&lt;elemType&gt;* node)\n{\n    if (!node) return nullptr;\n\n    if (!node-&gt;left) return node;\n\n    return FindMin(node-&gt;left);\n}\n\n\/* ===== Function 09 : \u67e5\u627e\u6700\u5927\u503c ===== *\/\ntemplate&lt;typename elemType&gt;\nBinaryTree&lt;elemType&gt;::Node&lt;elemType&gt;* BinaryTree&lt;elemType&gt;::FindMax(Node&lt;elemType&gt;* node)\n{\n    if (!node) return nullptr;\n\n    if (!node-&gt;right) return node;\n\n    return FindMax(node-&gt;right);\n}<\/code><\/pre>\n<h2>\u4e09\u3001\u63d2\u5165\u4e0e\u5220\u9664<\/h2>\n<h3>3.1 \u63d2\u5165<\/h3>\n<p>&emsp;&emsp;\u8fd9\u91cc\u6211\u4eec\u9010\u6b21\u6bd4\u8f83\uff0c\u627e\u5230\u5408\u9002\u7684\u4f4d\u7f6e\u5c31\u63d2\u5165\u3002<\/p>\n<pre><code class=\"language-cpp\">template&lt;typename elemType&gt;\nvoid BinaryTree&lt;elemType&gt;::Insert(const elemType&amp; ele, Node&lt;elemType&gt;*&amp; node)\n{\n    \/\/ \u6709\u7a7a\u4f4d\u63d2\n    if (!node)\n    {\n        node = new Node&lt;elemType&gt;(ele, nullptr, nullptr);\n    }\n    \/\/ \u8fd9\u4e2a\u7a7a\u4f4d\u6709\u4eba\u4e86\uff0c\u548c\u4ed6\u6bd4\u8f83\u4e0b\uff0c\u6309\u4e00\u5b9a\u6392\u5e8f\u51c6\u5219\u9009\u62e9\u5de6\u53f3\uff0c\u8fd9\u91cc\u4ee5 &lt; \u4e3a\u6392\u5e8f\u51c6\u5219\u3002\n    else if (ele &lt; node-&gt;element)\n    {\n        this-&gt;Insert(ele, node-&gt;left);\n    }\n    else if (node-&gt;element &lt; ele)\n    {\n        this-&gt;Insert(ele, node-&gt;right);\n    }\n}<\/code><\/pre>\n<h3>3.2 \u5220\u9664<\/h3>\n<p>&emsp;&emsp;\u627e\u5230\u5f53\u524d\u8282\u70b9\u7684\u5927\u4e00\u503c\u6216\u5c0f\u4e00\u503c\uff08\u4e2d\u5e8f\u904d\u5386\u76f8\u90bb\u7684\u503c\uff09\u6765\u66ff\u6362\u8fd9\u4e2a\u8282\u70b9<\/p>\n<pre><code class=\"language-cpp\">template&lt;typename elemType&gt;\nvoid BinaryTree&lt;elemType&gt;::Remove_val(const elemType&amp; ele, Node&lt;elemType&gt;*&amp; node)\n{\n    if (!node) return;\n\n    \/\/ \u4e0d\u662f\u76ee\u6807\uff0c\u6bd4\u8f83\n    if (ele &lt; node-&gt;element)\n        this-&gt;Remove_val(ele, node-&gt;left);\n    else if (ele &gt; node-&gt;element)\n        this-&gt;Remove_val(ele, node-&gt;left);\n    \/\/ \u627e\u5230\u76ee\u6807\n    else if (node-&gt;left &amp;&amp; node-&gt;right)       \/\/ \u88ab\u5220\u9664\u76ee\u6807\u6709\u4e24\u4e2a\u8282\u70b9\n    {\n        \/\/ \u53ef\u66ff\u6362\u5de6\u5b50\u6811\u7684\u6700\u5927\u503c\u3001\u53f3\u5b50\u6811\u7684\u6700\u5c0f\u503c\uff08\u4e2d\u5e8f\u5411\u91cf\u7684\u4e24\u4e2a\u70b9\uff0c\u9009\u4e00\uff09\n        node-&gt;element = this-&gt;FindMin(node-&gt;right)-&gt;element;\n        \/\/ \u66f4\u65b0\u5220\u9664\u76ee\u6807\n        Remove_val(node-&gt;element, node-&gt;right);\n    }\n    else                                    \/\/ \u88ab\u5220\u9664\u76ee\u6807\u53ea\u6709\u4e00\u4e2a\u8282\u70b9\u6216\u65e0\u8282\u70b9\n    {\n        Node&lt;elemType&gt;* oldOne = node;\n        node = (node-&gt;left) ?\n            node-&gt;left :\n            node-&gt;right;\n        delete oldOne;\n    }\n}<\/code><\/pre>\n<h2>\u56db\u3001\u9ad8\u5ea6\u4e0e\u5bbd\u5ea6<\/h2>\n<h3>4.1 \u9ad8\u5ea6<\/h3>\n<pre><code class=\"language-cpp\">template&lt;typename elemType&gt;\nint BinaryTree&lt;elemType&gt;::Height(Node&lt;elemType&gt;* node)\n{\n    if (!node)  return 0;\n\n    return std::max(this-&gt;Height(node-&gt;left), this-&gt;Height(node-&gt;right)) + 1;\n}<\/code><\/pre>\n<h3>4.2 \u5bbd\u5ea6<\/h3>\n<p>&emsp;&emsp;\u5bbd\u5ea6\u7ed3\u5408\u5c42\u6b21\u904d\u5386\u6765\u5224\u65ad\uff0c\u5b8c\u5168\u4e8c\u53c9\u6811\u7684\u5224\u65ad\u4e5f\u7528\u6b64\u79cd\u65b9\u6cd5\u3002<\/p>\n<pre><code class=\"language-cpp\">template&lt;typename elemType&gt;\nint BinaryTree&lt;elemType&gt;::Width(Node&lt;elemType&gt;* node)\n{\n    if (!node)  return 0;\n\n    std::deque&lt;Node&lt;elemType&gt;*&gt; dq;\n    dq.push_back(node);\n\n    int maxWidth = 1;\n    int currentWidth = 1;\n\n    while (!dq.empty())\n    {\n        while (currentWidth &gt; 0)\n        {\n            \/\/ \u961f\u9996\u51fa\u961f\uff0c\u5c06\u4e0b\u4e00\u5c42\u538b\u5165\u961f\u5217\n            Node&lt;elemType&gt;* head = dq.front();\n            dq.pop_front();\n\n            if (head-&gt;left)  dq.push_back(head-&gt;left);\n            if (head-&gt;right) dq.push_back(head-&gt;right);\n\n            currentWidth--;\n        }\n\n        \/\/ \u4e0b\u4e00\u5c42\u7684\u8282\u70b9\u6570\n        currentWidth = dq.size();\n\n        maxWidth = (maxWidth &lt; currentWidth) ?\n            currentWidth :\n            maxWidth;\n    }\n\n    return maxWidth;\n}<\/code><\/pre>\n<h2>\u4e94\u3001\u5b8c\u5168\u3001\u5e73\u8861\u4e0e\u65cb\u8f6c<\/h2>\n<h3>5.1 \u5b8c\u5168\u4e8c\u53c9\u6811<\/h3>\n<pre><code class=\"language-cpp\">template&lt;typename elemType&gt;\nbool BinaryTree&lt;elemType&gt;::is_Complete(Node&lt;elemType&gt;* node)\n{\n    if (!node)  return false;\n\n    std::deque&lt;Node&lt;elemType&gt;*&gt; dq;\n    dq.push_back(node);\n\n    int currentWidth = 1;\n    int currentLevel = 0;\n\n    while (!dq.empty())\n    {\n        while (currentWidth &gt; 0)\n        {\n            \/\/ \u961f\u9996\u51fa\u961f\uff0c\u5c06\u4e0b\u4e00\u5c42\u538b\u5165\u961f\u5217\n            Node&lt;elemType&gt;* head = dq.front();\n            dq.pop_front();\n\n            if (head-&gt;left)  dq.push_back(head-&gt;left);\n            if (head-&gt;right) dq.push_back(head-&gt;right);\n\n            currentWidth--;\n        }\n\n        \/\/ \u4e0b\u4e00\u5c42\u7684\u8282\u70b9\u6570\n        currentWidth = dq.size();\n        currentLevel++;\n\n        if ((currentWidth != pow(2, currentLevel))&amp;&amp; (currentWidth != 0))\n        {\n            return false;\n        }\n    }\n\n    return true;\n}<\/code><\/pre>\n<h3>5.2 \u5e73\u8861\u4e8c\u53c9\u6811<\/h3>\n<pre><code class=\"language-cpp\">template&lt;typename elemType&gt;\nbool BinaryTree&lt;elemType&gt;::is_Avl(Node&lt;elemType&gt;* node, int&amp; height)\n{\n    if (!node)\n    {\n        height = 0;\n        return true;\n    }\n\n    \/\/ left height\n    int lh(0);\n    \/\/ left flag\n    bool lf = this-&gt;is_Avl(node-&gt;left, lh);\n\n    \/\/ right\n    int rh(0);\n    bool rf = this-&gt;is_Avl(node-&gt;right, rh);\n\n    if (lf &amp;&amp; rf &amp;&amp; abs(lh - rh) &lt;= 1)\n    {\n        height = std::max(lh, rh) + 1;\n    }\n    else\n    {\n        height = std::max(lh, rh) + 1;\n        return false;\n    }\n\n    return true;\n}<\/code><\/pre>\n<h3>5.3 \u65cb\u8f6c<\/h3>\n<pre><code class=\"language-cpp\">template&lt;typename elemType&gt;\nBinaryTree&lt;elemType&gt;::Node&lt;elemType&gt;* BinaryTree&lt;elemType&gt;::Mirror(Node&lt;elemType&gt;* node)\n{\n    if (!node)  return nullptr;\n\n    Node&lt;elemType&gt;* lt = this-&gt;Mirror(node-&gt;left);\n    Node&lt;elemType&gt;* rt = this-&gt;Mirror(node-&gt;right);\n\n    node-&gt;left = rt;\n    node-&gt;right = lt;\n\n    return node;\n}<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"<p>\u4e00\u3001\u4e8c\u53c9\u6811\u8282\u70b9 &emsp;&emsp;\u8fd9\u91cc\u9700\u8981\u6ce8\u610f\u7684\u662f\uff0c\u5982\u679c\u4ee5\u6a21\u677f\u65b9\u6cd5\u6784\u9020\u4e8c\u53c9\u6811\uff0c\u63a8\u8350\u5c06\u5185\u90e8\u8282\u70b9\u7c7b\u4e5f\u58f0\u660e\u4e00\u4e2a\u6a21\u677f\uff0c\u5426\u5219\u7c7b\u5916\u51fd\u6570\uff08 &#8230;<\/p>","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[60],"tags":[],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/swordofmorning.com\/index.php\/wp-json\/wp\/v2\/posts\/636"}],"collection":[{"href":"https:\/\/swordofmorning.com\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/swordofmorning.com\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/swordofmorning.com\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/swordofmorning.com\/index.php\/wp-json\/wp\/v2\/comments?post=636"}],"version-history":[{"count":5,"href":"https:\/\/swordofmorning.com\/index.php\/wp-json\/wp\/v2\/posts\/636\/revisions"}],"predecessor-version":[{"id":642,"href":"https:\/\/swordofmorning.com\/index.php\/wp-json\/wp\/v2\/posts\/636\/revisions\/642"}],"wp:attachment":[{"href":"https:\/\/swordofmorning.com\/index.php\/wp-json\/wp\/v2\/media?parent=636"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/swordofmorning.com\/index.php\/wp-json\/wp\/v2\/categories?post=636"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/swordofmorning.com\/index.php\/wp-json\/wp\/v2\/tags?post=636"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}