资源描述
单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,2016-12-26,#,2016,数据结构,Data structure,讲授：,贺宁,二叉排序树的插入与生成,常州信息职业技术学院,02,03,二叉排序树的插入,（,1,）,插入方法,在二叉排序树中插入新结点，设其关键字域的值为,key,，要保证插入后仍满足,BST,性质。插入过程是：,若二叉排序树,T,为空，则为待插入结点申请存储空间，并令其为根；,若二叉排序树,T,不空，则将待插入结点关键字,key,与根的关键字比较：,(i),若,key=T-key,，则树中已有此关键字,key,，无须插入；,(ii),若,keykey,，则将,key,插入根的左子树中；,(iii),若,keyT-key,，则将,key,插入根的右子树中。,子树中的插入过程与上述的树中插入过程相同。如此进行下去，直到将,key,作为一个新的叶结点关键字插入到二叉排序树中，或者直到发现树中已有此关键字为止。,04,二叉排序树的插入,（,2,）,递归算法,int,InsertBSTR(BSTree *Tptr,KeyType key),/,二叉排序树插入新结点递归算法，插入成功返回,1,，失败返回,0,if,(!(*Tptr),(*Tptr)=(BSTNode *)malloc(,sizeof,(BSTNode);,if,(*Tptr =NULL), puts (,内存申请不成功,!);,return,0;,(*Tptr)-key=key;,(*Tptr)-lchild=NULL;,(*Tptr)-rchild=NULL;,else,if,(*Tptr)-key=key),return,0;,if,(keykey),InsertBSTR(,else,InsertBSTR(,return,1;,05,二叉排序树的生成,二叉排序树的生成，是从空的二叉排序树开始，每输入一个结点数据，就调用一次插入算法将它插入到当前已生成的二叉排序树中。,BSTree CreateBST(,void,),/,输入一个结点序列，建立一棵二叉排序树，将根结点指针返回,BSTree T=NULL;,/,初始时,T,为空树,KeyType key;,scanf(%d,/,读入一个关键字,while,(key),/,假设,key=0,是输入结束标志,InsertBSTR(,/,将,key,插入二叉排序树,T,scanf(%d,/,读入下一关键字,return,T;,/,返回建立的二叉排序树的根指针,注意,二叉排序树的形态与输入序列的顺序有关，第一个输入的结点一定是根结点。,二叉排序树的中序序列是一个有序序列。所以对于一个任意的关键字序列构造一棵二叉排序树，其实质是对此关键字序列进行排序，这种排序的平均执行时间亦为,O(nlgn),，“排序树”的名称也由此而来。,06,二叉排序树的生成,按输入序列（,25,32,9,18,27,6,29,）的顺序构造二叉排序树,T,，具体过程如,下图,所示,。,图示,二叉排序树生成过程,6,T,初始为空,T,25,插入,25,T,25,32,插入,32,9,32,T,25,插入,9,18,9,32,T,25,插入,18,27,18,9,32,T,25,插入,27,27,18,9,32,T,25,插入,6,THANKS,
展开阅读全文