二叉排序树怎么构造例题(二叉排序树怎么构造)

2023-10-17 20:28:24 社会百科 0阅读 回答者:admin

大家好,我是小百,我来为大家解答以上问题。二叉排序树怎么构造例题,二叉排序树怎么构造很多人还不知道,现在让我们一起来看看吧!

1、二叉排序树的构造过程:按照给定序列,以此将结点插入二叉排序树中,在二叉排序树中插入新结点,要保证插入后的二叉树仍符合二叉排序树的定义。

2、   插入过程:若二叉排序树为空,则待插入结点*S作为根结点插入到空树中;   当非空时,将待插结点关键字S->key和树根关键字t->key进行比较,   若s->key = t->key,则无须插入,若s->key< t->key,则插入到根的左子树中,   若s->key> t->key,则插入到根的右子树中。

3、而子树中的插入过程和在树中的插入过程相同,   如此进行下去,直到把结点*s作为一个新的树叶插入到二叉排序树中,或者直到发现树已有相同关键字的结点为止。

4、  说明:   ① 每次插入的新结点都是二叉排序树上新的叶子结点。

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

6、   ③ 对于一个任意的关键字序列构造一棵二叉排序树,其实质上对关键字进行排序。

7、查找的过程类似,从根结点开始进行比较,小于根结点的在左子树上,大于根结点的在右子树上,以此查找下去,直到查找成功或不成功(比较到叶子结点)。

本文到此讲解完毕了,希望对大家有帮助。

免责声明:本文来源网友投稿及网络整合仅代表文章作者的个人观点,与本站无关。其原创性、真实性以及文中陈述文字和内容未经本站证实,对本文以及其中全部或者部分内容文字的真实性、完整性和原创性本站不作任何保证或承诺,请读者仅作参考,并自行核实相关内容。投诉邮箱:1765130767@qq.com。

本文地址:https://www.lnsss.com/nvzhuang/shishang/962813.html