{"id":782,"date":"2013-10-14T18:51:40","date_gmt":"2013-10-14T10:51:40","guid":{"rendered":"http:\/\/guoh.ai\/lifelog\/?p=782"},"modified":"2013-10-15T14:47:07","modified_gmt":"2013-10-15T06:47:07","slug":"binary-tree","status":"publish","type":"post","link":"https:\/\/guoh.ai\/lifelog\/2013\/10\/binary-tree\/","title":{"rendered":"\u4e8c\u53c9\u6811"},"content":{"rendered":"

\u7092\u73b0\u996d\u7684\u5e16\u5b50\uff0c\u5185\u5bb9\u5747\u6765\u81ea\u4e8e\u7f51\u7edc\u6216\u8005\u4e66\u7c4d\u6574\u7406\u3002<\/p>\n

I)\u6811
\n\u5b83\u662f\u7531N(N>=1)\u4e2a\u6709\u9650\u7ed3\u70b9\u7ec4\u6210\u4e00\u4e2a\u5177\u6709\u5c42\u6b21\u5173\u7cfb\u7684\u96c6\u5408\uff0c\u5b83\u5177\u6709\u4ee5\u4e0b\u7684\u7279\u70b9\uff1a
\na)\u6bcf\u4e2a\u7ed3\u70b9\u6709\u96f6\u4e2a\u6216\u591a\u4e2a\u5b50\u7ed3\u70b9\uff0c\u6ca1\u6709\u5b50\u8282\u70b9\u7684\u8282\u70b9\u79f0\u4e3a\u53f6\u8282\u70b9(\u901a\u5e38\u79f0\u4e3a\u53f6\u5b50)
\nb)\u6ca1\u6709\u7236\u7ed3\u70b9\u7684\u7ed3\u70b9\u79f0\u4e3a\u6839\u7ed3\u70b9(\u901a\u5e38\u79f0\u4e3a\u6839)
\nc)\u6bcf\u4e00\u4e2a\u975e\u6839\u7ed3\u70b9\u6709\u4e14\u53ea\u6709\u4e00\u4e2a\u7236\u7ed3\u70b9(\u6ca1\u6709\u591a\u4e2a\u5f15\u7528\u6307\u5411\u540c\u4e00\u4e2a\u8282\u70b9)
\nd)\u9664\u4e86\u6839\u7ed3\u70b9\u5916\uff0c\u6bcf\u4e2a\u5b50\u7ed3\u70b9\u53ef\u4ee5\u5206\u4e3aM\u4e2a\u4e0d\u76f8\u4ea4\u7684\u5b50\u6811<\/p>\n

