二叉排序树的c语言实现

❶ 二叉排序树的实现（c语言）

/*二叉树的基本运算与实现*/
#include <stdio.h>
#include <malloc.h>
#define MAXNODE 256
typedef int datatype;
typedef struct BiTNode
{
datatype data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
typedef struct
{
BiTree link;
int flag;
}stacktype;void menu();
int Initiate(BiTree *bt,datatype x);
BiTree InsertL(BiTree bt,datatype x,BiTree parent);
BiTree InsertR(BiTree bt,datatype x,BiTree parent);
BiTree DeleteL(BiTree bt,BiTree parent);
BiTree DeleteR(BiTree bt,BiTree parent);
void PreOrder(BiTree bt);
void InOrder(BiTree bt);
void PostOrder(BiTree bt);
void LevelOrder(BiTree bt);
BiTree Find(BiTree parent,datatype a);
void NRPreOrder(BiTree bt);
void NRInOrder(BiTree bt);
void NRPostOrder(BiTree bt);void main()
{
int n,m=1;
BiTree t; /*clrscr();*/
while(m)
{
menu();
scanf("%d",&n);
switch(n)
{
case 1:{/*初始化*/
int flag;
datatype x;
printf("please input head point x:\n");
scanf("%d",&x);
flag=Initiate(&t,x);
if(flag==1)
printf("\nInitiate success!");
else
printf("\nInitiate fail!");
break;
}
case 2:{/*建树*/
break;
}
case 3:{/*插入结点x作为a的左孩子*/
datatype a,x;/*x作为a的左孩子*/
BiTree parent=t;
printf("please input a and x:\n");
scanf("%d%d",&a,&x);
parent=Find(parent,a);
parent=InsertL(t,x,parent);
if(parent!=NULL)
t=parent;
break;
}
case 4:{/*插入结点x作为a的右孩子*/
datatype a,x;/*x作为a的右孩子*/
BiTree parent=t;
printf("please input a and x:\n");
scanf("%d%d",&a,&x);
parent=Find(parent,a);
parent=InsertR(t,x,parent);
if(parent!=NULL)
t=parent;
break;
}
case 5:{/*删除结点a的左孩子*/
datatype a;
BiTree parent=t;
printf("please input a:\n");
scanf("%d",&a);
parent=Find(parent,a);
parent=DeleteL(t,parent);
if(parent!=NULL)
t=parent;
break;
}
case 6:{/*删除结点a的左孩子*/
datatype a;
BiTree parent=t;
printf("please input a:\n");
scanf("%d",&a);
parent=Find(parent,a);
parent=DeleteR(t,parent);
if(parent!=NULL)
t=parent;
break;
}
case 7:{/*递归先序遍历*/
PreOrder(t);
break;
}
case 8:{/*递归中序遍历*/
InOrder(t);
break;
}
case 9:{/*递归后序遍历*/
PostOrder(t);
break;
}
case 10:{/*层次遍历*/
LevelOrder(t);
break;
}
case 11:{/*先序遍历的非递归实现*/
NRPreOrder(t);
break;
}
case 12:{/*中序遍历的非递归实现*/
NRInOrder(t);
break;
}
case 13:{/*后序遍历的非递归实现*/
NRPostOrder(t);
break;
}
case 0:m=0;
}
}
}
void menu()
{
/*clrscr();*/
printf("\n");
printf("\t\t1.initiate\n\n");
printf("\t\t2.create thread\n\n");
printf("\t\t3.insert Left\n\n");
printf("\t\t4.insert Right\n\n");
printf("\t\t5.delete Left\n\n");
printf("\t\t6.delete Right\n\n");
printf("\t\t7.preorder\n\n");
printf("\t\t8.inorder\n\n");
printf("\t\t9.postorder\n\n");
printf("\t\t10.levelorder\n\n");
printf("\t\t11.nrpreorder\n\n");
printf("\t\t12.nrinorder\n\n");
printf("\t\t13.nrpostorder\n\n");
printf("\t\t0.exit\n\n");
printf("\n\n\n\tplease select:");
}
int Initiate(BiTree *bt,datatype x)
{
if((*bt=(BiTNode*)malloc(sizeof(BiTNode)))==NULL)
return 0;
(*bt)->data=x;
(*bt)->lchild=NULL;
(*bt)->rchild=NULL;
return 1;
}
BiTree InsertL(BiTree bt,datatype x,BiTree parent)
{
BiTree p;
if(parent==NULL)
{
printf("\nerror!\n");
return NULL;
}
if((p=(BiTNode*)malloc(sizeof(BiTNode)))==NULL)
return NULL;
p->data=x;
p->lchild=NULL;
p->rchild=NULL;
if(parent->lchild==NULL)
parent->lchild=p;
else
{
p->lchild=parent->lchild;
parent->lchild=p;
}
return bt;
}
BiTree InsertR(BiTree bt,datatype x,BiTree parent)
{
BiTree p;
if(parent==NULL)
{
printf("\nerror!\n");
return NULL;
}
if((p=(BiTNode*)malloc(sizeof(BiTNode)))==NULL)
return NULL;
p->data=x;
p->lchild=NULL;
p->rchild=NULL;
if(parent->rchild==NULL)
parent->rchild=p;
else
{
p->rchild=parent->rchild;
parent->rchild=p;
}
return bt;
}
BiTree DeleteL(BiTree bt,BiTree parent)
{
BiTree p;
if(parent==NULL||parent->lchild==NULL)
{
printf("\ndelete error!");
return NULL;
}
p=parent->lchild;
parent->lchild=NULL;
free(p);
return bt;
}
BiTree DeleteR(BiTree bt,BiTree parent)
{
BiTree p;
if(parent==NULL||parent->rchild==NULL)
{
printf("\ndelete error!");
return NULL;
}
p=parent->rchild;
parent->rchild=NULL;
free(p);
return bt;
}
void PreOrder(BiTree bt)
{
if(bt==NULL)
return;
printf("%5d",bt->data);
PreOrder(bt->lchild);
PreOrder(bt->rchild);
}
void InOrder(BiTree bt)
{
if(bt==NULL)
return;
InOrder(bt->lchild);
printf("%5d",bt->data);
InOrder(bt->rchild);
}
void PostOrder(BiTree bt)
{
if(bt==NULL)
return;
PostOrder(bt->lchild);
PostOrder(bt->rchild);
printf("%5d",bt->data);
}
void LevelOrder(BiTree bt)
{
BiTree Queue[MAXNODE];
int front,rear;
if(bt==NULL)
{
return;
}
front = -1;
rear = 0;
Queue[rear] = bt;
while(front!=rear)
{
front++;
printf("%5d",Queue[front]->data);
if(Queue[front]->lchild!=NULL)
{
rear++;
Queue[rear]=Queue[front]->lchild;
}
if(Queue[front]->rchild!=NULL)
{
rear++;
Queue[rear]=Queue[front]->rchild;
}
}//end while
}
BiTree Find(BiTree parent,datatype a)
{
BiTree p;
if(parent==NULL)
p=NULL;
else if(parent->data==a)
p=parent;
else
{
p=Find(parent->lchild,a);
if(p==NULL)
p=Find(parent->rchild,a);
}
return p;
}
void NRPreOrder(BiTree bt)
{
BiTree stack[MAXNODE],p;
int top;
if(bt==NULL)
{
printf("Tree is empty!\n");
return;
}
top=-1;
p=bt;
while((p!=NULL)||(top!=-1))
{
while(p!=NULL)
{
printf("%5d",p->data);
if(top==MAXNODE-1)
{
printf("Stack overflow!\n");
return;
} /* end if */
else
{
top++;
stack[top]=p;
} /* end if-else */
p=p->lchild;
} /* end while p */
p=stack[top];
top--;
p=p->rchild;
} /* end while p && top */
}
void NRInOrder(BiTree bt)
{
BiTree stack[MAXNODE],p;
int top;
if(bt==NULL)
{
printf("Tree is empty!\n");
return;
}
top=-1;
p=bt;
while((p!=NULL)||(top!=-1))
{
while(p!=NULL)
{
if(top==MAXNODE-1)
{
printf("Stack overflow!\n");
return;
} /* end if */
else
{
top++;
stack[top]=p;
} /* end if-else */
p=p->lchild;
} /* end while p */
p=stack[top];
top--;
printf("%5d",p->data);
p=p->rchild;
} /* end while p && top */
}
void NRPostOrder(BiTree bt)
{
stacktype stack[MAXNODE];
BiTree p;
int top,sign;
if(bt==NULL)
{
printf("Tree is empty!\n");
return;
}
top=-1;
p=bt;
while((p!=NULL)||(top!=-1))
{
if(p!=NULL) /*结点第一次入栈*/
{
top++;
stack[top].link=p;
stack[top].flag=1; /*标记第一次入栈*/
p=p->lchild;
} /* end if */
else
{
p=stack[top].link;
sign=stack[top].flag;
top--;
if(sign==1) /*结点第二次入栈*/
{
top++;
stack[top].link=p;
stack[top].flag=2; /*标记第二次入栈*/
p=p->rchild;
} /* end if */
else
{
printf("%5d",p->data);
p=NULL;
} /* end if-else */
} /* end if-else */
} /* end while */
}

❷ 用c语言写二叉排序树的基本操作要求实现查找插入和删除运算，统计二叉树中度为2的结点个数和叶子结点个数

#include<stdio.h>
#include<stdlib.h>
#definemaxNumberLength16
typedefstructnode
{
intdata;
structnode*lchild,*rchild;
}node;
node*create(void);
voidinsert(node*&root,intdata);
voidinOrder(node*root);
voidremove(node*&root,intdata);
voidsubRemove(node*root,node*&now);
boolsearch(node*root,intdata);
voidfindParent(node*root,node*data,node*&parent);
intmain(void)
{
node*root;
intengine=1;
intdata;
printf("输入元素:");
root=create();
printf("构造完成,中序遍历:");
inOrder(root);
putchar('
');
while(engine!=0)
{
printf("

1.插入2.删除3.查找0.退出
输入操作编号:");
fflush(stdin);
scanf("%d",&engine);
switch(engine)
{
case1:
printf("输入插入的元素值:");
scanf("%d",&data);
insert(root,data);
printf("插入完成,中序遍历:");
inOrder(root);
break;
case2:
printf("输入删除的元素值:");
scanf("%d",&data);
remove(root,data);
break;
case3:
printf("输入查找的元素值:");
scanf("%d",&data);
if(search(root,data))
printf("找到该元素，元素值%d
",data);
else
printf("没有该元素
");
case0:
break;
default:
printf("没有该选项
");
}
}
return0;
}
node*create(void)//构造
{
charnumToChar[maxNumberLength];
charinch;
intlocation,data;
node*root=NULL;
inch=getchar();
while((inch<'0'||inch>'9')&&inch!='
')
inch=getchar();
while(inch!='
')
{
location=0;
while(inch>='0'&&inch<='9')
{
numToChar[location++]=inch;
inch=getchar();
}
numToChar[location]='';
while((inch<'0'||inch>'9')&&inch!='
')
inch=getchar();
data=atoi(numToChar);
insert(root,data);
}
returnroot;
}
voidinsert(node*&root,intdata)//插入
{
if(root==NULL)
{
root=(node*)malloc(sizeof(node));
root->data=data,root->lchild=root->rchild=NULL;
}
else
{
if(data<=root->data)
insert(root->lchild,data);
else
insert(root->rchild,data);
}
}
voidinOrder(node*root)//中序遍历
{
if(root!=NULL)
{
inOrder(root->lchild);
printf("%d",root->data);
inOrder(root->rchild);
}

}
voidremove(node*&root,intdata)//删除
{
if(search(root,data))
{
node*temp=root,*parent;
while(temp)
{
if(temp->data<data)
temp=temp->rchild;
elseif(temp->data>data)
temp=temp->lchild;
else
break;
}
subRemove(root,temp);
printf("删除成功，中序遍历:");
inOrder(root);
}
else
printf("没有该元素
");
}
boolsearch(node*root,intdata)
{
node*temp=root;
while(temp)
{
if(temp->data<data)
temp=temp->rchild;
elseif(temp->data>data)
temp=temp->lchild;
else
break;
}
returntemp;
}
voidfindParent(node*root,node*data,node*&parent)
{
if(root)
{
if(root->lchild==data||root->rchild==data)
parent=root;
else
{
findParent(root->lchild,data,parent);
findParent(root->rchild,data,parent);
}
}
}
voidsubRemove(node*root,node*&now)
{
if(now->lchild==NULL&&now->rchild==NULL)
{
node*parent;
findParent(root,now,parent);
if(parent->lchild==now)
parent->lchild=NULL;
else
parent->rchild=NULL;
free(now);
}
else
{
node*temp=now;
intdata;
if(temp->lchild)
{
temp=temp->lchild;
while(temp->rchild)
temp=temp->rchild;
}
else
{
temp=temp->rchild;
while(temp->lchild)
temp=temp->lchild;
}
data=temp->data,temp->data=now->data,now->data=data;
now=temp;
subRemove(root,now);
}
}

❸ 用C语言实现二叉排序树排序，并按递减顺序打印各个数据

#include <stdio.h>
#include <malloc.h>
typedef int KeyType;
typedef char InfoType[10];
typedef struct node //记录类型
{
KeyType key; //关键字项
InfoType data; //其他数据域
struct node *lchild,*rchild; //左右孩子指针
} BSTNode;
int InsertBST(BSTNode *&p,KeyType k)
{
if (p==NULL) //原树为空, 新插入的记录为根结点
{
p=(BSTNode *)malloc(sizeof(BSTNode));
p->key=k;
p->lchild=p->rchild=NULL;
return 1;
}
else if (k==p->key) //树中存在相同关键字的结点,返回0
return 0;
else if (k<p->key)
return InsertBST(p->lchild,k); //插入到*p的左子树中
else
return InsertBST(p->rchild,k); //插入到*p的右子树中
}
BSTNode *CreateBST(KeyType A[],int n) //返回BST树根结点指针
{
BSTNode *bt=NULL; //初始时bt为空树
int i=0;
while (i<n)
{
InsertBST(bt,A[i]); //将关键字A[i]插入二叉排序树T中
i++;
}
return bt; //返回建立的二叉排序树的根指针
}

void DispInDescrease(BSTNode *bt){ //按从小到大输出查找树中的内容，对该树中序遍历即可
if(bt){
DispInDescrease(bt->lchild);
printf("%d\t",bt->key);
DispInDescrease(bt->rchild);
}
}
void main()
{
BSTNode *bt,*p,*f;
int n=9;
KeyType a[]={1,12,5,8,3,10,7,13,9};
bt=CreateBST(a,n);
DispInDescrease(bt);
}
//已上机验证成功

❹ 二叉排序树的实现(c语言)

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
typedef struct btnode
{char data; /*suppose the data field's type is char*/
struct btnode *lchild; /*left pointer field */
struct btnode *rchild; /*right pointer field */
}NODE;
void main()
{ NODE *root,*q,n;
NODE *create(NODE *p);
void preorder(NODE *root);
void inorder(NODE *root);
void postorder(NODE *root);
int t;
q=&n;
root=create(q);
printf("At the first,we create a tree\n");
printf("Please input nodes of tree\n");
if (root==NULL) printf("It's an empty tree!\n");
else
{
printf("\n1.The preordetraverse \n");
printf(" 2.The inordertraverse \n");
printf(" 3.The postordertraverse \n");
printf(" Please choose a kind of order\n");
scanf("%d",&t);
switch (t)
{
case 1: preorder(root); break;
case 2: inorder(root); break;
case 3:postorder(root); break;
default: printf(" The error!");
}
}
}

NODE * create(NODE *p) /*create the structure of binary tree */
{ char ch;
NODE *t;
scanf("%c",&ch);
if(ch==' ') p=NULL;
else
{p->data=ch;
t=(NODE *)malloc(sizeof(NODE));
p->lchild=create(t);
t=(NODE*)malloc(sizeof(NODE));
p->rchild=create(t);
}
return p;
}
void preorder(NODE *root) /*travel the tree using preorder */
{ if (root!=NULL)
{ printf( " %c", root->data);
preorder(root->lchild);
preorder(root->rchild);
}
return;
}
void inorder (NODE *root) /*travel the tree using inorder */
{ if (root!=NULL)
{ inorder(root->lchild);
printf(" %c ", root->data);
inorder(root->rchild);
}
return;
}
void postorder(NODE *root) /*travel the tree using postorder */
{ if (root!=NULL)
{ postorder (root->lchild);
postorder (root->rchild);
printf(" %c ", root->data);
}
return;
}