二叉树插入Word格式文档下载.docx
- 文档编号:6500219
- 上传时间:2023-05-06
- 格式:DOCX
- 页数:33
- 大小:20.55KB
二叉树插入Word格式文档下载.docx
《二叉树插入Word格式文档下载.docx》由会员分享,可在线阅读,更多相关《二叉树插入Word格式文档下载.docx(33页珍藏版)》请在冰点文库上搜索。
printf("
请输入关键字(输入0为结束标志):
\n"
);
T=CreateBST();
ListBinTree(T);
请输入欲插入关键字:
"
scanf("
%d"
&
key);
InsertBST(&
T,key);
}
voidInsertBST(BSTree*Tptr,KeyTypekey)
{//若二叉排序树*Tptr中没有关键字为key,则插入,否则直接返回
BSTNode*f,*p=*Tptr;
//p的初值指向根结点
while(p){//查找插入位置
if(p->
key==key)return;
//树中已有key,无须插入
f=p;
//f保存当前查找的结点
p=(key<
p->
key)?
p->
lchild:
rchild;
//若key<
key,则在左子树中查找,否则在右子树中查找
}
p=(BSTNode*)malloc(sizeof(BSTNode));
key=key;
lchild=p->
rchild=NULL;
//生成新结点
if(*Tptr==NULL)//原树为空
*Tptr=p;
//新插入的结点为新的根
else//原树非空时将新结点*p作为*f的左孩子或右孩子插入
if(key<
f->
key)
f->
lchild=p;
elsef->
rchild=p;
BSTreeCreateBST(void)
{//输入一个结点序列,建立一棵二叉排序树,将根结点指针返回
BSTreeT=NULL;
//初始时T为空树
//读入一个关键字
while(key){//假设key=0是输入结束标志
InsertBST(&
//将key插入二叉排序树T
scanf("
//读入下一关键字
returnT;
//返回建立的二叉排序树的根指针
//用广义表表示二叉树
voidListBinTree(BSTreeT)
if(T!
=NULL)
{
printf("
T->
if(T->
lchild!
=NULL||T->
rchild!
{
printf("
("
ListBinTree(T->
lchild);
if(T->
printf("
"
rchild);
)"
}
2.二叉树查找
BSTNode*SearchBST(BSTreeT,KeyTypekey);
BSTNode*p;
请输入欲查找关键字:
p=SearchBST(T,key);
if(p==NULL)
没有找到%d!
key);
else
找到%d!
ListBinTree(p);
BSTNode*SearchBST(BSTreeT,KeyTypekey)
{//在二叉排序树T上查找关键字为key的结点,成功时返回该结点位置,否则返回NULL
if(T==NULL||key==T->
key)//递归的终结条件
returnT;
//若T为空,查找失败;
否则成功,返回找到的结点位置
if(key<
T->
returnSearchBST(T->
lchild,key);
rchild,key);
//继续在右子树中查找
3.二叉树删除
voidDelBSTNode(BSTree*Tptr,KeyTypekey);
请输入欲删除关键字:
DelBSTNode(&
voidDelBSTNode(BSTree*Tptr,KeyTypekey)
{//在二叉排序树*Tptr中删去关键字为key的结点
BSTNode*parent=NULL,*p=*Tptr,*q,*child;
while(p){//从根开始查找关键字为key的待删结点
key==key)break;
//已找到,跳出查找循环
parent=p;
//parent指向*p的双亲
//parent指向*p的左或右子树中继续找
if(!
p)return;
//找不到被删结点则返回
q=p;
//q记住被删结点*p
if(q->
lchild&
&
q->
rchild)//*q的两个孩子均非空,故找*q的中序后继*p
for(parent=q,p=q->
lchild;
parent=p,p=p->
//现在情况(3)已被转换为情况
(2),而情况
(1)相当于是情况
(2)中child=NULL状况
child=(p->
lchild)?
//若是情况
(2),则child非空;
否则child为空
if(!
parent)//*p的双亲为空,说明*p为根,删*p后应修改根指针
*Tptr=child;
//若是情况
(1),则删去*p后,树为空;
否则child变为根
else{//*p不是根,将*p的孩子和*p的双亲进行连接,*p从树上被摘下
if(p==parent->
lchild)//*p是双亲的左孩子
parent->
lchild=child;
//*child作为*parent的左孩子
elseparent->
rchild=child;
//*child作为*parent的右孩子
if(p!
=q)//是情况(3),需将*p的数据复制到*q
q->
key=p->
key;
//若还有其它数据域亦需复制
free(p);
//释放*p占用的空间
4.二叉树建立
5.二叉树建立1
/*二叉树的链式存储表示*/
typedefcharDataType;
/*应由用户定义DataType的实际类型*/
typedefstructnode
{DataTypedata;
structnode*lchild,*rchild;
/*左右孩子指针*/
}BinTNode;
/*结点类型*/
typedefBinTNode*BinTree;
/*构造二叉链表*/
voidCreateBinTree(BinTree*T)
charch;
if((ch=getchar())=='
'
)
*T=NULL;
{/*读入非空格*/
*T=(BinTNode*)malloc(sizeof(BinTNode));
/*生成结点*/
(*T)->
data=ch;
CreateBinTree(&
(*T)->
lchild);
/*构造左子树*/
rchild);
/*构造右子树*/
/*用广义表表示二叉树*/
voidListBinTree(BinTreeT)
%c"
data);
/*用凹入表表示二叉树*/
voidDisplayBinTree(BinTreeT)
BinTreestack[100],p;
intlevel[100],top,n,i;
用凹入表表示二叉树:
top=1;
stack[top]=T;
level[top]=3;
while(top>
0)
p=stack[top];
n=level[top];
for(i=1;
i<
=n;
i++)
"
%c\n"
p->
top--;
if(p->
{
top++;
stack[top]=p->
level[top]=n+3;
}
/*前序遍历二叉树*/
voidPreorder(BinTreeT)
if(T)
/*访问结点*/
Preorder(T->
main()
BinTreeT;
请输入先序序列(虚结点用空格表示):
CreateBinTree(&
T);
DisplayBinTree(T);
前序遍历:
Preorder(T);
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 二叉 插入