二叉排序树的构造和查找方法

 我来答
mantoloo
推荐于2018-11-27 · TA获得超过937个赞
知道小有建树答主
回答量:160
采纳率:100%
帮助的人:176万
展开全部
二叉排序树的构造过程:按照给定序列,以此将结点插入二叉排序树中,在二叉排序树中插入新结点,要保证插入后的二叉树仍符合二叉排序树的定义。

  插入过程:若二叉排序树为空,则待插入结点*S作为根结点插入到空树中;

  当非空时,将待插结点关键字S->key和树根关键字t->key进行比较,

  若s->key = t->key,则无须插入,若s->key< t->key,则插入到根的左子树中,

  若s->key> t->key,则插入到根的右子树中。而子树中的插入过程和在树中的插入过程相同,

  如此进行下去,直到把结点*s作为一个新的树叶插入到二叉排序树中,或者直到发现树已有相同关键字的结点为止。
  说明:

  ① 每次插入的新结点都是二叉排序树上新的叶子结点

  ② 由不同顺序的关键字序列,会得到不同二叉排序树。

  ③ 对于一个任意的关键字序列构造一棵二叉排序树,其实质上对关键字进行排序。
查找的过程类似,从根结点开始进行比较,小于根结点的在左子树上,大于根结点的在右子树上,以此查找下去,直到查找成功或不成功(比较到叶子结点)。
推荐律师服务: 若未解决您的问题,请您详细描述您的问题,通过百度律临进行免费专业咨询

为你推荐:

下载百度知道APP,抢鲜体验
使用百度知道APP,立即抢鲜体验。你的手机镜头里或许有别人想知道的答案。
扫描二维码下载
×

类别

我们会通过消息、邮箱等方式尽快将举报结果通知您。

说明

0/200

提交
取消

辅 助

模 式