二叉排序树的查找_二叉排序树的查找效率_二叉排序树的查找方法

一.二叉排序树定义

二叉排序树（Binary Sort Tree）或者是一棵空树；或者是具有下列性质的二叉树：

若左子树不空，则左子树上所有结点的值均小于根结点的值；若右子树不空，则右子树上所有结点的值均大于根结点的值。

左右子树也都是二叉排序树。

由图9.4 可以看出，对二叉排序树进行中序遍历，便可得到一个按关键码有序的序列，因此，一个无序序列，可通过构一棵二叉排序树而成为有序序列。二叉排序树的查找 二.二叉排序树查找过程

从其定义可见，二叉排序树的查找过程为：

若查找树为空，查找失败。

查找树非空，将给定值kx 与查找树的根结点关键码比较。

若相等，查找成功，结束查找过程，否则，

a．当给kx 小于根结点关键码，查找将在以左子女为根的子树上继续进行，转①

b．当给kx 大于根结点关键码，查找将在以右子女为根的子树上继续进行，转①

以二叉链表作为二叉排序树的存储结构，则查找过程算法程序描述如下：

typedef struct NODE

{ ElemType elem; /*数据元素字段*/

struct NODE *lc,*rc; /*左、右指针字段*/

}NodeType; /*二叉树结点类型*/

【算法9.4】

int SearchElem(NodeType *t,NodeType **p,NodeType **q,KeyType kx)

{ /*在二叉排序树t 上查找关键码为kx 的元素，若找到，返回1，且q 指向该结点，p 指向其父结点；*/

/*否则，返回0，且p 指向查找失败的最后一个结点*/int flag=0; *q=t;while(*q) /*从根结点开始

查找*/{ if(kx>(*q)->elem.key) /*kx 大于当前结点*q 的元素关键码*/

{ *p=*q; *q=(*q)->rc; } /*将当前结点*q 的右子女置为新根*/

else

{ if(kx<(*q)->elem.key) /*kx 小于当前结点*q 的元素关键码*/

{ *p=*q; *q=(*q)->lc;} /*将当前结点*q 的左子女置为新根*/

else {flag=1;break;} /*查找成功，返回*/

}

}/*while*/

return flag;

}

三.二叉排序树插入操作和构造一棵二叉排序树

先讨论向二叉排序树中插入一个结点的过程：设待插入结点的关键码为kx，为将其插入，先要在二叉排序树中进行查找，若查找成功，按二叉排序树定义，待插入结点已存在，不用插入；查找不成功时，则插入之。因此，新插入结点一定是作为叶子结点添加上去的。

构造一棵二叉排序树则是逐个插入结点的过程。

【例9.3】记录的关键码序列为：63，90，70，55，67，42，98，83，10，45，58，则构造一棵二叉排序树的过程如下：【算法9.5】

int InsertNode (NodeType **t,KeyType kx)

{ /*在二叉排序树*t 上插入关键码为kx 的结点*/

NodeType *p=*t,*q,*s; int flag=0;

if(!SearchElem(*t,&p,&q,kx)); /*在*t 为根的子树上查找*/

{ s=(NodeType *))malloc(sizeof(NodeType)); /*申请结点，并赋值*/

s->elem.key=kx;s->lc=NULL;s->rc=NULL;

flag=1; /*设置插入成功标志*/

if(!p) t=s; /*向空树中插入时*/

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-25278-1.html