c语言二叉排序树查找

1. 用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);
}
}

2. 数据结构实验，求用C语言编一个二叉排序树的创建和查找的程序

这东西很多的这里给你一个#include <stdio.h>
#include <stdlib.h>
typedef struct np{
int dat;
struct np *left,*right;
} node;
node *create(void)
{
return (malloc(sizeof(node)));
}
node *t(node *a,int d)
{
if (a==NULL) {
a=create();
a->left =a->right =NULL;
a->dat=d;
}
else if (d>=a->dat) {
a->right =t(a->right,d);
}
else if (d<a->dat) {
a->left =t(a->left ,d);
}
return a;
}
void inorder(node *r)
{
if (r!=NULL) {
inorder(r->left );
printf("%d ",r->dat );
inorder(r->right );
}
}
int ser(node *so,int a)
{
if (so==NULL)
return 0;

else if (so->dat==a)
return 1;

else if (a>so->dat)
return ser(so->right,a);

else if (a<so->dat)
return ser(so->left ,a);

}
int main(int argc, char* argv[])
{
node *bst=NULL;
FILE *fp;
int i;
fp=fopen("c:\\dat.txt","r"); /*假设数据文件是c:\dat.txt*/

while (!feof(fp)){
fscanf(fp,"%d",&i);
bst=t(bst,i); /*生成二叉排序树*/
}
fclose(fp);
inorder(bst); /*输出二叉排序树*/
putchar('\n');
scanf("%d",&i); /*输入需要查找的数字*/
if (ser(bst,i)) printf("YES"); /*如果找到，则输出yes，否则输出no*/
else printf("NO");
return 0;
}
//-

3. 二叉排序树的建立与搜索 【用c语言编写的完整程序，包括main()函数】

#include <stdlib.h>
#include <string.h>
#include <stdio.h>

struct tree
{
char data;
tree *lchild,*rchild;
tree *father;
};

tree *Creat(tree *root,char p)
{
if(root==NULL)
{
root=(tree *)malloc(sizeof(tree));
root->lchild=NULL;
root->rchild=NULL;
root->father=NULL;
root->data = p;
}
else
{
if(root->data>=p)
{
root->lchild=Creat(root->lchild,p);
root->father = root->lchild;
}
else {
root->rchild=Creat(root->rchild,p);
root->father = root->rchild;
}
}
return root;
}

void PreOrderTraverse(tree *root)
{
if(root!=NULL)
{
PreOrderTraverse(root->lchild);
printf("%c ", root->data);
PreOrderTraverse(root->rchild);
}
}

void InOrderTraverse(tree *root) {
if ( root != NULL ) {
printf("%c ", root->data);
InOrderTraverse(root->lchild);
InOrderTraverse(root->rchild);
}
}

void PostOrderTraverse(tree *root) {
if ( root != NULL ) {
PostOrderTraverse(root->lchild);
PostOrderTraverse(root->rchild);
printf("%c ", root->data);
}
}

int main()
{
tree *root=NULL;
char p;
while( p = getchar() )
{
if ( p == ' ' || p == '\n' ) continue;
if ( p == '#' ) break;
root=Creat(root,p);
}
printf("先序： ");
InOrderTraverse(root);// 先序
printf("\n");
printf("中序： ");
PreOrderTraverse(root); // 中序
printf("\n后序： ");
PostOrderTraverse(root);// 后序
return 0;
}

4. 二叉排序树的实现（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 */
}

5. 二叉排序树的查找（C语言）代码

#include <stdlib.h>
#include <time.h>
#include <stdio.h>
#define INFMT "%d"
#define OUTFMT "%d "
/* #define NULL 0L */
#define BOOL int
#define TRUE 1
#define FALSE 0
#define LEN 10000

typedef int ElemType;
typedef struct BSTNode
{
ElemType data;
struct BSTNode *lchild, *rchild;
} BSTNode, *BSTree;