\r\n|\r\nr        55\r\no       \/  \\\r\no      \/    \\\r\nt     88     3\r\n.           \/|\\\r\n.          \/ | \\\r\n.         67 7 23\r\nl        \/ \\     \\\r\ne       \/   \\     \\\r\na      53    5     9\r\nf\r\n|\r\n\r\n        Figure. A\r\n<\/pre>\n
\u5982\u4e0a\u56fe(Figure. A)\uff0c\u5b83\u50cf\u4e00\u68f5\u81ea\u7136\u754c\u4e2d\u5012\u751f\u957f\u7684\u6811\uff0c\u6bcf\u4e2a\u679d\u4e2b\u5904\u5c31\u662f\u4e00\u4e2a\u8282\u70b9\uff0c\u65b9\u5411\u662f\u7531\u6839\u5230\u53f6\u5b50\uff0c\u5b83\u5b9e\u9645\u4e0a\u662f\u4e00\u4e2a\u6709\u5411\u56fe\u3002<\/p>\n
\u8fd9\u91cc\u6211\u4eec\u4ecb\u7ecd\u4e0b\u8282\u70b9\uff0c\u8282\u70b9\u662f\u5305\u542b\u4e00\u4e2a\u6570\u636e\u9879\u548c\u4e00\u4e2a(\u591a\u4e2a)\u6307\u5411\u5176\u4ed6\u8282\u70b9\u7684\u5f15\u7528\u9879\u7684\u6570\u636e\u7ed3\u6784\/\u8bb0\u5f55\uff0c\u901a\u5e38\u6211\u4eec\u7528\u7c7b\u4f3c\u5982\u4e0b\u4ee3\u7801\u6765\u8868\u793a\u4e00\u4e2a\u8282\u70b9\uff1a
\n1)<\/p>\n
\r\nrecord SinglyLinkedNode {\r\n    next, \/\/ A reference to the next node\r\n    data \/\/ Data or reference to data\r\n}\r\n<\/pre>\n
2)<\/p>\n
\r\nrecord DoublyLinkedNode {\r\n    previous, \/\/ A reference to the previous node\r\n    next, \/\/ A reference to the next node\r\n    data \/\/ Data or reference to data\r\n}\r\n<\/pre>\n
3)<\/p>\n
\r\nrecord BinaryNode {\r\n    parent, \/\/ A reference to the parent node                                \r\n    left_child, \/\/ A reference to the left child node\r\n    right_child, \/\/ A reference to the right child node\r\n    data \/\/ Data or reference to data\r\n}\r\n<\/pre>\n
\u7ed3\u5408\u4e0a\u56fe(Figure. A)\u6211\u4eec\u5c31\u5f88\u597d\u7406\u89e3\u4e86\u3002<\/p>\n
\u4e00\u4e9b\u6709\u5173\u6811\u7684\u57fa\u672c\u6982\u5ff5\uff1a
\n\u8282\u70b9\u7684\u5ea6(node’s degree): \u5b50\u8282\u70b9\u7684\u4e2a\u6570\u53eb\u505a\u8282\u70b9\u7684\u5ea6
\n\u6811\u7684\u5ea6: \u4e00\u68f5\u6811\u4e2d\uff0c\u6700\u5927\u7684\u8282\u70b9\u7684\u5ea6\u79f0\u4e3a\u6811\u7684\u5ea6
\n\u8282\u70b9\u5c42\u6b21(level): \u6839\u4e3a\u7b2c\u4e00\u5c42\uff0c\u6839\u7684\u5b50\u8282\u70b9\u4e3a\u7b2c\u4e8c\u5c42\uff0c\u4ee5\u6b64\u7c7b\u63a8
\n\u6570\u7684\u9ad8\u5ea6\u6216\u6df1\u5ea6(depth): \u6811\u4e2d\u6700\u5927\u7684\u8282\u70b9\u5c42\u6b21
\n\u5144\u5f1f\u8282\u70b9(siblings): \u5177\u6709\u76f8\u540c\u7236\u8282\u70b9\u7684\u8282\u70b9
\n\u68ee\u6797: M(M>=0)\u68f5\u4e92\u4e0d\u76f8\u4ea4\u7684\u6811\u7684\u96c6\u5408(\u5220\u53bb\u4e00\u68f5\u6811\u7684\u6839\uff0c\u5c31\u5f97\u5230\u4e00\u4e2a\u68ee\u6797\uff1b\u52a0\u4e0a\u4e00\u4e2a\u7ed3\u70b9\u4f5c\u6811\u6839\uff0c\u68ee\u6797\u5c31\u53d8\u4e3a\u4e00\u68f5\u6811)
\n\u6709\u5e8f\u6811(ordered tree)\/\u65e0\u5e8f\u6811(unodered tree): \u82e5\u5c06\u6811\u4e2d\u6bcf\u4e2a\u7ed3\u70b9\u7684\u5404\u5b50\u6811\u770b\u6210\u662f\u4ece\u5de6\u5230\u53f3\u6709\u6b21\u5e8f\u7684(\u5373\u4e0d\u80fd\u4e92\u6362)\uff0c\u5219\u79f0\u8be5\u6811\u4e3a\u6709\u5e8f\u6811(ordered tree)\uff1b\u5426\u5219\u79f0\u4e3a\u65e0\u5e8f\u6811(unodered tree)
\n\u8fd8\u6709\u8bf8\u5982\u5b50\u5b59\/\u7956\u5148\/\u5802\u5144\u5f1f\u8282\u70b9\u8fd9\u4e9b\u6982\u5ff5\u5c31\u4e0d\u5217\u4e3e\u4e86<\/p>\n
\u4e0a\u56fe(Figure. A)\u5f53\u4e2d\uff0c\u6811\u7684\u5ea6\u662f3\uff0c67\u8282\u70b9\u7684\u5ea6\u662f2\uff0c\u6570\u7684\u6df1\u5ea6\u662f4\uff0c55\u8282\u70b9\u662f\u6839\u8282\u70b9\u7b49\u7b49\u8fd9\u4e9b\u57fa\u672c\u5c5e\u6027\u6211\u4eec\u5c31\u80fd\u5f88\u5feb\u5f97\u51fa\u3002<\/p>\n
II)\u4e8c\u53c9\u6811
\n\u6bcf\u4e2a\u7ed3\u70b9\u6700\u591a\u6709\u4e24\u4e2a\u5b50\u6811\u7684\u6709\u5e8f\u6811\uff0c\u901a\u5e38\u6709\u5de6\u5b50\u6811(left subtree)\u548c\u53f3\u5b50\u6811(right subtree)\uff0c\u6700\u5927\u7684\u8282\u70b9\u7684\u5ea6\u4e3a2\uff0c\u4e5f\u5c31\u662f\u4e8c\u53c9\u6811\u7684\u5ea6\u4e3a2\u3002<\/p>\n
\u6ee1\u4e8c\u53c9\u6811(full binary tree): \u6709\u65f6\u88ab\u79f0\u4e3aproper binary tree\u6216\u80052-tree\u6216\u8005strictly binary tree\uff0c\u5c31\u662f\u6bcf\u4e2a\u8282\u70b9\u67090\u62162\u4e2a\u5b50\u8282\u70b9\u3002<\/p>\n
\u5b8c\u5168\u4e8c\u53c9\u6811(complete binary tree): \u9664\u4e86\u6700\u540e\u4e00\u5c42\u4e4b\u5916\u7684\u5176\u4ed6\u5c42\u6b21(\u5f53\u7136\u4e5f\u53ef\u80fd\u5305\u542b\u6700\u540e\u4e00\u5c42)\uff0c\u6bcf\u4e2a\u8282\u70b9\u90fd\u5305\u542b2\u4e2a\u5b50\u8282\u70b9\uff0c\u5e76\u4e14\u6240\u6709\u8282\u70b9\u90fd\u5c3d\u53ef\u80fd\u9760\u5de6\u6392\u5217<\/p>\n
\u5e73\u8861\u4e8c\u53c9\u6811: \u5982\u679c\u67d0\u4e8c\u53c9\u6811\u4e2d\u4efb\u610f\u7ed3\u70b9\u7684\u5de6\u53f3\u5b50\u6811\u7684\u6df1\u5ea6\u76f8\u5dee\u4e0d\u8d85\u8fc71\uff0c\u90a3\u4e48\u5b83\u5c31\u662f\u4e00\u68f5\u5e73\u8861\u4e8c\u53c9\u6811<\/p>\n
\u4e8c\u53c9\u6811\u7684\u904d\u5386\uff0c\u524d\u5e8f(pre-order)\uff0c\u4e2d\u5e8f(in-order)\u548c\u540e\u5e8f(post-order)\uff0c\u524d\u5e8f\u662f\u6839\u5de6\u53f3\uff0c\u4e2d\u5e8f\u662f\u5de6\u6839\u53f3\uff0c\u540e\u5e8f\u662f\u5de6\u53f3\u6839\u3002<\/p>\n
\u4e00\u4e9b\u6709\u5173\u4e8c\u53c9\u6811\u7684\u5e38\u7528\u7b97\u6cd5\u53c2\u770bhttp:\/\/blog.csdn.net\/luckyxiaoqiang\/article\/details\/7518888<\/p>\n
\u51e0\u4e2a\u7b80\u5355\u7684\u4f8b\u5b50:
\n