因为再查找的过程中可以确定该结点要插入的合适位置,所以插入就显得比较简单了。
下方我们会先给出二叉排序树查找与插入的示意图,然后再给出相应的代码实现。
最后给出中序遍历的结果,观察我们创建的二叉排序树的中序遍历是否是有序的。
1、二叉排序树的查找与插入的示意图 我们要将集合{62, 88, 58, 47, 35, 73, 51, 99, 37, 93}中的元素放入到我们的二叉排序树中去存储,如果对我们创建好的二叉排序树进行中序搜索的话,输出的结果就是上面集合的有序序列。
下方就是我们二叉排序树从无到有的完整创建过程。
(1)、在初始化状态下我们二叉排序树的根节点为空,我们依次将集合中的元素通过搜索插入到二叉排序树中合适的位置。
(2)、首先在二叉排序中进行搜索62的位置,树为空,所以将62存入到二叉排序树的根节点中,及root=(62)。
(3)、从集合中取出88,然后查找我们的二叉排序树,发现88大于我们的根节点62,所以将88插入到62节点的右子树中,即(62)->rightChild=(88)。
(4)、从集合中取出58,然后从根节点开始查找我们现有的二叉排序树,发现55<62,将55作为62的左结点,即(62)->leftChild=(55)。
(5)、从集合中取出47,然后对二叉排序树进行搜索,发现47<55, 所以(55)->leftChild=(47)。
(6)、从集合中取出35,再次对二叉排序树进行搜索,发现35又小于47,所以(47)->leftChild=(35)。
(7)、从集合中取出73,再次对二叉排序树进行搜索,发现62<73<88, 所以有(88)->leftChild=(73)。
以此类推,要做的事情就是不断从集合中取值,然后对二叉排序树进行查找,找到合适的插入点,然后将相应的节点进行插入,具体步骤就不做过多赘述了。
searchNote字段存储的就是查找到的节点,如果未查找到,那么该结点就为空。
fatherNote字段就负责存储当前查到节点的父节点,如果该节点为空,那么当前查到的节点就为根节点。
如果查找失败,那么我们的结点将要挂到fatherNote节点上。
isFound字段负责存储查找的结果,如果二叉排序树中有要查找的节点,那么该字段为true, 如果没有,该字段就为false。
首先创建存储查找结果的对象searchResult,以备下方查找时使用。
然后判断currentRoot是否为空,如果为nil说明没有找到key相应的结点。
根据此结果设置searchResult的值,并返回searchResult。
紧接着在判断key是否等于***.data, 如果等于就说明我们找到了相应的结点,根据此结果设置searchResult的值,并返回searchResult对象。
如果没有查找失败,也没有查找成功,我们就比较key是否小于***.data,如果小于的话,说明我们的key有可能位于左子树上,然后递归查找左子树。
如果key大于***.data, 那么说明我们的key有可能位于右子树上,递归查找右子树。
内容来自网友回答
设集合,,若,,则与集合,的关系是(??????)A、B、C、D、
设集合,,若,,则与集合,的关系是( ) A、 B、 C、 D、