C language binary sort (search) tree instances
- 2020-05-30 20:53:45
- OfStack
The example of this article for you to share C language 2 fork sort (search) tree instance code, for your reference, the specific content is as follows
/**1. We have recursion Non-recursive insert (create) 2 Cross-sort (search) trees;
corresponding Insert_BinSNode(TBinSNode* T,int k),NonRecursion_Insert_BinSNode(TBinSNode* T,int k);
2. We have recursion Non-recursive lookup 2 Cross-sort (search) the tree ;
corresponding Find_BinSNode(TBinSNode *T,int s),NonRecursion_Find_BinSNode(TBinSNode *T,int s);
3. Non-recursive deletion is implemented 2 Cross-sort (search) trees;
corresponding Delete_BinSNode() ;
4. Recursive first order, in order, after the order traversal 2 Cross-sort (search) trees;
corresponding Pre_Print_BinSNode(TBinSNode T),In_Print_BinSNode(TBinSNode T),Post_Print_BinSNode(TBinSNode T);
*/
#include<stdio.h>
#include<stdlib.h>
typedef struct BinSTreeNode{
int num;
struct BinSTreeNode *lchild,*rchild;
}BinSNode,*TBinSNode;
int Empty_Tree(TBinSNode T){
if(!T){
return 1;
}else{
return 0;
}
}
/*--------------------- Non-recursive methods 2 Delete of cross-sort tree -----------------*/
void Delete_BinSNode(TBinSNode *T,int del){
TBinSNode cur,pre,lt,rblast;
cur=*T;
pre=NULL;
// if 2 The cross-sort tree is empty
if(Empty_Tree(cur)){
printf("Sorry,Tree is none");
return;
}
// if 2 The cross-sort tree is not empty, so find the element that will be deleted del. Here again 1 Look through, of course, can also be modified 1 Under the Find Function of a class
while(cur && cur->num!=del){
if(del>cur->num){
pre=cur;
cur=cur->rchild;
}else{
pre=cur;
cur=cur->lchild;
}
}
if(!cur){
printf("Sorry,you want to delete the node ,which is non-existent");
return;
}
if(cur->num==del){
printf("find the delete node,wait a minute.......\n");
}
// If the node to be deleted is found, it is immediately judged whether the node has left subtree or not
// situation 1 : the node to be deleted has no left subtree
if(!cur->lchild){
if(pre==NULL){
cur=*T;
*T=(*T)->rchild;
free(cur);
return;
}
if(pre->lchild && pre->lchild->num==del){
pre->lchild=cur->rchild;
free(cur);
return;
}
if(pre->rchild && pre->rchild->num==del){
pre->rchild=cur->rchild;
free(cur);
return;
}
}
// situation 2 : the node to be deleted has a left subtree.
if(cur->lchild){
lt=cur->lchild;
// situation 2.1 : the left subtree has no right subtree
if(!lt->rchild){
if(pre->lchild && pre->lchild->num==del){
pre->lchild=lt;
free(cur);
return;
}
if(pre->rchild && pre->rchild->num==del){
pre->rchild=lt;
free(cur);
return;
}
}
// situation 2.2: The left subtree has a right subtree
if(lt->rchild){
while(lt->rchild){
rblast=lt; // Before the largest node in the left subtree 1 A node .
lt=lt->rchild;
}
cur->num=lt->num;
rblast->rchild=lt->lchild;
free(lt);
return;
}
}
}
/*-------------------- Recursive method To find the 2 Fork sort tree -------------------*/
void Find_BinSNode(TBinSNode T,int s){
if(s==T->num){
printf("%d\n",T->num);
return;
}
if(s>T->num){
Find_BinSNode(T->rchild,s);
}else{
Find_BinSNode(T->lchild,s);
}
}
/*------------------- Non-recursive methods To find the 2 Fork sort tree --------------------*/
void NonRecursion_Find_BinSNode(TBinSNode T,int s){
if(Empty_Tree(T)){
printf("Tree is none");
return;
}
while(T && s!=T->num ){
if(s>T->num){
T=T->rchild;
}else{
T=T->lchild;
}
}
if(!T){
printf("Sorry,Not Find!");
exit(0);
}
if(s==T->num){
printf("%d\n",T->num);
}
}
/*----------------- Recursive method create / insert 2 Fork sort tree ------------------*/
void Insert_BinSNode(TBinSNode *T,int k){
// int n;
TBinSNode node;
// scanf("%d",&n);
if(Empty_Tree(*T)){
*T=(TBinSNode)malloc(sizeof(BinSNode));
(*T)->num=k;
(*T)->lchild=(*T)->rchild=NULL;
return;
}else{
if(k>(*T)->num){
Insert_BinSNode(&(*T)->rchild,k);
}else{
Insert_BinSNode(&(*T)->lchild,k);
}
}
}
/*---------------------- The first sequence traversal 2 Fork sort tree ----------------------------------*/
void Pre_Print_BinSNode(TBinSNode T){
if(T){
printf("%d ",T->num);
Pre_Print_BinSNode(T->lchild);
Pre_Print_BinSNode(T->rchild);
}
}
/*----------------------- In the sequence traversal 2 Fork sort tree -----------------------------------*/
void In_Print_BinSNode(TBinSNode T){
if(T){
In_Print_BinSNode(T->lchild);
printf("%d ",T->num);
In_Print_BinSNode(T->rchild);
}
}
/*----------------------- After the sequence traversal 2 Fork sort tree -----------------------------------*/
void Post_Print_BinSNode(TBinSNode T){
if(T){
Post_Print_BinSNode(T->lchild);
Post_Print_BinSNode(T->rchild);
printf("%d ",T->num);
}
}
/*--------------------- non-recursive create / insert 2 Fork sort tree ---------------------------*/
void NonRecursion_Insert_BinSNode(TBinSNode *T,int k){
// If it's empty 2 Fork sort tree
TBinSNode cur,p,t;
t=*T;
if(!*T){
*T=(TBinSNode)malloc(sizeof(BinSNode));
(*T)->num=k;
(*T)->lchild=(*T)->rchild=NULL;
return;
}else{ //2 The cross-sort tree is not empty.
while(t){
if(k>t->num){
cur=t;
t=t->rchild;
}else{
cur=t;
t=t->lchild;
}
}
p=(TBinSNode)malloc(sizeof(BinSNode));
p->num=k;
p->lchild=p->rchild=NULL;
if(k>cur->num){
cur->rchild=p;
}
if(k<cur->num){
cur->lchild=p;
}
}
}
int main(void){
TBinSNode T=NULL;
int k,s,del;// To create the To find the Delete the
while(scanf("%d",&k) && k){
// Insert_BinSNode(&T,k);
NonRecursion_Insert_BinSNode(&T,k);
}
// scanf("%d",&s);
// Find_BinSNode(T,s);
// NonRecursion_Find_BinSNode(T,s);
Pre_Print_BinSNode(T);
scanf("%d",&del);
Delete_BinSNode(&T,del);
Pre_Print_BinSNode(T);
return 0;
}