docs__algorithm__datasources__binarytree.md.js

(window["webpackJsonp"]=window["webpackJsonp"]||[]).push([[3],{djdJ:function(n,e,t){"use strict";t.r(e);var l=t("q1tI"),r=t.n(l),a=t("dEAq"),o=t("H1Ra"),i=r.a.memo((n=>{n.demos;return r.a.createElement(r.a.Fragment,null,r.a.createElement("div",{className:"markdown"},r.a.createElement("h2",{id:"\u6811\u7684\u884d\u751f"},r.a.createElement(a["AnchorLink"],{to:"#\u6811\u7684\u884d\u751f","aria-hidden":"true",tabIndex:-1},r.a.createElement("span",{className:"icon icon-link"})),"\u6811\u7684\u884d\u751f"),r.a.createElement("ul",null,r.a.createElement("li",null,r.a.createElement("p",null,"\u65e0\u5e8f\u6811:\u6811\u4e2d\u4efb\u610f\u8282\u70b9\u7684\u5b50\u7ed3\u70b9\u4e4b\u95f4\u6ca1\u6709\u987a\u5e8f\u5173\u7cfb\uff0c\u8fd9\u79cd\u6811\u79f0\u4e3a\u65e0\u5e8f\u6811,\u4e5f\u79f0\u4e3a\u81ea\u7531\u6811")),r.a.createElement("li",null,r.a.createElement("p",null,"\u6709\u5e8f\u6811:\u6811\u4e2d\u4efb\u610f\u8282\u70b9\u7684\u5b50\u7ed3\u70b9\u4e4b\u95f4\u6709\u987a\u5e8f\u5173\u7cfb")),r.a.createElement("li",null,r.a.createElement("p",null,"\u4e8c\u53c9\u6811:\u6bcf\u4e2a\u8282\u70b9\u6700\u591a\u542b\u6709\u4e24\u4e2a\u5b50\u6811\u7684\u6811\u79f0\u4e3a\u4e8c\u53c9\u6811")),r.a.createElement("li",null,r.a.createElement("p",null,"\u5b8c\u5168\u4e8c\u53c9\u6811:\u9664\u4e86\u6700\u540e\u4e00\u5c42\uff0c\u5176\u5b83\u5404\u5c42\u8282\u70b9\u6570\u90fd\u8fbe\u5230\u6700\u5927")),r.a.createElement("li",null,r.a.createElement("p",null,"\u6ee1\u4e8c\u53c9\u6811:\u6bcf\u4e00\u5c42\u4e0a\u7684\u7ed3\u70b9\u6570\u90fd\u662f\u6700\u5927\u7ed3\u70b9\u6570")),r.a.createElement("li",null,r.a.createElement("p",null,"\u970d\u592b\u66fc\u6811:\u5e26\u6743\u8def\u5f84\u6700\u77ed\u7684\u4e8c\u53c9\u6811\uff0c\u4e5f\u53eb\u6700\u4f18\u4e8c\u53c9\u6811"))),r.a.createElement("h2",{id:"\u4e8c\u53c9\u6811\u6982\u5ff5"},r.a.createElement(a["AnchorLink"],{to:"#\u4e8c\u53c9\u6811\u6982\u5ff5","aria-hidden":"true",tabIndex:-1},r.a.createElement("span",{className:"icon icon-link"})),"\u4e8c\u53c9\u6811\u6982\u5ff5"),r.a.createElement("ul",null,r.a.createElement("li",null,r.a.createElement("p",null,"\u6811\u7531\u4e00\u7ec4\u4ee5\u8fb9\u8fde\u63a5\u7684\u8282\u70b9\u7ec4\u6210")),r.a.createElement("li",null,r.a.createElement("p",null,"\u5728\u4e00\u4e2a\u6811\u6700\u4e0a\u9762\u7684\u8282\u70b9\u79f0\u4e3a\u6839\u8282\u70b9\uff0c\u5982\u679c\u4e00\u4e2a\u8282\u70b9\u4e0b\u9762\u8fde\u63a5\u591a\u4e2a\u8282\u70b9\uff0c\u90a3\u4e48\u8be5\u8282\u70b9\u79f0\u4e3a\u7236\u8282\u70b9\uff0c\u4ed6\u4e0b\u9762\u7684\u8282\u70b9\u88ab\u79f0\u4e3a\u5b50\u8282\u70b9\uff0c\u4e00\u4e2a\u8282\u70b9\u53ef\u4ee5\u6709 0 \u4e2a\u30011 \u4e2a\u6216\u591a\u4e2a\u5b50\u8282\u70b9\uff0c\u6ca1\u6709\u4efb\u4f55\u5b50\u8282\u70b9\u7684\u8282\u70b9\u79f0\u4e3a\u53f6\u5b50\u8282\u70b9")),r.a.createElement("li",null,r.a.createElement("p",null,"\u4e8c\u53c9\u6811\u662f\u4e00\u79cd\u7279\u6b8a\u7684\u6811\uff0c\u5b50\u8282\u70b9\u4e2a\u6570\u4e0d\u8d85\u8fc7\u4e24\u4e2a")),r.a.createElement("li",null,r.a.createElement("p",null,"\u4ece\u4e00\u4e2a\u8282\u70b9\u8d70\u5230\u53e6\u4e00\u4e2a\u8282\u70b9\u7684\u8fd9\u4e00\u7ec4\u8fb9\u4e3a\u8def\u5f84")),r.a.createElement("li",null,r.a.createElement("p",null,"\u4ee5\u67d0\u79cd\u7279\u5b9a\u987a\u5e8f\u8bbf\u95ee\u4e66\u4e2d\u7684\u6240\u6709\u8282\u70b9\u79f0\u4e3a\u6811\u7684\u904d\u5386")),r.a.createElement("li",null,r.a.createElement("p",null,"\u6811\u5206\u4e3a\u51e0\u4e2a\u5c42\u6b21\uff0c\u6839\u8282\u70b9\u662f\u7b2c 0 \u5c42\uff0c\u4ed6\u7684\u5b50\u8282\u70b9\u662f\u7b2c\u4e00\u5c42\uff0c\u4ee5\u6b64\u7c7b\u63a8\uff0c\u6211\u4eec\u5b9a\u4e49\u6811\u7684\u5c42\u6811\u5c31\u662f\u6811\u7684\u6df1\u5ea6")),r.a.createElement("li",null,r.a.createElement("p",null,"\u6bcf\u4e2a\u8282\u70b9\u90fd\u6709\u4e00\u4e2a\u4e0e\u4e4b\u76f8\u5173\u7684\u503c\uff0c\u8be5\u503c\u6709\u65f6\u88ab\u79f0\u4e3a",r.a.createElement("strong",null,"\u952e"))),r.a.createElement("li",null,r.a.createElement("p",null,"\u4e00\u4e2a\u7236\u8282\u70b9\u7684\u4e24\u4e2a\u5b50\u8282\u70b9\u5206\u522b\u79f0\u4e3a\u5de6\u8282\u70b9\u548c\u53f3\u8282\u70b9\uff0c",r.a.createElement("strong",null,"*\u4e8c\u53c9\u67e5\u627e\u6811"),"\u662f\u4e00\u79cd\u7279\u6b8a\u7684\u4e8c\u53c9\u6811\uff0c\u76f8\u5bf9\u8f83\u5c0f\u7684\u503c\u4fdd\u5b58\u5728\u5de6\u8282\u70b9\uff0c\u8f83\u5927\u7684\u503c\u4fdd\u5b58\u5728\u53f3\u8282\u70b9\uff0c\u8fd9\u4e00\u7279\u6027\u4f7f\u5f97\u67e5\u627e\u6548\u7387\u5f88\u9ad8"))),r.a.createElement("h2",{id:"\u4e8c\u53c9\u6811\u7684\u904d\u5386"},r.a.createElement(a["AnchorLink"],{to:"#\u4e8c\u53c9\u6811\u7684\u904d\u5386","aria-hidden":"true",tabIndex:-1},r.a.createElement("span",{className:"icon icon-link"})),"\u4e8c\u53c9\u6811\u7684\u904d\u5386"),r.a.createElement(o["a"],{code:"const root = {\n  val: 'A',\n  left: {\n    val: 'B',\n    left: {\n      val: 'D',\n    },\n    right: {\n      val: 'E',\n    },\n  },\n  right: {\n    val: 'C',\n    right: {\n      val: 'F',\n    },\n  },\n};\n\n//\u5148\u5e8f\u904d\u5386\nfunction preorder(root) {\n  if (!root) return;\n  console.log('\u5f53\u524d\u904d\u5386\u7684\u7ed3\u70b9\u503c\u662f\uff1a', root.val);\n  preorder(root.left);\n  preorder(root.right);\n}\n//\u4e2d\u5e8f\nfunction preorder(root) {\n  if (!root) return;\n  preorder(root.left);\n  console.log('\u5f53\u524d\u904d\u5386\u7684\u7ed3\u70b9\u503c\u662f\uff1a', root.val);\n  preorder(root.right);\n}\n//\u540e\u5e8f\nfunction preorder(root) {\n  if (!root) return;\n  preorder(root.left);\n  preorder(root.right);\n  console.log('\u5f53\u524d\u904d\u5386\u7684\u7ed3\u70b9\u503c\u662f\uff1a', root.val);\n}\n\npreorder(root);\n\n//\u5148\u5e8f ABDECF\n//\u4e2d\u5e8f DBEACF\n//\u540e\u5e8f DEBFCA",lang:"js"}),r.a.createElement("h2",{id:"\u4e8c\u53c9\u6811\u7684\u67e5\u627e\u65b9\u6cd5"},r.a.createElement(a["AnchorLink"],{to:"#\u4e8c\u53c9\u6811\u7684\u67e5\u627e\u65b9\u6cd5","aria-hidden":"true",tabIndex:-1},r.a.createElement("span",{className:"icon icon-link"})),"\u4e8c\u53c9\u6811\u7684\u67e5\u627e\u65b9\u6cd5"),r.a.createElement("ul",null,r.a.createElement("li",null,"\u524d\u5e8f(\u6df1\u5ea6\u4f18\u5148)\uff1a\u6839\u8282\u70b9->\u5de6\u5b50\u6811->\u53f3\u5b50\u6811"),r.a.createElement("li",null,"\u4e2d\u5e8f(\u6df1\u5ea6\u4f18\u5148)\uff1a\u5de6\u5b50\u6811->\u6839\u8282\u70b9->\u53f3\u5b50\u6811"),r.a.createElement("li",null,"\u540e\u5e8f(\u6df1\u5ea6\u4f18\u5148)\uff1a\u5de6\u5b50\u6811->\u53f3\u5b50\u6811->\u6839\u8282\u70b9"),r.a.createElement("li",null,"\u5c42\u5e8f(\u5e7f\u5ea6\u4f18\u5148)\uff1a\u6839\u8282\u70b9->\u7b2c\u4e00\u5c42->\u7b2c\u4e8c\u5c42")),r.a.createElement("p",null,"\u770b\u4e0b\u9762\u7684\u4e00\u4e2a\u4e8c\u53c9\u6811\u7684\u56fe\uff0c\u5199\u51fa\u524d\u4e2d\u540e\u5e8f\u7684\u6392\u5217"),r.a.createElement("img",{src:t("v8Mt")}),r.a.createElement("ul",null,r.a.createElement("li",null,"\u6df1\u5ea6\u4f18\u5148\u904d\u5386",r.a.createElement("ul",null,r.a.createElement("li",null,"\u524d\u5e8f A BDGH CEIF"),r.a.createElement("li",null,"\u4e2d\u5e8f GDHB A EICF"),r.a.createElement("li",null,"\u540e\u5e8f GHDB IEFC A"))),r.a.createElement("li",null,"\u5e7f\u5ea6\u4f18\u5148\u904d\u5386",r.a.createElement("ul",null,r.a.createElement("li",null,"\u5c42\u5e8f A BC DEF GHI")))),r.a.createElement("h2",{id:"\u4e8c\u53c9\u6811\u7684\u4ee3\u7801\u5b9e\u73b0"},r.a.createElement(a["AnchorLink"],{to:"#\u4e8c\u53c9\u6811\u7684\u4ee3\u7801\u5b9e\u73b0","aria-hidden":"true",tabIndex:-1},r.a.createElement("span",{className:"icon icon-link"})),"\u4e8c\u53c9\u6811\u7684\u4ee3\u7801\u5b9e\u73b0"),r.a.createElement(o["a"],{code:"function Node(data, left, right) {\n  this.data = data;\n  this.left = left;\n  this.right = right;\n  this.show = show;\n}\n//\u663e\u793a\nfunction show() {\n  return this.data;\n}\n//\u5b9a\u4e49\u4e8c\u53c9\u6811\nfunction BST() {\n  this.insert = insert;\n  this.inOrder = inOrder;\n  this.getSmalllest = getSmalllest;\n  this.getMax = getMax;\n  this.find = find;\n  this.remove = remove;\n}\n//\u63d2\u5165\nfunction insert(data) {\n  var n = new Node(data, null, null);\n  if (this.root == null) {\n    this.root = n;\n  } else {\n    var current = this.root;\n    var parent;\n    while (true) {\n      parent = current;\n      if (data < current.data) {\n        current = current.left;\n        if (current == null) {\n          parent.left = n;\n          break;\n        }\n      } else {\n        current = current.right;\n        if (current == null) {\n          parent.right = n;\n          break;\n        }\n      }\n    }\n  }\n}\n\n//\u4e2d\u5e8f\u904d\u5386\nfunction inOrder(node) {\n  if (node != null) {\n    inOrder(node.left);\n    console.log(node.data);\n    inOrder(node.right);\n  }\n}\n\n//\u6700\u5c0f\u503c\u7684\u67e5\u627e\nfunction getSmalllest(root) {\n  var current = this.root || root;\n  while (current.left != null) {\n    current = current.left;\n  }\n  return current.data;\n}\n\n//\u6700\u5927\u503c\u7684\u67e5\u627e\nfunction getMax(root) {\n  var current = this.root || root;\n  while (current.right != null) {\n    current = current.right;\n  }\n  return current.data;\n}\n\n//\u67e5\u627e\u7279\u5b9a\u503c\nfunction find(data) {\n  var current = this.root;\n  while (current != null) {\n    if (current.data == data) {\n      return current;\n    } else if (data < current.data) {\n      current = current.left;\n    } else {\n      current = current.right;\n    }\n  }\n  return null;\n}\n\n//\u5220\u9664\nfunction remove(data) {\n  removeNode(this.root, data);\n}\n\nfunction removeNode(node, data) {\n  if (node == null) {\n    return null;\n  }\n  if (data == node.data) {\n    if (node.left == null && node.right == null) {\n      return null;\n    } else if ((node.left = null)) {\n      return node.right;\n    } else if (node.right == null) {\n      return node.left;\n    }\n    var tempNode = getSmalllest(node.right);\n    node.data = tempNode.data;\n    node.right = removeNode(node.right, tempNode.data);\n    return node;\n  } else if (data < node.data) {\n    node.left = removeNode(node.left, data);\n    return node;\n  } else {\n    node.right = removeNode(node.right, data);\n    return node;\n  }\n}\n\nvar nums = new BST();\nnums.insert(23);\nnums.insert(45);\nnums.insert(16);\nnums.insert(37);\nnums.insert(3);\nnums.insert(99);\nnums.insert(22);\n\n// nums.inOrder(nums.root)\n// console.log('\u6700\u5c0f\u8282\u70b9',nums.getSmalllest())\n// console.log('\u6700\u5927\u8282\u70b9',nums.getMax())\n\nconsole.log('\u5220\u966416', nums.remove(16));\nconsole.log('\u904d\u5386\u8282\u70b9', nums.root);\nnums.inOrder(nums.root);",lang:"js"})))}));e["default"]=n=>{var e=r.a.useContext(a["context"]),t=e.demos;return r.a.useEffect((()=>{var e;null!==n&&void 0!==n&&null!==(e=n.location)&&void 0!==e&&e.hash&&a["AnchorLink"].scrollToAnchor(decodeURIComponent(n.location.hash.slice(1)))}),[]),r.a.createElement(i,{demos:t})}},v8Mt:function(n,e,t){n.exports=t.p+"static/\u4e8c\u53c9\u6811.249d8875.png"}}]);