数据结构：二叉排序树 |
您所在的位置：网站首页 › 二叉排序树关键字序列是什么 › 数据结构：二叉排序树 |
数据结构：二叉排序树
|
什么是二叉排序树？
二叉排序树要么是空二叉树，要么具有如下特点： 二叉排序树中，如果其根结点有左子树，那么左子树上所有结点的值都小于根结点的值；二叉排序树中，如果其根结点有右子树，那么右子树上所有结点的值都大小根结点的值；二叉排序树的左右子树也要求都是二叉排序树；如图所示，就是一个二叉排序树：
二叉排序树中查找某关键字时，查找过程类似于次优二叉树，在二叉排序树不为空树的前提下，首先将被查找值同树的根结点进行比较，会有3种不同的结果： 如果相等，查找成功；如果比较结果为根结点的关键字值较大，则说明该关键字可能存在其左子树中；如果比较结果为根结点的关键字值较小，则说明该关键字可能存在其右子树中；实现函数为：（运用递归的方法） BSTree SreachBST(BSTree T, int key){ //如果递归过程中 T 为空，则查找结果，返回NULL；或者查找成功，返回指向该关键字的指针 if ((!T) || (key == T->data)) return T; else if(key data) return SreachBST(T->lchild, key);//递归遍历其左孩子 else return SreachBST(T->rchild, key);//递归遍历其右孩子 } 二叉排序树中插入关键字二叉排序树本身是动态查找表的一种表示形式，有时会在查找过程中插入或者删除表中元素，当因为查找失败而需要插入数据元素时，该数据元素的插入位置一定位于二叉排序树的叶子结点，并且一定是查找失败时访问的最后一个结点的左孩子或者右孩子。 例如，在图 1 的二叉排序树中做查找关键字 1 的操作，当查找到关键字 3 所在的叶子结点时，判断出表中没有该关键字，此时关键字 1 的插入位置为关键字 3 的左孩子。 所以，二叉排序树表示动态查找表做插入操作，只需要稍微更改一下上面的代码就可以实现，具体实现代码为： void InserBST(BSTree &T, int key){ if(!T){//如果递归过程中T为空，则初始化插入结点 BSTNode *S = new BSTNode; S->data = key; S->lchild = NULL; S->rchild = NULL; T = S; } else if(key data) InserBST(T->lchild, key); else if(key > T->data) InserBST(T->rchild, key); else if(key == T->data) {cout //如果递归过程中 T 为空，则查找结果，返回NULL；或者查找成功，返回指向该关键字的指针 if ((!T) || (key == T->data)) return T; else if(key data) return SreachBST(T->lchild, key);//递归遍历其左孩子 else return SreachBST(T->rchild, key);//递归遍历其右孩子 } void InserBST(BSTree &T, int key){ if(!T){//如果递归过程中T为空，则初始化插入结点 BSTNode *S = new BSTNode; S->data = key; S->lchild = NULL; S->rchild = NULL; T = S; } else if(key data) InserBST(T->lchild, key); else if(key > T->data) InserBST(T->rchild, key); else if(key == T->data) {cout //-1表示输入结束 InserBST(T, key); cin >> key; } } void DeleteBST(BSTree &T, int key){ BSTree p = T, f = NULL; while (p){//找到要删除的关键字 if (p->data == key) break; f = p;//f为p的父节点 if (p->data > key) p = p->lchild; else p = p->rchild; } if (!p) return; //若p为空，则表示未找到要删除的结点 BSTree q = p; if ((p->lchild) && (p->rchild)){//被删除的结点左右子树均不为空 BSTree s = p->lchild; while (s->rchild){//在p的左子树中找到其前驱结点，即最右下结点 q = s; s = s->rchild; } p->data = s->data; if(q != p) q->rchild = s->lchild;//接入q的右子树 else q->lchild = s->lchild;//接入q的左子树 delete s; return; } else if (!p->rchild){//被删除结点p没有右子树，只需重接其左子树 p = p->lchild; } else if (!p->lchild){//被删除结点p灭有左子树，只需重接其右子树 p = p->rchild; } if (!f) T = p;//被删除的是更节电 else if (q = f->lchild) f->lchild = p;//q在那边就将p重接到那边 else f->rchild = p; delete q; } 总结使用二叉排序树在查找表中做查找操作的时间复杂度同建立的二叉树本身的结构有关。即使查找表中各数据元素完全相同，但是不同的排列顺序，构建出的二叉排序树大不相同。 例如：查找表 {45，24，53，12，37，93} 和表 {12，24，37，45，53，93} 各自构建的二叉排序树图下图所示：
图 5 不同构造的二叉排序树 使用二叉排序树实现动态查找操作的过程，实际上就是从二叉排序树的根结点到查找元素结点的过程，所以时间复杂度同被查找元素所在的树的深度（层次数）有关。 为了弥补二叉排序树构造时产生如图 5 右侧所示的影响算法效率的因素，需要对二叉排序树做“平衡化”处理，使其成为一棵平衡二叉树。 平衡二叉树是动态查找表的另一种实现方式 |
【本文地址】
今日新闻 |
推荐新闻 |