1.构造如图先构造一个二叉树的节点由一个数值和左右两个孩子组成并给他进行初始化2.构造类来进行封装把二叉树的节点起一个名字然后给一个根节点先置为空3.各个函数的含义3.1插入函数insert第一步先判断根节点是否为空如果为空则说明这个二叉树里面啥都没有所以新来的这个就是根给他开辟空间然后返回就行先给两个初始化然后找哪个地方为空cur的值和key进行比较如图如果大那说明往右走在重新更新一下值如果小的话就向左走在重新赋值如果相等就返回错误这里我们规定不允许放相同的值这里依旧走出了while说明cur现在的位置为空且大小符合key所以这里直接把key插入就行但是要注意连接父节点3.2寻找函数根据搜索二叉树的定义直接找就行最理想的是logn但是也有可能是n所以不建议使用3.3删除函数当cur不为空的时候先寻找这个节点的位置到底在哪里呢图中就是在寻找这里else说明找到了如果这里友节点为空的话那么只需要把左节点给父节点就行当然要先排除cur是根节点的可能性不然他都没有父节点如果cur是父亲的左节点就把cur的左节点和父亲的左节点连接起来如果cur是父亲的右节点就把父亲的右节点和cur的左节点连接起来最后如果是根节点就直接给把左节点当作根节点就行和上面的原理一样这里不做赘述最后一种情况是左右都不为空则就需要寻找到可以替换cur的节点数值这个数值就是左子树的最大值或者右子树的最小值这里用右子树最小值来论述先赋初值cur当作父cur的右当作子因为这里要找最小值所以就是中cur右子树的左边最后一个这个while就是在判断左子树是不是空当跳出while之后说明已经找到右边的最小值把这个与cur交换然后的if就是判断算这个最小值左变没有数据了但是他的右边可能会有这里我们先进行梳理min的左变是空的parent是min的父亲节点所以如果这里min是父亲节点的左变那么min的右边要与父亲节点的左变连接可以判断这里min不可能跑到parent的右边所以这里else就是相等既一次while都不走此时parent就是curmin就是cur的右节点且此时cur没有左节点但可能存在右节点所以连接起来删除这里很复杂不好理解3.4输出函数就左根右直接输出但是注意的是这里是把它封转起来了因为这里是需要有 _root 但是他是私有的所以这里主要的函数要是私有的但是如果是私有的话就用不了所以这里给他封装一下