二叉排序树上的构建 如何构造二叉排序树 1)构造过程: 从空树出发,依次插入R1~Rn各数据值: (1)如果二叉排序树是空树,则插入结点就是 二叉排序树的根结点; (2)如果二叉排序树是非空的,则插入值与 跟结点比较,若小于根结点的值,就插 入到左子树中去;否则插入到右子树中 示例: 45,24,53,12,22,90}
如何构造二叉排序树 1) 构造过程： 从空树出发，依次插入R1 ～ Rn各数据值： （1）如果二叉排序树是空树，则插入结点就是 二叉排序树的根结点； （2）如果二叉排序树是非空的，则插入值与 跟结点比较，若小于根结点的值，就插 入到左子树中去；否则插入到右子树中。 示例： { 45，24，53，12，22，90 }
2)二叉排序树的数据类型描述 typedef struct int key;) Elem Type typedef struct BiTNode i Elem Type data struct BitNode *lchild. rchild 3 BiTNode, BiTree 3)二叉排序树上插入结点的算法 (1)在二叉排序树上插入一个结点的算法; (2)依次输入一组数据元素,并插入到二叉排 序树中的算法
typedef struct { int key; } ElemType; typedef struct BiTNode{ ElemType data; struct BiTNode *lchild, *rchild; } BiTNode, * BiTree; （1）在二叉排序树上插入一个结点的算法； （2）依次输入一组数据元素，并插入到二叉排 序树中的算法
(1)将指针S所指的结点插入到根结点指针为T的 二叉排序树中的算法 void Insert BST( BiTree &t, Bitree S) BiTree p, q if(T)T=S; else p=t while( p) &q=p if(S->data. key p->data. key)p=p->lchild; else p= p->rchild; if (S->data. key q->dat. key) q->lchild=S else g->rchild=S return
将指针S所指的结点插入到根结点指针为T的 二叉排序树中的算法 void Insert_BST( BiTree &T, BiTree S ) { BiTree p, q; if(!T) T=S; else { p=T; while ( p ) { q = p; if (S->data.key < p->data.key) p = p->lchild; else p = p->rchild; } if (S->data.key < q->dat.key) q->lchild = S; else q->rchild = S; } return; }
(2)输入一组数据元素的序列,构造二叉排序树 的算法 void Creat bst( BiTree &t int x: BiTree S: T-NULL while( scanf ( %od,, &x),x!=0) is=(BiTNode )malloc(sizeof(BitNode)) S->data key =X, S->lchild= NULL S->rchild= NULL Insert BST(T,S) return
输入一组数据元素的序列，构造二叉排序树 的算法 void Creat BST( BiTree &T ) { int x; BiTree S; T=NULL; while ( scanf ( “%d” ,&x), x!=0 ) { S = (BiTNode *) malloc(sizeof(BitNode)); S->data.key = x; S->lchild = NULL; S->rchild = NULL; Insert_BST( T,S ); } return; }
4)二叉排序树上的查找(动态查找) int Searh Bst( BiTree T, int key i BiTree p, a, s,p=t while( p) if( p->data key -key return(1) else if p->data key> key) g=p; p=p->lchild; j else ( qp; p=p->rchild; i S=(BiTNode *)malloc(sizeof(BitNode)) S->data key =key; S->lchild=S->rchild=NULL if (!T)T=S else if q->data key >key)q->lchild=s else g->rchild=s return(O) 说明:(1)正常情况下,返回0是未找到,但实际上已经插入; (2)也可以用 return返回一个自己定义的标志值
int Searh_BST( BiTree T, int key ) { BiTree p, q, S, p = T; while ( p ) if ( p->data.key == key ) return(1); else if ( p->data.key > key) { q=p; p=p->lchild; } else {q=p; p=p->rchild; } S = (BiTNode *) malloc(sizeof(BitNode)); S->data.key = key; S->lchild=S->rchild=NULL; if (!T) T=S; else if ( q->data.key > key ) q->lchild=S; else q->rchild=S; return(0); } 说明：（1）正常情况下，返回0是未找到，但实际上已经插入； （2）也可以用return返回一个自己定义的标志值