/* 插入新节点 */
void Insert(BSTree *tree, ElemType item)
{
BSTree node = (BSTree)malloc(sizeof(BSTNode));
node->data = item;
node->lchild = node->rchild = NULL;

if (!*tree)
*tree = node;
else
{
BSTree cursor = *tree;

while (1)
{
if (item < cursor->data)
{
if (NULL == cursor->lchild)
{
cursor->lchild = node;
break;
}

cursor = cursor->lchild;
}
else
{
if (NULL == cursor->rchild)
{
cursor->rchild = node;
break;
}

cursor = cursor->rchild;
}
}
}
return;
}

/* 查找指定值 */
BSTree Search(BSTree tree, ElemType item)
{
BSTree cursor = tree;

while (cursor)
{
if (item == cursor->data)
return cursor;
else if ( item < cursor->data)
cursor = cursor->lchild;
else
cursor = cursor->rchild;
}

return NULL;
}

/* 中缀遍历 */
void Inorder(BSTree tree)
{
BSTree cursor = tree;

if (cursor)
{
Inorder(cursor->lchild);
printf(OUTFMT, cursor->data);
Inorder(cursor->rchild);
}
}

/* 回收资源 */
void Cleanup(BSTree tree)
{
BSTree cursor = tree, temp = NULL;

if (cursor)
{
Cleanup(cursor->lchild);
Cleanup(cursor->rchild);
free(cursor);
}
}

/* 产生一组随机数 */
void randnum(int *a, int s)
{
int i, j, mod = s * 10;
srand(time(NULL));

for (i = 0; i < s; ++i)
{
a[i] = rand() % mod + 1;

for (j = 0; j < i; ++j)
{
if (a[i] == a[j])
{
a[i] = rand() % mod + 1;
j = -1;
continue;
}
}
}
}

void main()
{
ElemType item;
char choice;
BSTree root = NULL, ret; /* 必须赋予NULL值，否则出错 */
BOOL finish = FALSE;

printf("***欢迎使用二叉排序树演示程序***\n\n");
printf("请选择创建树的方式：\n");
printf("1. 手动输入数据创建二叉排序树\n");
printf("2. 自动产生数据创建二叉排序树\n");

do
{
scanf("%c", &choice);
getchar();

if (choice == '1' || choice == '2')
finish = TRUE;

} while (FALSE == finish);

switch (choice)
{
case '1':
{
printf("请输入数据(-10000结束)：\n");

while (1)
{
scanf(INFMT, &item);

if (-10000 != item)
Insert(&root, item);
else
break;
}
break;
}
case '2':
{
int ia[LEN], i = 0, loop = LEN;
randnum(ia, LEN);

while (loop--)
{
Insert(&root, ia[i++]);
}

break;
}
}

printf("\n\n创建完成...\n");
Inorder(root);
printf("\n\n");

/* 二叉排序树的查找测试 */
do
{
printf("\n请输入查找数据：");
scanf("%d", &item);
getchar();
printf("Searching...\n");
ret = Search(root, item);

if (NULL == ret)
printf("查找失败！");
else
printf("查找成功！");

printf("\n继续测试按y，退出按其它键。\n");
choice = getchar();
} while (choice=='y'||choice=='Y');

Cleanup(root);
}

6. C语言二叉树遍历查找问题

二叉树的遍历分为以下三种：

先序遍历：遍历顺序规则为【根左右】

中序遍历：遍历顺序规则为【左根右】

后序遍历：遍历顺序规则为【左右根】

什么是【根左右】？就是先遍历根，再遍历左孩子，最后遍历右孩子；

举个例子，看下图：

先序遍历：ABCDEFGHK

中序遍历：BDCAEHGKF

后序遍历：DCBHKGFEA

以中序遍历为例：

中序遍历的规则是【左根右】，我们从root节点A看起；

此时A是根节点，遍历A的左子树；

A的左子树存在，找到B，此时B看做根节点，遍历B的左子树；

B的左子树不存在，返回B，根据【左根右】的遍历规则，记录B，遍历B的右子树；

B的右子树存在，找到C，此时C看做根节点，遍历C的左子树；

C的左子树存在，找到D，由于D是叶子节点，无左子树，记录D，无右子树，返回C，根据【左根右】的遍历规则，记录C，遍历C的右子树；

