二叉排序树.docx
- 文档编号:17972557
- 上传时间:2023-08-05
- 格式:DOCX
- 页数:8
- 大小:16.87KB
二叉排序树.docx
《二叉排序树.docx》由会员分享,可在线阅读,更多相关《二叉排序树.docx(8页珍藏版)》请在冰点文库上搜索。
二叉排序树
二叉排序树(二叉查找树)
二叉排序树或者是一棵空树,或者是具有下列性质的二叉树:
(1)若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值。
(2)若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值。
(3)它的左,右子树也分别是二叉排序树。
二叉排序树有类似折半查找的特点,又采用了名字表作为存储结构,因而是一种动态查找表
二叉排序树的插入
二叉排序树是一种动态树表,特点是:
树的结构通常不是一次生成的,而是在查找过程中,当树中不存在关键字等于给定值的结点时再进行插入。
新插入的结点一定是一个新添加的叶子结点,并且是查找不成功时查找路径上访问的最后一个结点的左孩子或右孩子结点。
插入过程中:
若二叉树为空,则待插入结点*S作为根结点插入到空树中;
当二叉树非空时,将待插入结点的关键字S->key和树的根关键字比较,相等则无需要插入;大于则插入到右子树中;小于则插入到左子树中。
如此下去,直到把结点*S作为一个新的树叶插入到二叉树中,或者直支发现有相同关键字为止。
二叉排序树的删除过程
设*p为要删除的结点,其双亲为*f,左右子树分别为PL,PR
(1)若*p结点为叶子结点,即PLPR均为空,则删除*p不破坏整棵树的结构,只要修改双亲结点的指针即可。
(2)若*p结点只有左子树PL或只有右子树PR,些时
当*p是*f的左孩子时,则删除*p后将PL或PR作为*p的双亲*f的左子树;
当*p是*f的右孩子时,则删除*p后将PL或PR作为*p的双亲*f的右子树;
⑶若结点*p的左、右子树均非空,先找到*p的中序前趋结点*s(注意*s是*p的左子树中的最右下的结点,它的右链域为空),然后有两种做法:
①令*p的左子树直接链到*p的双亲结点*f的左链上,而*p的右子树链到*p的中序前趋结点*s的右链上。
②以*p的中序前趋结点*s代替*p(即把*s的数据复制到*p中),将*s的左子树链到*s的双亲结点*q的左(或右)链上。
对于删除操作理解较为容易的方法是:
*p为要删除结点,则将*p下移调整为叶子结点后将其删除;既可以将它与右子树中最小关键字交换,也可以把它与左子树中最大关键字交换。
如果*p本身就是叶子结点,则直接删除;若是非叶子结点,它最少有一棵非空子树,因此至少有一次这样的交换是可能的;如果交换之后,*p还不是叶子结点,进一步交换,*p必须最终到达可进行删除操作的树的底部,即成为叶结点。
二叉排序树的性能分析
二叉查找树中查找的运行时间与树T的高度成正比。
因为有n个结点的树的高度小则为O(logn),大则为O(n).;
对于有n个关键字元素的数据项,高度为h的二叉查找树T,空间复杂度为O(n);其中,查找元素,插入元素,删除元素的时间复杂度均为O(h);
二叉排序树的查找过程与二分法相似,也是一个逐步缩小查找范围的过程。
若查找成功,则走了一条从根结点到待查结点的路径;若失败,则是走了一条根结点到某个叶子结点的路径。
因而,查找过程中和关键字的比较次数不超过树的深度。
由于含有n个结点的二叉排序树不唯一,因而有n个结点的二叉排序树的平均查找长度为树的形态有关;
最好的情况:
二叉排序树和二叉判定树形态相同;
最坏的情况:
二叉排序树为单支树,这时平均查找长度与顺序查找时相同;
就平均性能而言,二叉排序树上的查找与二分查找相差不大,且二叉排序树上的插入和删除结点十分方便,不用大量移动结点。
/************************************************************************/
/*建立一棵二叉查找树,并进行查找元素,删除元素,调整,遍历输出 */
/************************************************************************/
#include
#include
#include
#define ERROR0
usingnamespacestd;
structTreeNode//查找树结点
{
intm_nValue;
TreeNode*lchild;//左孩子
TreeNode*rchild;//右孩子
};
classBSTree//二叉查找树类
{
private:
public:
BSTree();
~BSTree();
void InsertTree(TreeNode*&root,intdata);//插入建立二叉查找树
TreeNode*SearchTree(TreeNode*root,intdata);//在二叉查找树中搜索查找元素
voidDeleteTree(TreeNode*&root,intdata);//删除二叉查找树查找中元素
voidTrvaerTree(TreeNode*root);//前序遍历
voidMidTrvaerTree(TreeNode*root);//中序遍历
voidAftTrvaerTree(TreeNode*root);//后序遍历
};
BSTree:
:
BSTree()
{
}
BSTree:
:
~BSTree()
{
}
voidSwap(int&a,int&b)//交换两个数据,注意采用引用变量作参数
{
inttemp;
temp=a;
a=b;
b=temp;
}
voidBSTree:
:
InsertTree(TreeNode*&root,intdata)//插入数据构造二叉查找树
{
if(root==NULL)
{
root=(TreeNode*)malloc(sizeof(TreeNode));//分配结点
if(!
root)
exit(ERROR);
root->m_nValue=data;
root->lchild=NULL;
root->rchild=NULL;
}
elseif(data>root->m_nValue)
InsertTree(root->rchild,data);
elseif(data
InsertTree(root->lchild,data);
}
voidBSTree:
:
TrvaerTree(TreeNode*root)//前序遍历
{
if(root)
{
cout<<""<
}
if(root->lchild)
TrvaerTree(root->lchild);
if(root->rchild)
TrvaerTree(root->rchild);
}
voidBSTree:
:
MidTrvaerTree(TreeNode*root)//中序遍历
{
if(root->lchild)
MidTrvaerTree(root->lchild);
if(root)
{
cout<<""<
}
if(root->rchild)
MidTrvaerTree(root->rchild);
}
voidBSTree:
:
AftTrvaerTree(TreeNode*root)//后序遍历
{
if(root->lchild)
AftTrvaerTree(root->lchild);
if(root->rchild)
AftTrvaerTree(root->rchild);
if(root)
{
cout<<""<
}
}
TreeNode*BSTree:
:
SearchTree(TreeNode*root,intdata)//二叉查找树查找
{
if(root)
{
if(root->m_nValue==data)
returnroot;
elseif(data>root->m_nValue)
SearchTree(root->rchild,data);
elseSearchTree(root->lchild,data);
}
elsereturnNULL;
}
/*删除二叉查找树中元素,先将要删除的元素调整为叶子结点,调整方
式为,可以将它与右子树中最小的关键字交换,也可以把它与左子树中
最大关键字交换;如果交换之后,还不是叶子结点,则进一步调整;成
为叶子结点后直接删除,删除后的树仍为二叉查找树*/
voidBSTree:
:
DeleteTree(TreeNode*&root,intdata)
{
TreeNode*p,*q,*r;
q=SearchTree(root,data);//查找到要删除的结点
p=q;
while(p->rchild||p->lchild)
{
r=p;//记录父结点
if(p->rchild)//查找右子树中最小的
{
p=p->rchild;
while(p->lchild)
{
r=p;
p=p->lchild;
}
Swap(p->m_nValue,q->m_nValue);//交换结点元素
q=p;//更新q的位置
}
elseif(p->lchild)//查找左子树中最大的
{
p=p->lchild;
while(p->rchild)
{
r=p;
p=p->rchild;
}
Swap(p->m_nValue,q->m_nValue);//交换结点元素
q=p;
}
}
if(r->lchild==p)//删除叶子结点
r->lchild=NULL;
elseif(r->rchild==p)
r->rchild=NULL;
free(p);
p=NULL;
}
intmain()
{
BSTreeBiTree=BSTree();
TreeNode*root=NULL;
intdata;
while
(1)
{
cin>>data;
if(data==0)break;
BiTree.InsertTree(root,data);
}
BiTree.TrvaerTree(root);
cout< BiTree.MidTrvaerTree(root); cout< BiTree.AftTrvaerTree(root); cout< cin>>data; BiTree.DeleteTree(root,data); cout<<"Afterdelete: "< //BiTree.AdjustTree(root); cout<<"Afteradjust: "< BiTree.TrvaerTree(root); cout< BiTree.MidTrvaerTree(root); return1; }
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 二叉排序树
![提示](https://static.bingdoc.com/images/bang_tan.gif)