{"id":562,"date":"2007-03-05T11:33:00","date_gmt":"2007-03-05T03:33:00","guid":{"rendered":"http:\/\/note.systw.net\/note\/?p=562"},"modified":"2023-11-04T11:33:43","modified_gmt":"2023-11-04T03:33:43","slug":"tree","status":"publish","type":"post","link":"https:\/\/systw.net\/note\/archives\/562","title":{"rendered":"Tree"},"content":{"rendered":"\n<p>\u6a39\u72c0\u7d50\u69cb<\/p>\n\n\n\n<p>general tree(\u4e00\u822c\u6a39)<br>\u5b9a\u7fa9:\u4e00\u7fa4\u7bc0\u9ede\u6240\u5f62\u6210\u4e4b\u96c6\u5408,\u81f3\u5c11\u4e00\u500b\u7bc0\u9ede(\u6a39\u6839),\u6bcf\u500b\u96c6\u5408\u53c8\u662f\u4e00\u68f5\u6a39<br>\u6709\u5e8f\u6a39:\u5144\u5f1f\u4e4b\u9593\u7684\u6b21\u5e8f\u662f\u56fa\u5b9a\u7684<br>\u7121\u5e8f\u6a39:\u5144\u5f1f\u4e4b\u9593\u7684\u6b21\u4e4b\u53ef\u8b8a\u52d5\u7684<br>degree(\u5206\u652f\u5ea6):\u6307\u7bc0\u9ede\u7684\u5b50\u6578\u500b\u6578<br>leaf(\u6a39\u8449),terminal node(\u672b\u7aef\u7bc0\u9ede):\u6307\u5206\u652f\u5ea6\u70ba0\u7684\u7bc0\u9ede<br>ancestors(\u7956\u5148):\u5f9e\u6a39\u6839\u7bc0\u9ede\u5230\u8a72\u7bc0\u9ede\u7684\u8def\u5f91\u4e2d\u6240\u6709\u7bc0\u9ede<br>\u7bc0\u9ede\u6578=\u5206\u652f\u6578+1,\u56e0\u70ba\u9664\u4e86\u6a39\u6839\u5916,\u5404\u7bc0\u9ede\u90fd\u88ab\u4e00\u500b\u5206\u652f\u6307\u5230<\/p>\n\n\n\n<p><br><strong>binary tree(\u4e8c\u5143\u6a39):<\/strong><br>\u5b9a\u7fa9:\u4e00\u7fa4\u7bc0\u9ede\u6240\u5f62\u6210\u4e4b\u96c6\u5408,\u7bc0\u9ede\u6578\u53ef\u70ba0(\u7a7a\u96c6\u5408),\u5176\u9918\u7bc0\u9ede\u70ba\u6a39\u6839\u7684\u5de6\u5b50\u6a39\u8207\u53f3\u5b50\u6a39\u4e14\u7686\u70ba2\u5143\u6a39<br>\u8a2d\u4e8c\u5143\u6a39\u6df1\u5ea6\u70bak,\u968e\u5c64\u70bai,\u5247\u6709\u4e09\u7279\u6027:<br>1:\u7bc0\u9ede\u6578\u6700\u591a\u70ba2^k-1<br>2:\u7b2ci\u5c64\u7684\u7bc0\u9ede\u6578\u6700\u591a\u70ba2^(i-1)<br>3:\u8a2dn0=\u5206\u652f\u5ea6\u70ba0\u7684\u7bc0\u9ede,n2=\u5206\u652f\u5ea6\u70ba2\u7684\u7bc0\u9ede,\u5247n0=n2+1,\u4e5f\u5c31\u662f\u6a39\u8449\u6578=\u5206\u652f\u5ea6\u70ba2\u7684\u7bc0\u9ede\u7684\u7e3d\u6578+1<br>\u8b49\u660e:\u8a2d\u7bc0\u9ede\u500b\u6578:n2+n1+n0,\u5206\u652f\u500b\u6578:2*n2+1*n1+0*n0=2*n2+n1<br>\u56e0\u7bc0\u9ede\u6578=\u5206\u652f\u6578+1,\u6240\u4ee5n2+n1+n0=(2*n2+n1)+1,\u79fb\u9805\u5f97\u5230n0=n2+1<\/p>\n\n\n\n<p>\u4e8c\u5143\u6a39\u7684\u7a2e\u985e:<br>full binary tree(\u5168\u6eff\u4e8c\u5143\u6a39):\u7bc0\u9ede\u500b\u6578\u6700\u591a\u7684\u4e8c\u5143\u6a39,\u7bc0\u9ede\u6578\u70ba2^k-1<br>complete binary tree(\u5b8c\u6574\u4e8c\u5143\u6a39):\u7bc0\u9ede\u6700\u5c11\u70ba2^(k-1),\u6700\u591a\u70ba2^k-1<br>strictly binary tree<br>skewed binary tree(\u50be\u659c\u6a39):\u7bc0\u9ede\u500b\u6578\u6700\u5c11\u7684\u4e8c\u5143\u6a39,\u7bc0\u9ede\u6578\u70bak<\/p>\n\n\n\n<p>\u6a39\u6797\u8b8a\u4e8c\u5143\u6a39<br>1,\u5404\u6a39\u7684\u6a39\u6839\u7686\u70ba\u5144\u5f1f<br>2,\u662f\u5144\u5f1f\u4e00\u5f8b\u653e\u5728\u53f3\u5b50\u6a39,\u662f\u5152\u5b50\u4e00\u5f8b\u653e\u5728\u5de6\u5b50\u6a39<\/p>\n\n\n\n<p>&#8230;&#8230;&#8230;&#8230;&#8230;&#8230;&#8230;&#8230;&#8230;&#8230;&#8230;&#8230;&#8230;&#8230;&#8230;&#8230;&#8230;&#8230;&#8230;&#8230;&#8230;&#8230;&#8230;&#8230;..<\/p>\n\n\n\n<p>\u82e5\u7528\u9663\u5217\u8868\u793a\u4e8c\u5143\u6a39<br>\u8a2di\u70ba\u7236\u7bc0\u9ede,\u5247\u5de6\u5152\u5b50\u7bc0\u9ede\u70ba2i,\u53f3\u5152\u5b50\u7bc0\u9ede\u70ba2i+1<br>\u7f3a\u9ede:\u63d2\u5165\u548c\u522a\u9664\u6642\u9700\u5927\u91cf\u642c\u52d5\u8cc7\u6599,\u82e5\u4e8c\u5143\u6a39\u6709\u8cc7\u6599\u7684\u7bc0\u9ede\u4e0d\u591a\u5247\u6d6a\u8cbb\u7a7a\u9593<\/p>\n\n\n\n<p>\u82e5\u7528\u93c8\u7d50\u8868\u793a\u4e8c\u5143\u6a39<br>typedef struct bin_tree{ \/\/\u4e8c\u5143\u6a39\u7bc0\u9ede\u542b\u6307\u6a19\u7684\u7d50\u69cb:<br>\u3000struct bin_tree *left; \/\/\u5de6\u5b50\u6a39\u7684\u6307\u6a19<br>\u3000int data; \/\u8cc7\u6599\/<br>\u3000struct bin_tree *right; \/\/\u53f3\u5b50\u6a39\u7684\u6307\u6a19<br>}BIN_TREE;<\/p>\n\n\n\n<p>\u8a08\u7b97\u7aef\u672b\u7bc0\u9ede\u6578<br>int count(struct bin_tree *root){ \/\/\u6703\u5c07\u5404\u7bc0\u9ede\u8d70\u8a2a\u4e00\u6b21,\u6240\u4ee5\u662fbig O(n)<br>\u3000 if(root==null)return(0);<br>\u3000else if(root-&gt;left==null&amp;&amp;root-&gt;right==null)return(1)<br>\u3000else return(count(root-&gt;left)+count(root-&gt;right));<br>}<br>\u5c0d\u8abf\u5de6\u5b50\u6a39\u548c\u53f3\u5b50\u6a39<br>void swap(treenode root){<br>\u3000treenode *temp;<br>\u3000if(root==null){return(null);}<br>\u3000else{<br>\u3000\u3000temp=root-&gt;right;<br>\u3000\u3000root-&gt;right=swap(root-&gt;left);<br>\u3000\u3000root-&gt;left=swap(temp);<br>\u3000}<br>}<\/p>\n\n\n\n<p>&#8230;&#8230;&#8230;&#8230;&#8230;&#8230;&#8230;&#8230;&#8230;&#8230;.<\/p>\n\n\n\n<p>traversal<br>\u4e3b\u8981\u6709\u4e09\u7a2e<br>preorder(DLR)\u524d\u5e8f\u8d70\u8a2a<br>void preorder(treenode root){<br>\u3000if(root!=null){<br>\u3000\u3000printf(&#8220;%d&#8221;,root-&gt;data); \/\/\u5217data,<br>\u3000\u3000preorder(root-&gt;left); \/\/\u5728\u5f80\u5de6\u5b50\u6a39<br>\u3000\u3000preorder(root-&gt;right); \/\/\u5728\u5f80\u53f3\u5b50\u6a39<br>\u3000}<br>}<br>inorder(LDR)\u4e2d\u5e8f\u8d70\u8a2a<br>void inorder(treenode root){<br>\u3000if(root!=null){<br>\u3000\u3000preorder(root-&gt;left); \/\/\u5728\u5f80\u5de6\u5b50\u6a39<br>\u3000\u3000printf(&#8220;%d&#8221;,root-&gt;data); \/\/\u5217data,<br>\u3000\u3000preorder(root-&gt;right); \/\/\u5728\u5f80\u53f3\u5b50\u6a39<br>\u3000}<br>}<br>postorder(LRD)\u5f8c\u5e8f\u8d70\u8a2a<br>void postorder(treenode root){<br>\u3000if(root!=null){<br>\u3000\u3000preorder(root-&gt;left); \/\/\u5728\u5f80\u5de6\u5b50\u6a39<br>\u3000\u3000preorder(root-&gt;right); \/\/\u5728\u5f80\u53f3\u5b50\u6a39<br>\u3000\u3000printf(&#8220;%d&#8221;,root-&gt;data); \/\/\u5217data,<br>\u3000}<br>}<br>\u547c\u53eb\u6b21\u6578\u7686\u70ba2n+1\u6b21,\u6642\u9593\u8907\u96dc\u5ea6\u70baO(n)<\/p>\n\n\n\n<p>\u524d\u5e8f\u8d70\u8a2a\u7684\u6a39\u6839\u4e00\u5b9a\u5148\u5370\u51fa,\u5f8c\u5e8f\u8d70\u8a2a\u7684\u6a39\u6839\u4e00\u5b9a\u6700\u5f8c\u88ab\u5370\u51fa,\u800c\u4e2d\u5e8f\u8d70\u8a2a\u7684\u6a39\u6839\u5247\u5728\u5de6\u5b50\u6a39\u4e4b\u5f8c\u53f3\u5b50\u6a39\u4e4b\u524d<br>\u56e0\u6b64\u53ea\u8981\u85c9\u7531\u524d\u5e8f\u8d70\u8a2a+\u4e2d\u5e8f\u8d70\u8a2a\u6216\u5f8c\u5e8f\u8d70\u8a2a+\u4e2d\u5e8f\u8d70\u8a2a,\u5c31\u53ef\u5c07\u5370\u51fa\u7684\u8cc7\u6599\u4f9d\u9806\u5e8f\u91cd\u7d44\u56de\u4e8c\u5143\u6a39<br>\u4f46\u5f8c\u5e8f\u8d70\u8a2a+\u524d\u5e8f\u8d70\u8a2a\u5247\u4e0d\u4e00\u5b9a\u53ef\u4ee5\u7d44\u56de\u4e8c\u5143\u6a39<br>ex:\u7d66\u524d\u5e8fabc\u53ca\u5f8c\u5e8fcba\uff0c\u5247\u53ef\u7522\u751f\u53f3\u50be\u659c\u4e8c\u5143\u6a39\u548c\u5de6\u50be\u659c\u4e8c\u5143\u6a39<\/p>\n\n\n\n<p>&#8230;&#8230;&#8230;&#8230;&#8230;&#8230;&#8230;&#8230;&#8230;&#8230;&#8230;&#8230;&#8230;&#8230;&#8230;&#8230;&#8230;&#8230;&#8230;&#8230;&#8230;&#8230;&#8230;&#8230;&#8230;&#8230;&#8230;&#8230;&#8230;&#8230;&#8230;&#8230;&#8230;&#8230;&#8230;.<\/p>\n\n\n\n<p><strong>threaded binary trees(\u5f15\u7dda\u4e8c\u5143\u6a39)<\/strong><br>\u8aaa\u660e:<br>\u4e00\u7a2e\u7279\u6b8a\u7684\u4e8c\u5143\u6a39,\u5229\u7528\u539f\u4e8c\u5143\u6a39\u4e2d\u7684\u7a7a\u6307\u6a19,\u6539\u8b8a\u6210\u5f15\u7dda,\u4ee5\u65b9\u4fbf\u9032\u884c\u8ffd\u8e64<br>\u82e5\u5de6\u6b04\u70ba\u7a7a\u5247\u8b8a\u5f15\u7dda,\u4e26\u6307\u5411\u4e0a\u4e00\u500b\u88ab\u5370\u51fa\u7684\u7bc0\u9ede,\u82e5\u53f3\u6b04\u70ba\u7a7a\u8b8a\u70ba\u5f15\u7dda,\u5247\u6307\u5411\u4e0b\u4e00\u500b\u88ab\u5370\u51fa\u7684\u7bc0\u9ede<\/p>\n\n\n\n<p>\u7279\u6027:<br>\u4e00\u500b\u5177n\u500b\u7bc0\u9ede\u7684\u5f15\u7dda\u4e8c\u5143\u6a39,\u6703\u67092n\u7684\u93c8\u7d50\u6b04\u4f4d,n-1\u500b\u6b04\u4f4d\u662f\u539f\u5148\u7684\u6307\u6a19,n+1\u500b\u6b04\u4f4d\u662f\u5f15\u7dda<br>\u7a7a\u7684\u5f15\u7dda\u4e8c\u5143\u6a39\u7684\u958b\u982d\u7bc0\u9ede\u53f3\u6b04\u4e0d\u7576\u5f15\u7dda,\u4e26\u6307\u81ea\u5df1,\u4f46\u5de6\u6b04\u5247\u7576\u5f15\u7dda,\u4e26\u6307\u81ea\u5df1<br>\u800c\u975e\u7a7a\u7684\u5f15\u7dda\u4e8c\u5143\u6a39\u7684\u958b\u982d\u7bc0\u9ede\u5de6\u6b04\u4e0d\u7576\u5f15\u7dda,\u4e26\u6307\u6a39\u6839\u7bc0\u9ede<\/p>\n\n\n\n<p>\u5f15\u7dda\u5206\u70ba:<br>in-thread(\u4e2d\u5f15\u7dda),pre-thread(\u524d\u5f15\u7dda),post-thread(\u5f8c\u5f15\u7dda)<\/p>\n\n\n\n<p>\u8cc7\u6599\u7d50\u69cb\u70ba\uff1a<br>typedef struct threaded_tree{<br>\u3000short int lthread;<br>\u3000treenode left;<br>\u3000char data;<br>\u3000treenode right;<br>\u3000short int rthread;<br>}treenode;<\/p>\n\n\n\n<p>\u5e38\u898b\u904b\u4f5c:\u5c07\u8cc7\u6599\u63d2\u5728\u7bc0\u9ede\u5f8c,\u5c07\u8cc7\u6599\u63d2\u5728\u7bc0\u9ede\u524d,\u627e\u4e0b\u4e00\u500b\u7bc0\u9ede<br>\u5c07\u7bc0\u9ede\u63d2\u5728\u67d0\u7bc0\u9ede\u5f8c<br>void insert _right(struct treenode *x,struct treenode *new){<br>\u3000new-&gt;lthread=1; \/\/\u56e0\u70ba\u662f\u5728x\u7684\u4e0b\u4e00\u500b,\u56e0\u70balthread\u4e00\u5b9a\u662f\u5f15\u7dda<br>\u3000new-&gt;left=x; \/\/\u56e0\u70ba\u662f\u5f15\u7dda\u6240\u4ee5\u6307\u5411x<br>\u3000new-&gt;right=x-&gt;right;<br>\u3000new-&gt;rthread=x-&gt;rthread;<br>\u3000x-&gt;right=new;<br>\u3000x-&gt;rthread=0;<br>\u3000\/*\u82e5\u4e0d\u662f\u63d2\u5165left\u5247\u9700\u8981\u505a\u4ee5\u4e0b,\u627e\u5230\u65b0\u7bc0\u9ede\u9069\u5408\u7684\u4f4d\u7f6e*\/<br>\u3000if(new-&gt;rthread==0){<br>\u3000\u3000temp=new-&gt;right;<br>\u3000\u3000while(temp-&gt;lthread==0){temp=temp-&gt;left;}<br>\u3000\u3000temp-&gt;left=new;<br>\u3000}<br>\/*\u7d50\u675f*\/<br>}<br>\u627ex\u7684\u4e0b\u4e00\u500b\u7bc0\u9ede<br>treenode next(struct treenode *x){<br>\u3000treenode *temp;<br>\u3000temp=x-&gt;right;<br>\u3000if(x-&gt;rthread==0){ \/\/\u5982\u679c\u6709\u975e\u7a7a\u53f3\u5b50\u6a39<br>\u3000\u3000while(temp-&gt;lthread==0){temp=temp-&gt;left;} \/\/\u5de6\u6b04\u4f4d\u662f\u5de6\u5b50\u6a39\u5c31\u9032\u5165<br>\u3000}<br>\u3000return(temp);<br>}<\/p>\n\n\n\n<p>&#8230;&#8230;&#8230;&#8230;&#8230;&#8230;&#8230;&#8230;&#8230;&#8230;&#8230;&#8230;&#8230;&#8230;&#8230;&#8230;&#8230;&#8230;&#8230;&#8230;&#8230;&#8230;&#8230;&#8230;&#8230;&#8230;&#8230;.<\/p>\n\n\n\n<p><strong>binary expression trees(\u4e8c\u5143\u904b\u7b97\u6a39)<\/strong><br>\u5177\u6709\u968e\u5c64\u95dc\u4fc2(\u904b\u7b97\u5b50\u4e4b\u9593\u7684\u512a\u5148\u9806\u5e8f)\u53ca\u4e8c\u5143\u95dc\u4fc2(\u904b\u7b97\u5b50\u9700\u5c0d\u61c9\u5169\u500b\u904b\u7b97\u5143)<br>\u7aef\u672b\u7bc0\u9ede\u8868\u793a\u904b\u7b97\u5143,\u5167\u90e8\u7bc0\u9ede\u8868\u793a\u904b\u7b97\u5b50,\u904b\u7b97\u5b50\u8d8a\u512a\u5148\u5247\u6703\u5728\u8d8a\u5e95\u5c64<br>\u904b\u7b97\u5b50\u512a\u5148\u9806\u5e8f\u901a\u5e38\u70ba:\u7b97\u8853\u904b\u7b97\u5b50(\u6b63\u8ca0,*\/,+-) &gt; \u95dc\u4fc2\u904b\u7b97\u5b50 &gt; \u908f\u8f2f\u904b\u7b97\u5b50(~,and)<br>\u9032\u884cpre-order traversal\u53ef\u8868\u793a\u6210prefix expression<br>\u9032\u884cpost-order traversal\u53ef\u8868\u793a\u6210postfix expression<br>\u9032\u884cin-order traversal,\u5728\u53e6\u5916\u52a0\u62ec\u865f\u53ef\u8868\u793a\u6210infix expression<\/p>\n\n\n\n<p>\u5229\u7528\u5f8c\u5e8f\u8d70\u8a2a\u9806\u5e8f\u5c0d\u4e8c\u5143\u904b\u7b97\u6a39\u8a08\u7b97<br>int evaluate(struct treenode *root){<br>\u3000int x,,result;<br>\u3000if(root-&gt;left==null&amp;&amp;root-&gt;right==null){return (root-&gt;data);} \/\/\u5982\u679c\u662f\u904b\u7b97\u5143\u5c31\u56de\u50b3<br>\u3000else{ \/\/\u905e\u8ff4\u95dc\u4fc2\u662f\u5148\u8655\u7406\u5de6\u5b50\u6a39\u5728\u8655\u7406\u53f3\u5b50\u6a39\uff0c\u6700\u5f8c\u9032\u884c\u8a08\u7b97<br>\u3000\u3000x=evaluate(root-&gt;left);<br>\u3000\u3000y=evaluate(root-&gt;right);<br>\u3000\u3000switch(root-&gt;operator){<br>\u3000\u3000\u3000case &#8216;+&#8217;:result=x+y;break;<br>\u3000\u3000\u3000case &#8216;*&#8217;:result=x*y;break;<br>\u3000\u3000\u3000case &#8216;\/&#8217;:result=x\/y;break;<br>\u3000\u3000\u3000case &#8216;-&#8216;:result=x-y;break;<br>\u3000\u3000}<br>\u3000\u3000return(result);<br>\u3000}<br>}<br>\u5229\u7528stack\u8a08\u7b97postfix<br>&#8230;.<\/p>\n\n\n\n<p>&#8230;&#8230;&#8230;&#8230;&#8230;&#8230;&#8230;&#8230;&#8230;&#8230;&#8230;&#8230;&#8230;&#8230;&#8230;&#8230;&#8230;&#8230;&#8230;&#8230;&#8230;&#8230;&#8230;..<\/p>\n\n\n\n<p>\u6a39\u7684\u61c9\u7528<br><strong>\u96c6\u5408\u7684\u6a39<\/strong><br>\u6a39\u7684\u7bc0\u9ede\u7528\u4f86\u8868\u793a\u96c6\u5408\u7684\u6240\u6709\u5143\u7d20,\u53ef\u7528\u4e00\u7dad\u9663\u5217\u8868\u793an\u500b\u5143\u7d20\u7684\u96c6\u5408\u60c5\u6cc1,<br>ex:int parent[1-n];<br>\u800c\u5404\u7bc0\u9ede\u90fd\u6307\u5411\u7236\u89aa\u7bc0\u9ede\uff0c\u53ef\u7528\u4e00\u7dad\u9663\u5217\u5167\u7684value\u6b04\u5132\u5b58\u7236\u7bc0\u9edekey\u503c<br>\u7236\u89aa\u7bc0\u9ede\u7684value\u6b04\u5247\u5132\u5b58\u9019\u96c6\u5408\u7684\u5143\u7d20\u500b\u6578(\u53ef\u8868\u793a\u70ba\u8ca0\u6578\u65b9\u4fbf\u5340\u5225)<br>ex:set 1={1,2,4},\u5247parent[1]=-3,parent[2]=1,parent[4]=1,<br>\u96c6\u5408\u7684\u904b\u4f5c\u6709\uff1a\u806f\u96c6\u904b\u4f5c,\u627e\u5143\u7d20\u6240\u5c6c\u96c6\u5408<\/p>\n\n\n\n<p>\u806f\u96c6\u904b\u4f5c\uff1a\u5c07\u5169\u68f5\u6a39\u5408\u4f75\u70ba\u4e00\u68f5\u6a39\uff0c\u53ef\u5c07\u4e00\u500b\u6a39\u7684\u6a39\u6839\u7bc0\u9ede\u6307\u5411\u53e6\u4e00\u68f5\u6a39<br>\u5982\u679c\u5168\u90e8\u6709n\u500b\u5143\u7d20,\u6700\u5dee\u60c5\u6cc1\u6703\u5f62\u6210\u4e00\u500b\u9ad8\u5ea6\u70ban\u7684\u6a39(\u53ef\u5728\u806f\u9032\u904b\u4f5c\u6642\u4f7f\u7528\u52a0\u6b0a\u6cd5\u5247\u907f\u514d)<br>weighting rule(\u52a0\u6b0a\u6cd5\u5247):\u5c07\u96c6\u5408\u7684\u5143\u7d20\u500b\u6578\u7576\u6210\u52a0\u6b0a\u8003\u91cf,\u5c07\u8f03\u5c11\u7bc0\u9ede\u7684\u6a39\u6307\u5411\u5c07\u591a\u7bc0\u9ede\u7684\u6a39,\u5247\u9ad8\u5ea6\u4e0d\u8b8a\uff0c\u9664\u975e\u7bc0\u9ede\u76f8\u540c\u9ad8\u5ea6\u624d\u6703\u52a01<br>void union(int x,int y){ \/\/big O(1)<br>if(parent[x]<br>parent[y]=x; \/\/y\u96c6\u5408\u6307\u5411x\u96c6\u5408,\u56e0\u70bax\u7684\u5143\u7d20\u591a<br>}else{<br>parent[x]=y; \/\/x\u96c6\u5408\u6307\u5411y\u96c6\u5408,\u56e0\u70bay\u7684\u5143\u7d20\u591a,\u6216\u662f\u7b49\u65bcx<br>}<br>}<br>\u627e\u5143\u7d20\u6240\u5c6c\u96c6\u5408\uff1a\u76f8\u7576\u65bc\u7531\u7bc0\u9ede\u5f80\u4e0a\u627e\u5230\u6a39\u6839\u7bc0\u9ede\uff0c\u8907\u96dc\u5ea6\uff1d\u96c6\u5408\u5c0d\u61c9\u7684\u6a39\u9ad8<br>\u82e5\u5728\u806f\u96c6\u904b\u4f5c\u6642\u7528\u52a0\u6b0a\u6cd5\u5247,\u8907\u96dc\u5ea6\u70babig O(log2(n))<br>find(int z){<br>int father;<br>father=parent[z];<br>while(parent[father]&gt;0){ \/\/\u5982\u679c\u662f\u8ca0\u6578\u5247\u4ee3\u8868\u96c6\u5408\uff0c\u4e0d\u7136\u7e7c\u7e8c\u5f80\u4e0a\u627e<br>father=parent[father];<br>}<br>return(father);<br>}<\/p>\n\n\n\n<p><strong>\u6c7a\u7b56\u6a39<br>\u904a\u6232\u6a39<\/strong><\/p>\n","protected":false},"excerpt":{"rendered":"<p>\u6a39\u72c0\u7d50\u69cb general tree(\u4e00\u822c\u6a39)\u5b9a\u7fa9:\u4e00\u7fa4\u7bc0\u9ede\u6240 &#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"fifu_image_url":"","fifu_image_alt":"","_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2}},"categories":[15],"tags":[],"class_list":["post-562","post","type-post","status-publish","format-standard","hentry","category-algorithm"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/systw.net\/note\/wp-json\/wp\/v2\/posts\/562","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/systw.net\/note\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/systw.net\/note\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/systw.net\/note\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/systw.net\/note\/wp-json\/wp\/v2\/comments?post=562"}],"version-history":[{"count":0,"href":"https:\/\/systw.net\/note\/wp-json\/wp\/v2\/posts\/562\/revisions"}],"wp:attachment":[{"href":"https:\/\/systw.net\/note\/wp-json\/wp\/v2\/media?parent=562"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/systw.net\/note\/wp-json\/wp\/v2\/categories?post=562"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/systw.net\/note\/wp-json\/wp\/v2\/tags?post=562"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}