二叉树顺序查找

《二叉树顺序查找》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、#include"stdio.h"#include"malloc.h"#defineNULL0typedefstructnode/*链表的方式构造节点，存储二叉排序树中的节点！这是节点类型和指针类型。*/{intkey;intother;structnode*lchild,*rchild;}Twotree;Twotree*Bsearch(Twotree*t,intx)/*查找相应的节点*/{Twotree*p;intflag=0;p=t;while(p!=NULL){if(p->key==x){printf("已找到该节

2、点！");flag=1;return(p);break;}/*寻访所有的节点，如有和关键字相同的，就输出*/if(xkey)/*如果key小于节点没有就查找左子树*/p=p->lchild;elsep=p->rchild;/*如果key大于节点没有就查找右子树*/}if(flag==0){printf("找不到值为%d的节点！",x);returnNULL;}}Twotree*InsertBST(Twotree*t,intx)/*插入节点，创建二叉顺序树*/{Twotree*s,*p,*f;p=t;while(p

3、!=NULL){f=p;/*查找过程中，f指向*p的父节点*/if(x==p->key)returnt;/*二叉排序树中已有关键字为x的元素，无序插入*/if(xkey)p=p->lchild;elsep=p->rchild;}s=(Twotree*)malloc(sizeof(Twotree));s->key=x;s->lchild=NULL;s->rchild=NULL;if(t==NULL)returns;/*原树为空，新节点成为二叉排序树的根*/if(xkey)f->lchild=s;/*新节点作

4、为*f的左孩子*/elsef->rchild=s;/*新节点作为*f的右孩子*/returnt;}Twotree*CreateBST()/*创建一个新的二叉树*/{Twotree*t;intkey;t=NULL;/*设置二叉排序树的初态为空*/scanf("%d",&key);/*读入第一个节点的关键字*/while(key!=0){t=InsertBST(t,key);scanf("%d",&key);}returnt;}voidInorder(Twotree*T)/*中序遍历*/{if(T){/*若二叉树不空*/In

5、order(T->lchild);/*中序遍历左子树*/printf("%4d",T->key);/*访问根节点*/Inorder(T->rchild);/*中序遍历右子树*/}}voidmenu()/*主函数显示菜单模块.*/{printf("┏━━━━━━━━━━━━━━━┓");printf("┠───────────────┨");printf("┃1----------查找数据-----------┃");printf("┠───────────────┨");printf("┠────────

6、───────┨");printf("┃2----------退出系统-----------┃");printf("┠───────────────┨");printf("┗━━━━━━━━━━━━━━━┛");}main()/*主函数模块.*/{Twotree*tree,*p;intseai,deli,x;intk,flag=1;printf("┏━━━━━数据输入━━━━━━┓");printf("┠───────────────┨");printf("┃---输入数据，以‘0’结束。----

7、┃");printf("┠───────────────┨");printf("┗━━━━━━━━━━━━━━━┛");printf("数据如下：");tree=CreateBST();/*调用构造二叉树函数*/printf("顺序排列所得序列为:");Inorder(tree);/*调用中序遍历函数*/printf("");/*输出遍历结果*/menu();/*主函数显示菜单模块函数.*/while(flag){printf("请选择操作（1或2）:");scanf("%d",&k);switc

8、h(k){case1:{printf("输入查找的数据:");scanf("%d",&seai);p=Bsearch(tree,seai);printf("");/*调用查找函数*/break;}case2:{flag=0;break;}/*调用退出函数*/}}}