C的右子树不存在，返回B，B的右子树遍历完，返回A；

至此，A的左子树遍历完毕，根据【左根右】的遍历规则，记录A，遍历A的右子树；

A的右子树存在，找到E，此时E看做根节点，遍历E的左子树；

E的左子树不存在，返回E，根据【左根右】的遍历规则，记录E，遍历E的右子树；

E的右子树存在，找到F，此时F看做根节点，遍历F的左子树；

F的左子树存在，找到G，此时G看做根节点，遍历G的左子树；

G的左子树存在，找到H，由于H是叶子节点，无左子树，记录H，无右子树，返回G，根据【左根右】的遍历规则，记录G，遍历G的右子树；

G的右子树存在，找到K，由于K是叶子节点，无左子树，记录K，无右子树，返回G，根据【左根右】的遍历规则，记录F，遍历F的右子树；

F的右子树不存在，返回F，E的右子树遍历完毕，返回A；

至此，A的右子树也遍历完毕；

最终我们得到上图的中序遍历为BDCAEHGKF，无非是按照遍历规则来的；

根据“中序遍历”的分析，相信先序遍历和后序遍历也可以轻松写出~

7. c语言 二叉排序树 100分

class TREE
{
private:
NODE *root; //树根
ofstream outfile; //输出流
public:
TREE(){root=0;} //构造函数，用来初始化树根
~TREE(){} //析构函数
void build_tree(NODE *&root,long data,float number); //建立二叉树
int search_tree(NODE *root,float number); //搜索二叉树
void print(NODE *root,ofstream outfile); //输出
void destory(NODE *root); //删除root

};

//建立二叉树
void TREE::build_tree(NODE *&root,long data,float number)
{
NODE *temp,*backtemp; //定义当前指针和拖后指针
if(root==0) //定义树根
{
root=new NODE;
root->lchild=root->rchild=0;
root->data=data;
root->number=number;
}
else
{
temp=root;
while(temp!=0)
{
backtemp=temp;
if(number>(temp->number))
temp=temp->lchild;
else temp=temp->rchild;
}

if(number>(backtemp->number))
{
NODE *newdode = new NODE;
newdode->lchild=newdode->rchild=0;
newdode->data=data;
newdode->number=number;
backtemp->lchild=newdode;
}
else
{
NODE *newdode = new NODE;
newdode->lchild=newdode->rchild=0;
newdode->data=data;
newdode->number=number;
backtemp->rchild=newdode;
}
}
}

//输出二叉树，按照中序遍历
void TREE::print(NODE *root,ofstream outfile)
{
if(root!=0)
{
print(root->lchild,outfile);
outfile << (root->data) << " ";
outfile << (root->number) << endl;
print(root->rchild,outfile);

}
}

void TREE::destory(NODE *root)

8. C程序 二叉排序树的创建和查找 问题

/* 初始化二叉树，即把树根指针置空 */
void InitBiTree(BiTree &T){
T=NULL;
}

/* 按先序次序建立一个二叉树*/
Status PreCreatBiTree(BiTree &T){
ElemType ch;
cin>>ch;
if (ch=='#') T = NULL;
else {
if (!(T = (BitNode *)malloc(sizeof(BitNode))))
return ERROR;
T->data = ch; // 生成根结点
PreCreatBiTree(T->lchild); // 构造左子树
PreCreatBiTree(T->rchild); // 构造右子树
}
return OK;
}
/* 按中序次序建立一个二叉树*/
Status InCreatBiTree(BiTree &T){
ElemType ch;
cin>>ch;
if (ch=='#') T = NULL;
else {
if (!(T = (BitNode *)malloc(sizeof(BitNode))))
return ERROR;
InCreatBiTree(T->lchild); // 构造左子树
T->data = ch;
InCreatBiTree(T->rchild); // 构造右子树
}
return OK;
}

9. C语言数据结构（二叉排序树的创建及查找算法）

int BSTInsert(BTNode *&T,int k)//修改此处，理由：引用型操作