{"id":184,"date":"2021-09-05T00:53:44","date_gmt":"2021-09-05T00:53:44","guid":{"rendered":"http:\/\/www.gislxz.top\/?p=184"},"modified":"2022-11-17T08:04:30","modified_gmt":"2022-11-17T08:04:30","slug":"%e6%95%b0%e6%8d%ae%e7%bb%93%e6%9e%847%e4%ba%8c%e5%8f%89%e6%a0%91","status":"publish","type":"post","link":"https:\/\/www.gislxz.com\/index.php\/2021\/09\/05\/%e6%95%b0%e6%8d%ae%e7%bb%93%e6%9e%847%e4%ba%8c%e5%8f%89%e6%a0%91\/","title":{"rendered":"\u6570\u636e\u7ed3\u6784\uff087\uff09\u4e8c\u53c9\u6811"},"content":{"rendered":"\n

\u7528\u6570\u7ec4\u63cf\u8ff0\u4e8c\u53c9\u6811\u4e0d\u592a\u5e38\u7528\uff0c\u6570\u7ec4\u63cf\u8ff0\u662f\u6309\u6ee1\u4e8c\u53c9\u6811\u7684\u7f16\u53f7\u8bb0\u5f55\u6570\u636e\uff0c\u5982\u679c\u5143\u7d20\u6570\u76ee\u5c11\u7684\u65f6\u5019\u5f88\u6d6a\u8d39\u7a7a\u95f4\uff0c\u4e00\u822c\u8fd8\u662f\u7528\u94fe\u8868\u63cf\u8ff0<\/p>\n\n\n\n

\u9996\u5148\u5b9a\u4e49\u8282\u70b9\uff0c\u8282\u70b9\u5305\u62ec\u5143\u7d20\u503c\u548c\u5de6\u53f3\u5b50\u6811\u7684\u6307\u9488\u3002\u901a\u5e38\u8282\u70b9\u4e0d\u5305\u62ec\u6307\u5411\u7236\u8282\u70b9\u7684\u6307\u9488\uff0c\u5982\u6709\u9700\u8981\u4e5f\u53ef\u4ee5\u6dfb\u52a0<\/p>\n\n\n\n

template<class T>\r\nstruct binaryTreeNode {\/\/\u8282\u70b9\r\n\tT element;\r\n\tbinaryTreeNode<T>* leftChild, * rightChild;\/\/\u5de6\u53f3\u5b50\u6811\r\n\tbinaryTreeNode() { leftChild = rightChild = NULL; }\/\/\u9ed8\u8ba4\u6784\u9020\u51fd\u6570;\r\n\tbinaryTreeNode(const T& theElement) {\/\/\u6307\u5b9a\u5143\u7d20\u503c\u7684\u6784\u9020\u51fd\u6570\r\n\t\telement(theElement);\r\n\t\tleftChild = rightChild = NULL;\r\n\t}\r\n\tbinaryTreeNode(const T& theElement, binaryTreeNode* theLeftChild, binaryTreeNode* theRightChild) {\/\/\u5b8c\u6574\u6784\u9020\r\n\t\telement(theElement);\r\n\t\tleftChild = theLeftChild;\r\n\t\trightChild = theRightChild;\r\n\t}\r\n};<\/code><\/pre>\n\n\n\n
\u5148\u4e0d\u6025\u7740\u5b9a\u4e49\u4e8c\u53c9\u6811\u7c7b\uff0c\u5148\u770b\u770b\u56db\u79cd\u904d\u5386\u65b9\u6cd5<\/p>\n\n\n\n
\"\"
\u4ece\u522b\u4eba\u535a\u5ba2\u622a\u7684\u56fe<\/figcaption><\/figure><\/div>\n\n\n\n
\u524d\u4e09\u79cd\u904d\u5386\u901a\u8fc7\u9012\u5f52\u7b97\u6cd5\u90fd\u5f88\u5bb9\u6613\u63cf\u8ff0\uff0c\u8fd0\u7528\u4e86\u6808\u7684\u601d\u60f3<\/p>\n\n\n\n
template<class T>\r\nvoid visit(binaryTreeNode<T>* x) {\r\n\tcout << x->element << \" \";\r\n}\r\n\/*---------\u524d\u5e8f\u904d\u5386------------------*\/\r\ntemplate<class T>\r\nvoid preOrder(binaryTreeNode<T>* t) {\r\n\tif (t != NULL) {\r\n\t\tvisit(t);\r\n\t\tpreOrder(t->leftChild);\r\n\t\tpreOrder(t->rightChild);\r\n\t}\r\n}\r\n\/*--------\u4e2d\u5e8f\u904d\u5386------------------*\/\r\ntemplate<class T>\r\nvoid inOrder(binaryTreeNode<T>* t) {\r\n\tif (t != NULL) {\r\n\t\tinOrder(t->leftChild);\r\n\t\tvisit(t);\r\n\t\tinOrder(t->rightChild);\r\n\t}\r\n}\r\n\/*--------\u540e\u5e8f\u904d\u5386------------------*\/\r\ntemplate<class T>\r\nvoid postOrder(binaryTreeNode<T>* t) {\r\n\tif (t != NULL) {\r\n\t\tpostOrder(t->leftChild);\r\n\t\tpostOrder(t->rightChild);\r\n\t\tvisit(t);\r\n\t}\r\n}<\/code><\/pre>\n\n\n\n
\u5c42\u6b21\u904d\u5386\u590d\u6742\u4e00\u4e9b\uff0c\u9700\u8981\u9010\u5c42\u8f93\u51fa\uff0c\u7528\u5230\u4e86\u961f\u5217<\/p>\n\n\n\n
\/*-------\u5c42\u6b21\u904d\u5386------------------*\/\r\ntemplate<class T>\r\nvoid levelOrder(binaryTreeNode<T>* t) {\r\n\tarrayQueue<binaryTreeNode<T>*> q;\/\/\u5efa\u7acb\u8282\u70b9\u6307\u9488\u961f\u5217\r\n\twhile (t != NULL) {\r\n\t\tvisit(t);\r\n\t\t\/\/\u8f93\u51fa\u7684\u540c\u65f6\u628a\u5de6\u53f3\u5b50\u6811\u63d2\u5165\u961f\u5217\r\n\t\tif (t->leftChild != NULL)\r\n\t\t\tq.push(t->leftChild);\r\n\t\tif (t->rightChild != NULL)\r\n\t\t\tq.push(t->rightChild);\r\n\r\n\t\ttry { t = q.front(); }\r\n\t\tcatch (queueEmpty) { return; }\r\n\t\tq.pop();\r\n\t}\r\n}<\/code><\/pre>\n\n\n\n
\u4e4b\u540e\u662f\u4e8c\u53c9\u6811\u7c7b\u7684\u5b8c\u6574\u5b9a\u4e49<\/p>\n\n\n\n
\r\n\/\/ linked binary tree using nodes of type binaryTreeNode\r\n\/\/ derives from the abstract class binaryTree\r\n\r\n#ifndef linkedBinaryTree_\r\n#define linkedBinaryTree_\r\n\r\nusing namespace std;\r\n\r\n\r\n#include <iostream>\r\n#include \"binaryTree.h\"\r\n#include \"arrayQueue.h\"\r\n#include \"binaryTree.h\"\r\n#include \"myExceptions.h\"\r\n#include \"booster.h\"\r\n#include \"traverse.h\"\r\n\r\ntemplate<class E>\r\nclass linkedBinaryTree : public binaryTree<binaryTreeNode<E> >\r\n{\r\npublic:\r\n    linkedBinaryTree() { root = NULL; treeSize = 0; }\r\n    ~linkedBinaryTree() { erase(); };\r\n    bool empty() const { return treeSize == 0; }\r\n    int size() const { return treeSize; }\r\n    E* rootElement() const;\r\n    void makeTree(const E& element,\r\n        linkedBinaryTree<E>&, linkedBinaryTree<E>&);\r\n    linkedBinaryTree<E>& removeLeftSubtree();\r\n    linkedBinaryTree<E>& removeRightSubtree();\r\n    void preOrder(void(*theVisit)(binaryTreeNode<E>*))\r\n    {\r\n        visit = theVisit; preOrder(root);\r\n    }\r\n    void inOrder(void(*theVisit)(binaryTreeNode<E>*))\r\n    {\r\n        visit = theVisit; inOrder(root);\r\n    }\r\n    void postOrder(void(*theVisit)(binaryTreeNode<E>*))\r\n    {\r\n        visit = theVisit; postOrder(root);\r\n    }\r\n    void levelOrder(void(*)(binaryTreeNode<E>*));\r\n    void preOrderOutput() { preOrder(output); cout << endl; }\r\n    void inOrderOutput() { inOrder(output); cout << endl; }\r\n    void postOrderOutput() { postOrder(output); cout << endl; }\r\n    void levelOrderOutput() { levelOrder(output); cout << endl; }\r\n    void erase()\r\n    {\r\n        postOrder(dispose);\r\n        root = NULL;\r\n        treeSize = 0;\r\n    }\r\n    int height() const { return height(root); }\r\nprotected:\r\n    binaryTreeNode<E>* root;                \/\/ pointer to root\r\n    int treeSize;                           \/\/ number of nodes in tree\r\n    static void (*visit)(binaryTreeNode<E>*);      \/\/ visit function\r\n    static int count;         \/\/ used to count nodes in a subtree\r\n    static void preOrder(binaryTreeNode<E>* t);\r\n    static void inOrder(binaryTreeNode<E>* t);\r\n    static void postOrder(binaryTreeNode<E>* t);\r\n    static void countNodes(binaryTreeNode<E>* t)\r\n    {\r\n        visit = addToCount;\r\n        count = 0;\r\n        preOrder(t);\r\n    }\r\n    static void dispose(binaryTreeNode<E>* t) { delete t; }\r\n    static void output(binaryTreeNode<E>* t)\r\n    {\r\n        cout << t->element << ' ';\r\n    }\r\n    static void addToCount(binaryTreeNode<E>* t)\r\n    {\r\n        count++;\r\n    }\r\n    static int height(binaryTreeNode<E>* t);\r\n};\r\n\/\/ the following should work but gives an internal compiler error\r\n\/\/ template <class E> void (*linkedBinaryTree<E>::visit)(binaryTreeNode<E>*);\r\n\/\/ so the explicit declarations that follow are used for our purpose instead\r\nvoid (*linkedBinaryTree<int>::visit)(binaryTreeNode<int>*);\r\nvoid (*linkedBinaryTree<booster>::visit)(binaryTreeNode<booster>*);\r\nvoid (*linkedBinaryTree<pair<int, int> >::visit)(binaryTreeNode<pair<int, int> >*);\r\nvoid (*linkedBinaryTree<pair<const int, char> >::visit)(binaryTreeNode<pair<const int, char> >*);\r\nvoid (*linkedBinaryTree<pair<const int, int> >::visit)(binaryTreeNode<pair<const int, int> >*);\r\n\r\ntemplate<class E>\r\nE* linkedBinaryTree<E>::rootElement() const\r\n{\/\/ Return NULL if no root. Otherwise, return pointer to root element.\r\n    if (treeSize == 0)\r\n        return NULL;  \/\/ no root\r\n    else\r\n        return &root->element;\r\n}\r\n\r\ntemplate<class E>\r\nvoid linkedBinaryTree<E>::makeTree(const E& element,\r\n    linkedBinaryTree<E>& left, linkedBinaryTree<E>& right)\r\n{\/\/ Combine left, right, and element to make new tree.\r\n \/\/ left, right, and this must be different trees.\r\n   \/\/ create combined tree\r\n    root = new binaryTreeNode<E>(element, left.root, right.root);\r\n    treeSize = left.treeSize + right.treeSize + 1;\r\n\r\n    \/\/ deny access from trees left and right\r\n    left.root = right.root = NULL;\r\n    left.treeSize = right.treeSize = 0;\r\n}\r\n\r\ntemplate<class E>\r\nlinkedBinaryTree<E>& linkedBinaryTree<E>::removeLeftSubtree()\r\n{\/\/ Remove and return the left subtree.\r\n   \/\/ check if empty\r\n    if (treeSize == 0)\r\n        throw emptyTree();\r\n\r\n    \/\/ detach left subtree and save in leftSubtree\r\n    linkedBinaryTree<E> leftSubtree;\r\n    leftSubtree.root = root->leftChild;\r\n    count = 0;\r\n    leftSubtree.treeSize = countNodes(leftSubtree.root);\r\n    root->leftChild = NULL;\r\n    treeSize -= leftSubtree.treeSize;\r\n\r\n    return leftSubTree;\r\n}\r\n\r\ntemplate<class E>\r\nlinkedBinaryTree<E>& linkedBinaryTree<E>::removeRightSubtree()\r\n{\/\/ Remove and return the right subtree.\r\n   \/\/ check if empty\r\n    if (treeSize == 0)\r\n        throw emptyTree();\r\n\r\n    \/\/ detach right subtree and save in rightSubtree\r\n    linkedBinaryTree<E> rightSubtree;\r\n    rightSubtree.root = root->rightChild;\r\n    count = 0;\r\n    rightSubtree.treeSize = countNodes(rightSubtree.root);\r\n    root->rightChild = NULL;\r\n    treeSize -= rightSubtree.treeSize;\r\n\r\n    return rightSubTree;\r\n}\r\n\r\ntemplate<class E>\r\nvoid linkedBinaryTree<E>::preOrder(binaryTreeNode<E>* t)\r\n{\/\/ Preorder traversal.\r\n    if (t != NULL)\r\n    {\r\n        linkedBinaryTree<E>::visit(t);\r\n        preOrder(t->leftChild);\r\n        preOrder(t->rightChild);\r\n    }\r\n}\r\n\r\ntemplate<class E>\r\nvoid linkedBinaryTree<E>::inOrder(binaryTreeNode<E>* t)\r\n{\/\/ Inorder traversal.\r\n    if (t != NULL)\r\n    {\r\n        inOrder(t->leftChild);\r\n        linkedBinaryTree<E>::visit(t);\r\n        inOrder(t->rightChild);\r\n    }\r\n}\r\n\r\ntemplate<class E>\r\nvoid linkedBinaryTree<E>::postOrder(binaryTreeNode<E>* t)\r\n{\/\/ Postorder traversal.\r\n    if (t != NULL)\r\n    {\r\n        postOrder(t->leftChild);\r\n        postOrder(t->rightChild);\r\n        linkedBinaryTree<E>::visit(t);\r\n    }\r\n}\r\n\r\ntemplate <class E>\r\nvoid linkedBinaryTree<E>::levelOrder(void(*theVisit)(binaryTreeNode<E>*))\r\n{\/\/ Level-order traversal.\r\n    arrayQueue<binaryTreeNode<E>*> q;\r\n    binaryTreeNode<E>* t = root;\r\n    while (t != NULL)\r\n    {\r\n        theVisit(t);  \/\/ visit t\r\n\r\n        \/\/ put t's children on queue\r\n        if (t->leftChild != NULL)\r\n            q.push(t->leftChild);\r\n        if (t->rightChild != NULL)\r\n            q.push(t->rightChild);\r\n\r\n        \/\/ get next node to visit\r\n        try { t = q.front(); }\r\n        catch (queueEmpty) { return; }\r\n        q.pop();\r\n    }\r\n}\r\n\r\ntemplate <class E>\r\nint linkedBinaryTree<E>::height(binaryTreeNode<E>* t)\r\n{\/\/ Return height of tree rooted at *t.\r\n    if (t == NULL)\r\n        return 0;                    \/\/ empty tree\r\n    int hl = height(t->leftChild);  \/\/ height of left\r\n    int hr = height(t->rightChild); \/\/ height of right\r\n    if (hl > hr)\r\n        return ++hl;\r\n    else\r\n        return ++hr;\r\n}\r\n\r\n#endif\r\n\r\n<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"
\u4e8c\u53c9\u6811\u7684\u5b9e\u73b0\uff08\u6ca1\u600e\u4e48\u5199\u6ce8\u91ca\uff09<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[5],"tags":[],"class_list":["post-184","post","type-post","status-publish","format-standard","hentry","category-5"],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.gislxz.com\/index.php\/wp-json\/wp\/v2\/posts\/184","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.gislxz.com\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.gislxz.com\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.gislxz.com\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.gislxz.com\/index.php\/wp-json\/wp\/v2\/comments?post=184"}],"version-history":[{"count":2,"href":"https:\/\/www.gislxz.com\/index.php\/wp-json\/wp\/v2\/posts\/184\/revisions"}],"predecessor-version":[{"id":189,"href":"https:\/\/www.gislxz.com\/index.php\/wp-json\/wp\/v2\/posts\/184\/revisions\/189"}],"wp:attachment":[{"href":"https:\/\/www.gislxz.com\/index.php\/wp-json\/wp\/v2\/media?parent=184"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.gislxz.com\/index.php\/wp-json\/wp\/v2\/categories?post=184"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.gislxz.com\/index.php\/wp-json\/wp\/v2\/tags?post=184"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}