{"id":416,"date":"2015-03-25T09:50:42","date_gmt":"2015-03-25T09:50:42","guid":{"rendered":"8fe0093bb30d6f8c31474bd0764e6ac0"},"modified":"2015-03-25T09:50:42","modified_gmt":"2015-03-25T09:50:42","slug":"","status":"publish","type":"post","link":"https:\/\/www.xiaobo.li\/notes\/archives\/416","title":{"rendered":"\u57fa\u4e8e\u4e8c\u53c9\u6811\u7684\u601d\u8def\u5b9e\u73b0\u7684\u201c\u5341\u53c9\u6811\u201d"},"content":{"rendered":"

\u8be5\u6570\u636e\u7ed3\u6784\u7528\u4e8e\u4ee5\u66ff\u4ee3\u4e00\u4e9b\u7b80\u5355\u7684\u672c\u5730\u7f13\u5b58\u7cfb\u7edf\uff0c\u5e76\u63d0\u4f9b\u5feb\u901f\u68c0\u7d22\u7684\u529f\u80fd\u3002<\/p>\n

\n<\/p>\n

\u4e1a\u52a1\u573a\u666f\uff1a<\/p>\n

\u7528\u6237\u5e10\u53f7223\uff0c\u62e5\u6709\u4e0b\u7ea7\u5e10\u53f7223001\u3001223002\u30012230055\u300122312345...<\/p>\n

\u7528\u6237\u5e10\u53f7224\uff0c\u62e5\u6709\u4e0b\u7ea7\u5e10\u53f7224002\u30012248888...<\/p>\n

\u7528\u6237...<\/p>\n

\n<\/p>\n

223\u548c224\uff0c\u6211\u4eec\u6682\u4e14\u53eb\u4ed6\u4e3a\u5927\u5e10\u53f7\uff0c\u540e\u9762\u7684\u90fd\u53eb\u5c0f\u5e10\u53f7\u3002\n<\/p>\n

\n<\/p>\n

\u5f53\u8fd9\u4e9b\u5c0f\u5e10\u53f7\u53d1\u6d88\u606f\u7ed9\u7cfb\u7edf\u65f6\uff0c\u9700\u8981\u8bc6\u522b\u51fa\u5bf9\u5e94\u7684\u5927\u5e10\u53f7\uff0c\u4e14\u5c0f\u5e10\u53f7\u7684\u957f\u5ea6\u4e0d\u7b49\uff0c\u4e0d\u53ef\u4ee5\u68c0\u7d22\u5e93\u8868\u3002<\/p>\n

\u5047\u8bbe\u5927\u5e10\u53f7\u5df2\u7ecf\u9a7b\u7559\u5728\u5185\u5b58\u3002<\/p>\n

 <\/p>\n

java:<\/p>\n

\/**\r\n * \u57fa\u4e8e\u4e8c\u53c9\u6811\u7684\u601d\u8def\u5b9e\u73b0\u7684\u201c\u5341\u53c9\u6811\u201d\uff0c\u7528\u4e8e\u5b58\u50a8\u4e00\u4e9b\u4e34\u65f6\u6027\u7684\u6570\u636e\uff0c\u5e76\u63d0\u4f9b\u4e00\u4e9b\u67e5\u8be2\u63a5\u53e3\r\n * @project xframework\r\n * @date 2013-1-11\r\n * @version 1.0\r\n * @author Jason5186@qq.com\r\n * \r\n * @review_history\r\n * [2013-1-11] create by Jason\r\n *\/\r\npublic class BinaryTree {\r\n\t\r\n\t\/\/ \u6811\u7684\u6839\u7ed3\u70b9\r\n\tprivate TreeNode root = null;\r\n\t\r\n\t\/**\r\n\t * \r\n\t *\/\r\n\tpublic BinaryTree() {\r\n\t\t\/\/ TODO Auto-generated constructor stub\r\n\t\troot = new TreeNode(0);\r\n\t}\r\n\t\r\n\tprivate class TreeNode {\r\n\t\t\r\n\t\tprivate int key; \r\n\t\tprivate Object value;\r\n\t\tprivate TreeNode[] nodes = new TreeNode[10];\r\n\t\t\r\n\t\t\r\n\t\tpublic TreeNode(int key) {\r\n\t\t\t\/\/ TODO Auto-generated constructor stub\r\n\t\t\tthis(key, null);\r\n\t\t}\r\n\t\t\r\n\t\tpublic TreeNode(int key, Object value) {\r\n\t\t\tthis.key = key;\r\n\t\t\tthis.value = value;\r\n\t\t}\t\r\n\t\t\r\n\t\t\r\n\t\tpublic TreeNode setChildTreeNode(int key, Object value){\r\n\t\t\t\r\n\t\t\tsynchronized(this){\r\n\t\t\t\tTreeNode treeNode = nodes[key];\r\n\t\t\t\tif (treeNode == null) {\r\n\t\t\t\t\tnodes[key] = new TreeNode(key);\r\n\t\t\t\t}\r\n\t\t\t\tgetChildTreeNode(key).setValue(value);\r\n\t\t\t}\r\n\t\t\t\r\n\t\t\treturn getChildTreeNode(key);\r\n\t\t\t\r\n\t\t}\r\n\t\t\r\n\t\tpublic TreeNode setChildTreeNode(int key){\r\n\t\t\tsynchronized(this){\r\n\t\t\t\tTreeNode treeNode = nodes[key];\r\n\t\t\t\tif (treeNode == null) {\r\n\t\t\t\t\tnodes[key] = new TreeNode(key);\r\n\t\t\t\t}\r\n\t\t\t}\r\n\t\t\t\r\n\t\t\treturn getChildTreeNode(key);\r\n\t\t}\r\n\t\t\r\n\t\tpublic TreeNode getChildTreeNode(int key){\r\n\t\t\treturn nodes[key];\r\n\t\t}\r\n\t\t\r\n\t\tpublic int getKey() {\r\n\t\t\treturn key;\r\n\t\t}\r\n\t\t\r\n\t\tpublic Object getValue(){\r\n\t\t\treturn value;\r\n\t\t}\r\n\t\t\r\n\t\tpublic void removeValue(){\r\n\t\t\tthis.value = null;\r\n\t\t}\r\n\t\t\r\n\t\tpublic void setValue(Object value){\r\n\t\t\tthis.value = value;\r\n\t\t}\r\n\t\t\r\n\t\tpublic String toString()\r\n\t\t{\r\n\t\t\t\r\n\t\t\treturn \"(\" + key + \" , \" + value + \" )\";\r\n\t\t}\r\n\t\t\r\n\t}\r\n\t\r\n\t\/**\r\n\t * \u7a7a\u8fd4\u56de true \uff0c\u5426\u5219\u8fd4\u56de false . \r\n\t *\/\r\n\tpublic boolean isEmpty()\r\n\t{\r\n\t\tif (root == null) {\r\n\t\t\treturn true;\r\n\t\t} else {\r\n\t\t\treturn false;\r\n\t\t}\t\t\t\r\n\t}\r\n\t\r\n\t\r\n\tpublic void TreeEmpty() throws Exception \r\n\t{\r\n\t\tif (isEmpty()) {\r\n\t\t\tthrow new Exception(\"\u6811\u4e3a\u7a7a\");\r\n\t\t}\r\n\t}\r\n\t\r\n\t\r\n\t\r\n\t\/**\r\n\t * \u67e5\u627e\u6307\u5b9as_key\u5bf9\u5e94\u7684\u8282\u70b9\r\n\t * @param s_key\r\n\t * @return TreeNode\r\n\t * @throws Exception\r\n\t *\/\r\n\tpublic TreeNode search(String s_key) throws Exception \r\n\t{\r\n\t\t\r\n\t\tif (getRoot() == null) {\r\n\t\t\tthrow new Exception(\"root node is null\");\r\n\t\t}\r\n\t\t\r\n\t\tTreeNode treeNode = getRoot();\r\n\t\t\r\n\t\tchar[] key_array = s_key.toCharArray();\r\n\t\t\r\n\t\t\/\/ \u6839\u636e\u7ed9\u5b9a\u7684s_key\uff0c\u904d\u5386tree node\u7684\u7edd\u5bf9\u8def\u5f84\uff0c\u4e14\u4ee5\u6700\u77ed\u5339\u914d\u7684\u89c4\u5219\u68c0\u7d22\uff1b\r\n\t\t\/\/ \u547d\u4e2d\u540e\u8fd4\u56de\u5bf9\u5e94\u7684tree node\uff0c\u5426\u5219\u8fd4\u56deNull\u3002\r\n\t\tfor (char skey : key_array) {\r\n\t\t\t\r\n\t\t\tint key = skey & 0xf;\r\n\t\t\t\r\n\t\t\tTreeNode t_treeNode = treeNode.getChildTreeNode(key);\r\n\t\t\tif (t_treeNode == null) {\r\n\t\t\t\t\r\n\t\t\t\t\/\/ \u8be5\u8282\u70b9\u5c1a\u672a\u521b\u5efa\uff1a\r\n\t\t\t\treturn null;\r\n\t\t\t}else if (t_treeNode.getValue() != null) {\r\n\t\t\t\t\r\n\t\t\t\t\/\/ \u547d\u4e2d\uff1a\r\n\t\t\t\treturn t_treeNode;\r\n\t\t\t}else{\r\n\t\t\t\t\r\n\t\t\t\t\/\/ \u5426\u5219\uff0c\u5c06\u904d\u5386\u4e0b\u4e00\u4e2a\u8282\u70b9\uff1a\r\n\t\t\t\ttreeNode = t_treeNode;\r\n\t\t\t}\r\n\t\t\t\r\n\t\t}\r\n\t\t\r\n\t\t\/\/ \u5faa\u73af\u4f53\u4e4b\u5916\uff0c\u5c06\u89c6\u4e3a\u672a\u547d\u4e2d\uff1a\r\n\t\treturn null;\r\n\t\t\r\n\t}\r\n\t\r\n\t\r\n\t\/**\r\n\t * \u5c06\u6307\u5b9a\u7684s_key\u653e\u5165\u8282\u70b9\uff0c\u5e76\u8bbe\u7f6e\u5bf9\u5e94\u7684value\r\n\t * @param s_key\r\n\t * @param value\r\n\t * @throws Exception \r\n\t *\/\r\n\tpublic void insert(String s_key, Object value) throws Exception{\r\n\t\tTreeNode treeNode = getRoot();\r\n\t\t\r\n\t\tchar[] key_array = s_key.toCharArray();\r\n\t\tint s_key_length = key_array.length;\r\n\t\tint s_key_count = 1;\r\n\t\t\/*\r\n\t\t * \u6839\u636e\u7ed9\u5b9a\u7684key_array\u7684\u957f\u5ea6\uff0c\u67e5\u627e\u8282\u70b9\u3001\u5e03\u7f6e\u8282\u70b9\u5e76\u5f97\u5230\u6700\u540e\u4e00\u4e2a\u8282\u70b9\u7684tree node\uff0c\u7136\u540e\u8d4b\u503cvalue\u3002\r\n\t\t *\/\r\n\t\tfor (char skey : key_array) {\r\n\t\t\t\r\n\t\t\tint key = skey & 0xf;\r\n\t\t\t\r\n\t\t\t\/\/ \u53d6\u67d0\u8282\u70b9\u4e0b\uff0cN\u4e2a\u5b50\u8282\u70b9\u4e2d\u7684\u4e00\u4e2a\u5206\u652f\uff1a\r\n\t\t\tTreeNode t_treeNode = treeNode.getChildTreeNode(key);\r\n\t\t\t\r\n\t\t\tif (t_treeNode == null) {\r\n\t\t\t\t\r\n\t\t\t\t\/\/ \u521b\u5efa\u4e00\u4e2a\u65b0\u7684\u5b50\u8282\u70b9\uff1a\r\n\t\t\t\tt_treeNode = treeNode.setChildTreeNode(key);\r\n\t\t\t}else{\r\n\t\t\t\t\r\n\t\t\t\tif (t_treeNode.getValue() != null && s_key_count != s_key_length) {\r\n\t\t\t\t\t\r\n\t\t\t\t\ttreeNode = null;\r\n\t\t\t\t\tbreak;\r\n\t\t\t\t}\r\n\t\t\t\t\r\n\t\t\t}\r\n\t\t\t\r\n\t\t\t\/\/ \u8be5\u8282\u70b9\u5df2\u7ecf\u5b58\u5728\uff0c\u8282\u70b9\u4ea4\u6362\uff1a\r\n\t\t\ttreeNode = t_treeNode;\r\n\t\t\t\r\n\t\t\ts_key_count++;\r\n\t\t}\r\n\t\t\r\n\t\tif (treeNode != null) {\r\n\t\t\t\r\n\t\t\t\/\/ \u4e3a\u6700\u540e\u4e00\u4e2a\u8282\u70b9\u8d4b\u503c\uff1a\r\n\t\t\ttreeNode.setValue(value);\r\n\t\t}\r\n\t\t\r\n\t\t\r\n\t}\r\n\t\r\n\t\r\n\t\/**\r\n\t * \u5220\u9664\u6307\u5b9akey\u7684\u8282\u70b9\r\n\t * @param s_key\r\n\t * @throws Exception\r\n\t *\/\r\n\tpublic void delete(String s_key) throws Exception\r\n\t{\r\n\t\tTreeNode node = search(s_key);\r\n\t\tif (node == null) {\r\n\t\t\tthrow new Exception(\"Tree node not found, Tree node key is:[\"+s_key+\"]\");\r\n\t\t}\r\n\t\t\r\n\t\tnode.removeValue();\r\n\t\tnode = null;\r\n\t\t\r\n\t}\r\n\t\r\n\t\r\n\t\r\n\t\r\n\tpublic TreeNode getRoot() {\r\n\t\treturn root;\r\n\t}\r\n\t\r\n\t\r\n}<\/pre>\n
Test:<\/p>\n
public static void main(String[] args) \r\n    {\r\n    \ttry {\r\n\t    \tBinaryTree bt = new BinaryTree();\r\n\r\n\t    \tString key = \"223\";\r\n\t    \tString msg = \"hello jason\";\r\n\t    \tbt.insert(key, msg);\r\n\t    \t\r\n\t    \tTreeNode node = bt.search(key);\r\n\t    \tif (node != null) {\r\n\t    \t\tSystem.out.println(node.getValue());\r\n\t    \t}\r\n\t    \t\r\n\t    \tnode = bt.search(\"223001\");\r\n\t    \tif (node != null) {\r\n\t    \t\tSystem.out.println(node.getValue());\r\n\t    \t}\r\n\t    \t\r\n\t    \t\r\n\t    \tSystem.out.println(\"Done!\");\r\n\t    \t\r\n    \t} catch (Exception e) {\r\n    \t\tSystem.out.println(e.getMessage());\r\n    \t\te.printStackTrace();\r\n    \t}\r\n    }<\/pre>\n
 <\/p>\n
 <\/p>\n
 <\/p>\n
.<\/p>\n","protected":false},"excerpt":{"rendered":"
\u8be5\u6570\u636e\u7ed3\u6784\u7528\u4e8e\u4ee5\u66ff\u4ee3\u4e00\u4e9b\u7b80\u5355\u7684\u672c\u5730\u7f13\u5b58\u7cfb\u7edf\uff0c\u5e76\u63d0\u4f9b\u5feb\u901f\u68c0\u7d22\u7684\u529f\u80fd\u3002<\/p>\n
<\/p>\n
\u4e1a\u52a1\u573a\u666f\uff1a<\/p>\n
\u7528\u6237\u5e10\u53f7223\uff0c\u62e5\u6709\u4e0b\u7ea7\u5e10\u53f7223001\u3001223002\u30012230055\u300122312345...<\/p>\n
\u7528\u6237\u5e10\u53f7224\uff0c\u62e5\u6709\u4e0b\u7ea7\u5e10\u53f7224002\u30012248888...<\/p>\n
\u7528\u6237...<\/p>\n
<\/p>\n
223\u548c224\uff0c\u6211\u4eec\u6682\u4e14\u53eb\u4ed6\u4e3a\u5927\u5e10\u53f7\uff0c\u540e\u9762\u7684\u90fd\u53eb\u5c0f\u5e10\u53f7\u3002<\/p>\n
<\/p>\n
\u5f53\u8fd9\u4e9b\u5c0f\u5e10\u53f7\u53d1\u6d88\u606f\u7ed9\u7cfb\u7edf\u65f6\uff0c\u9700\u8981\u8bc6\u522b\u51fa\u5bf9\u5e94\u7684\u5927\u5e10\u53f7\uff0c\u4e14\u5c0f\u5e10\u53f7\u7684\u957f\u5ea6\u4e0d\u7b49\uff0c\u4e0d\u53ef\u4ee5\u68c0\u7d22\u5e93\u8868\u3002<\/p>\n
\u5047\u8bbe\u5927\u5e10\u53f7\u5df2\u7ecf\u9a7b\u7559\u5728\u5185\u5b58\u3002<\/p>\n
 <\/p>\n
java:<\/p>\n
\/**\r\n * \u57fa\u4e8e\u4e8c\u53c9\u6811\u7684\u601d\u8def\u5b9e\u73b0\u7684\u201c\u5341\u53c9\u6811\u201d\uff0c\u7528\u4e8e\u5b58\u50a8\u4e00\u4e9b\u4e34\u65f6\u6027\u7684\u6570\u636e\uff0c\u5e76\u63d0\u4f9b\u4e00\u4e9b\u67e5\u8be2\u63a5\u53e3\r\n * @project xframework\r\n * @date 2...<\/pre>\n
 \u7ee7\u7eed\u9605\u8bfb →<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[283],"tags":[],"class_list":["post-416","post","type-post","status-publish","format-standard","hentry","category-technologys"],"_links":{"self":[{"href":"https:\/\/www.xiaobo.li\/notes\/wp-json\/wp\/v2\/posts\/416","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.xiaobo.li\/notes\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.xiaobo.li\/notes\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.xiaobo.li\/notes\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.xiaobo.li\/notes\/wp-json\/wp\/v2\/comments?post=416"}],"version-history":[{"count":0,"href":"https:\/\/www.xiaobo.li\/notes\/wp-json\/wp\/v2\/posts\/416\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.xiaobo.li\/notes\/wp-json\/wp\/v2\/media?parent=416"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.xiaobo.li\/notes\/wp-json\/wp\/v2\/categories?post=416"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.xiaobo.li\/notes\/wp-json\/wp\/v2\/tags?post=416"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}