二叉排序树的查找
A选项的查找比较路径是这样的
28
\
36
/
18
\
46
/
35
该选项，若说它是升序排序树，18在右子树上，若说是降序排序树，则显然不是。
B选项的查找比较路径是这样的
18
\
36
/
28
\
46
/
35
这里看的是以36为根的子树，弃选它道理同上。36的右左子树上既有28，又有46、35。
C选项的查找比较路径是这样的
48
/
28
/
18
\
36
/
35
则以28为根的子树，它的左子树上既有18又有36、35。所以弃选。
选项D的查找比较路径如下
46
/
36
/
18
\
28
\
35
完全符合条件，所以正确选项是D。
二叉排序树最重要的性质：对于每个节点a的左子树的根al的值一定比该节点值小，节点a右子树的根节点ar的值一定比a的值大，因此可以推出==>一个节点的左子树的所有节点的值都比它的值要小，一个节点的右子树的所有节点的值都比它大！对上面的这个序列进行分析，202是925的左子树根，所以202.911.240.912.245.363这些节点都必须要比925小，911是202右子树的根，所以911.240.912.245.363都要比202大，240是911的左子树根，所以240.912.245.363都要比911小才行，但是912比911要大是吧？所以912不应该是911左子树的节点，所以错了呗！应该够清楚了吧？再不懂就没辙了！记得给分哈^.^
步骤：若根结点的关键字值等于查找的关键字，成功。
否则，若小于根结点的关键字值，递归查左子树。
若大于根结点的关键字值，递归查右子树。
若子树为空，查找不成功。
平均情况分析（在成功查找两种的情况下）：
在一般情况下，设 P（n，i）为它的左子树的结点个数为 i 时的平均查找长度。如图的结点个数为 n = 6 且 i = 3; 则 P（n,i）= P（6, 3） = [ 1+ ( P(3) + 1) * 3 + ( P(2) + 1) * 2 ] / 6= [ 1+ ( 5/3 + 1) * 3 + ( 3/2 + 1) * 2 ] / 6
注意：这里 P(3)、P(2) 是具有 3 个结点、2 个结点的二叉分类树的平均查找长度。 在一般情况，P（i）为具有 i 个结点二叉分类树的平均查找长度。
P(3) = （1+2+2）/ 3 = 5/3
P(2) = （1+2）/ 2 = 3/2∴ P（n,i）= [ 1+ ( P(i) + 1) * i + ( P(n-i-1) + 1) * (n-i-1) ] / n
∴ P（n）= P（n,i）/ n <= 2(1+I/n)lnn
因为 2(1+I/n)lnn≈1.38logn 故P(n)=O(logn)
在二叉排序树上进行插入、查找及删除等操作?
对于查找操作，我们需要遍历二叉排序树，根据当前节点的值与目标值的大小关系，决定向左子树或右子树进行查找，直到找到目标值或者遍历到空节点为止。删除操作 对于删除操作，我们需要遵循以下步骤：首先，我们需要在二叉排序树中查找待删除节点。如果待删除节点不存在，则结束操作 如果待删除节点没有子节点，...
在某个二叉查找树(即二叉排序树)中进行查找时,效率最差的情形是该二叉...
非空二叉查找树中的结点分布特点是左子树中的结点均小于树根，右子树中的结点均大于树根。因此，在二叉查找树中进行查找时，走了一条从树根出发到所找到结点的路径，到达一个空的子树则表明查找失败。根据定义，高度为h的满二叉树中有2h-l个结点，每一层上的结点数都达到最大值。完全二叉树的最高...
二叉排序树的查找长度是多少?
n个结点的二叉排序树在最坏的情况下的平均查找长度为（n+1）\/2。二叉排序树每个结点的C（i）为该结点的层次数。最坏情况下，当先后插入的关键字有序时，构成的二叉排序树蜕变为单支树，树的深度为其平均查找长度（n+1）\/2（和顺序查找相同），最好的情况是二叉排序树的形态和折半查找的判定树...
二叉排序树最长查找长度是多少?
在一棵深度为h的具有n个元素的二叉排序树,查找所有元素的最长查找长度为h。从具有n个结点的二叉搜索树中查找一个元素时，在平均情况下的时间复杂性大致为O(log2n)。从具有n个结点的二叉搜索树中查找一个元素时，在最坏情况下的时间复杂性为O(n)。
如何求二叉排序树的平均查找长度?
最坏的情况是整个二叉排序树往右倾斜(或者左倾斜),成功找到结点1需要1次, 成功找到结点2需要2次, 成功找到结点3需要3次, ...成功找到结点n需要n次, 平均查找长度为: (1+2+3+...+n) \/ n上述 1+2+3+...+n 就是等差数列求和,数学公式是 (n+1)*n \/ 2所以, (1+2+3+...+n)...
什么是二叉判定树?什么是二叉排序树?
二叉排序树又称为二叉查找树，是一种特殊的二叉树。他或者是一种空树，或者时具有下面性质的二叉树：若他的右子树非空，则右子树上所有节点的值均大于根节点的值。若他的左子树非空，则左子树上所有节点的值都小于根节点的值。左、右子树本身又各时一棵二叉排序树。三、查找结果 二叉排序树首...
二叉排序树平均查找长度
二叉排序树（Binary Sort Tree），又称二叉查找树（Binary Search Tree），亦称二叉搜索树。与次优二叉树相对，二叉排序树是一种动态树表。其特点是：树的结构通常不是一次生成的，而是在查找过程中，当树中不存在关键字等于给定值的结点时再进行插入。新插入的结点一定是一个新添加的叶子结点，并且...
二叉排序树
二叉排序树也叫二叉搜索树、二叉查找树。二叉排序树树是一颗它的左子树上的节点都小于根节点，右子树上的节点都大于根节点的二叉树，且其左右子树也是二叉排序树。实例 当要向二叉排序树中插入元素的时候，从根节点开始查找，先将根节点作为当前节点，如果要插入的值比当前节点的值小，则判断当前节...
二叉排序树查找的介绍
二叉排序树的定义：二叉排序树或者是一棵空树， 或者是一棵具有如下性质的二叉树： ⑴ 若它的左子树非空，则左子树上所有结点的值均小于根结点的值； ⑵ 若它的右子树非空，则右子树上所有结点的值均大于根结点的值； ⑶ 左、右子树本身又各是一棵二叉排序树。二叉排序树的性质： 按中序遍历...
二叉排序树和二叉查找树有相同的特性吗?
所以二叉排序树不一定是平衡树，它是只要求了左右子树与根结点存在大小关系。但是对左右子树之间没有层次差异的约束，因此通过二叉排序树进行查找不一定能够满足logn的。例如一棵只有多层左子树的而叉排序树。只有是一棵平衡的二叉排序树时，其查找时间性能才和折半查找类似。
盈建嘉瑞： #include #include #define INFMT ＂%d＂#define OUTFMT ＂%d ＂/* #define NULL 0L */#define BOOL int#define TRUE 1#define FALSE 0#define LEN 10000 typedef int ElemType; typedef struct BSTNode { ElemType data; struct BSTNode *...
公安县13141471792： 二叉排序树查找算法中的语句:kdata、 p=p - >lchild、 s - >lchild=s - >rchild=NULL、q - >lchild=s谁能告诉我这些语句的意思? - ？
盈建嘉瑞：[答案] k data :用于比较待查找值与结点值的大小 p = p->lchild :从当前搜索节点转到其左子树内继续搜索 s->lchild = s->rchild = NULL:将叶节点的两个链接置空 q->lchild = s:用当前值更改排序树中节点的值
公安县13141471792： 二叉排序树的构造和查找方法 - ？
盈建嘉瑞： 二叉排序树的构造过程:按照给定序列,以此将结点插入二叉排序树中,在二叉排序树中插入新结点,要保证插入后的二叉树仍符合二叉排序树的定义. 插入过程:若二叉排序树为空,则待插入结点*S作为根结点插入到空树中; 当非空时,...
公安县13141471792： 用C语言实现二叉排序树的查找、插入和删除 - ？
盈建嘉瑞： #include <stdio.h>#include <conio.h> #include <stdlib.h> typedef struct BitNode { char data; struct BitNode *lchild,*rchild; }BitNode,*BiTree; void CreateBiTree(BiTree &); //生成一个二叉树 void FirstOrder(BiTree); //先序递归遍历二叉树 void ...
公安县13141471792： 二叉排序树的构造与查找 - ？
盈建嘉瑞： 一样的,折半查找树是二叉判定树,跟二叉排序树是不同的
公安县13141471792： 用C语言实现二叉排序树的查找、插入和删除？
盈建嘉瑞： #include <stdio.h> #include <conio.h> #include <stdlib.h> typedef struct BitNode { char data; struct BitNode *lchild,*rchild; }BitNode,*BiTree; void CreateBiTree(BiTree &); //生成一个二叉树 void FirstOrder(BiTree); //先序递归...
公安县13141471792： 1.设有序列(45、24、53、12、28、90),请构成一棵二叉排序树,并求其查找成功时的平均查找长度. - ？
盈建嘉瑞：[答案] .45 24 53 12 28 90 平均时间=1/6(1+2*2+3*3)=7/3
公安县13141471792： 二叉排序树的创建和查找 - ？
盈建嘉瑞： 首先你需要做的是怎么比较电话号码关键字,只有能比较大小后才能根据关键字建立二叉排序树 然后就是二叉排序树的知识了,我在这里面放了二叉排序树的主要操作的介绍及实现,你可以看一下(二叉查找树就是二叉排序树) http://blog.csdn.net/sb55154634/archive/2010/07/22/5755201.aspx
公安县13141471792： 关于二叉排序树查找的问题? 8.在含有27个结点的二叉排序树上,查找关键字为35的结点,则依次比较的关键字有可能是 - ？
盈建嘉瑞：[选项] A. 28,36,18,46,35 B. 18,36,28,46,35 C. 46,28,18,36,35 D. 46,36,18,28,35请哥哥姐姐给说下解析方法,我好笨.
公安县13141471792： 二叉排序树在最坏的情况下查找最小值的时间复杂度是多少? - ？
盈建嘉瑞： 二叉排序树在最坏的情况下查找最小值的时间复杂度是O(n). 一棵空树,或者是具有下列性质的二叉树:若左子树不空,则左子树上所有结点的值均小于它的根结点的值;若右子树不空,则右子树上所有结点的值均大于它的根结点的值;左、右...
