㈠ 二叉排序樹的實現(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;
}
㈡ 用c語言編寫一個名為bst的函數
#include<stdio.h>
#define N 10
void bst(int *a,int n) { int i,max,min;
max=0; for ( i=0;i<n;i++ ) if ( a[i]>a[max] ) max=i;
i=a[n-1]; a[n-1]=a[max]; a[max]=i;
min=0; for ( i=0;i<n;i++ ) if ( a[i]<a[min] ) min=i;
i=a[0]; a[0]=a[min]; a[min]=i;
}
void main() { int a[N],i;
for ( i=0;i<N;i++ ) scanf("%d",&a[i]);
bst(a,N);
for ( i=0;i<N;i++ ) printf("%d ",a[i]); printf("\n");
}
㈢ 求二叉查找樹（BST）的數組實現方法（c++)
一般不會使用數組的，因為你要支持插入，刪除的動態操作的話，數組的內存管理很麻煩。
而且，數組是支持隨機訪問的，使用數組作為元素的容器的話，一個簡單的升序排列，在使用二分查找是很方便的。
㈣ 用C語言實現二叉排序的建立。查詢。刪除。插入
#include<stdio.h>
#include<stdlib.h>
#define TRUE 1
#define OK 1
#define FALSE 0
#define ERROR 0
typedef int Status;
typedef int ElemType;
#define EQ(a,b) ((a)== (b))
#define LT(a,b) ((a) <= (b))
#define LQ(a,b) ((a) >= (b))
typedef struct //靜態表的定義
{
ElemType *elem;
int Length;
}SSTable;
typedef struct BStNode //動態表的定義
{
ElemType data;
struct BStNode *lchild,*rchild;
}BStNode, *BSTree;
void Creat_Table(SSTable &S) //建立靜態表
{
int i;
printf("請輸入要建靜態表的長度： ");
scanf("%d",&S.Length);
S.elem = (int *) malloc (S.Length * sizeof(int));
printf("請輸入要建靜態表的元素： ");
for(i = 1; i <= S.Length; i++)
{
scanf("%d",&S.elem[i]);
}
}
int Search_Seq(SSTable ST,int Key) //靜態表的查找
{
for(int i = ST.Length; !EQ(ST.elem[i],Key) ; --i);
return i;
}
void Creat_BinTable(SSTable &S) //創建有序的靜態表
{
int i;
printf("請輸入要建靜態表的長度：");
scanf("%d",&S.Length);
S.elem = (int *) malloc (S.Length * sizeof(int));
printf("請輸入要建靜態表的有序表：");
for(i = 1; i <= S.Length; i++)
{
scanf("%d",&S.elem[i]);
}
}
int Search_Bin(SSTable ST,int Key) //有序表的二分查找
{
int low,high,mid;
low = 1; high = ST.Length;
while(low <= high )
{
mid = (low + high)/2;
if(EQ(Key , ST.elem[mid]))
return mid;
else if (LT(Key , ST.elem[mid]))
high = mid - 1;
else
low = mid + 1;
}
return ERROR;
}
Status InitDSTable(BSTree *DT) /* 操作結果: 構造一個空的動態查找表DT */
{
*DT=NULL;
return OK;
}
void print(int key) /* 遍歷數的時候調用的函數 */
{
printf("%d ", key);
}
void DestroyDSTable(BSTree *DT) /* 初始條件: 動態查找表DT存在。操作結果: 銷毀動態查找表DT */
{
if(*DT) /* 非空樹 */
{
if((*DT)->lchild) /* 有左孩子 */
DestroyDSTable(&(*DT)->lchild); /* 銷毀左孩子子樹 */
if((*DT)->rchild) /* 有右孩子 */
DestroyDSTable(&(*DT)->rchild); /* 銷毀右孩子子樹 */
free(*DT); /* 釋放根結點 */
*DT=NULL; /* 空指針賦0 */
}
}
BSTree SearchBST(BSTree DT,int key)
{ /* 在根指針T所指二叉排序樹中遞歸地查找某關鍵字等於key的數據元素， */
/* 若查找成功，則返回指向該數據元素結點的指針,否則返回空指針*/
if((!DT)||EQ(key,DT->data))
return DT; /* 查找結束 */
else if (LT(key,DT->data)) /* 在左子樹中繼續查找 */
return SearchBST(DT->lchild,key);
else
return SearchBST(DT->rchild,key); /* 在右子樹中繼續查找 */
}
void SearchBST1(BSTree *DT,int key,BSTree f,BSTree *p,Status *flag)
{ /* 在根指針T所指二叉排序樹中遞歸地查找其關鍵字等於key的數據元素，若查找 */
/* 成功，則指針p指向該數據元素結點，並返回TRUE，否則指針p指向查找路徑上 */
/* 訪問的最後一個結點並返回FALSE,指針f指向T的雙親，其初始調用值為NULL */
if(!*DT) /* 查找不成功 */
{
*p=f;
*flag=FALSE;
}
else if (EQ(key,(*DT)->data)) /* 查找成功 */
{
*p=*DT;
*flag=TRUE;
}
else if (LT(key,(*DT)->data))
SearchBST1(&(*DT)->lchild,key,*DT,p,flag); /* 在左子樹中繼續查找 */
else
SearchBST1(&(*DT)->rchild,key,*DT,p,flag); /* 在右子樹中繼續查找 */
}
Status InsertBST(BSTree *DT, ElemType e)
{ /* 當二叉排序樹T中不存在關鍵字等於e.key的數據元素時，插入e並返回TRUE， */
/* 否則返回FALSE。 */
BSTree p,s;
Status flag;
SearchBST1(DT,e,NULL,&p,&flag);
if(!flag) /* 查找不成功 */
{
s=(BSTree)malloc(sizeof(BStNode));
s->data = e;
s->lchild = s->rchild = NULL;
if(!p)
*DT=s; /* 被插結點*s為新的根結點 */
else if (LT(e,p->data))
p->lchild=s; /* 被插結點*s為左孩子 */
else
p->rchild=s; /* 被插結點*s為右孩子 */
return TRUE;
}
else
return FALSE; /* 樹中已有關鍵字相同的結點，不再插入 */
}
void Delete(BSTree *p)
{ /* 從二叉排序樹中刪除結點p，並重接它的左或右子樹。 */
BSTree q,s;
if(!(*p)->rchild) /* 右子樹空則只需重接它的左子樹（待刪結點是葉子也走此分支） */
{
q=*p;
*p=(*p)->lchild;
free(q);
}
else if(!(*p)->lchild) /* 只需重接它的右子樹 */
{
q=*p;
*p=(*p)->rchild;
free(q);
}
else /* 左右子樹均不空 */
{
q=*p;
s=(*p)->lchild;
while(s->rchild) /* 轉左，然後向右到盡頭（找待刪結點的前驅） */
{
q=s;
s=s->rchild;
}
(*p)->data=s->data; /* s指向被刪結點的＂前驅＂（將被刪結點前驅的值取代被刪結點的值） */
if(q!=*p)
q->rchild=s->lchild; /* 重接*q的右子樹 */
else
q->lchild=s->lchild; /* 重接*q的左子樹 */
free(s);
}
}
Status DeleteBST(BSTree *T,int key)
{ /* 若二叉排序樹T中存在關鍵字等於key的數據元素時，則刪除該數據元素結點， */
/* 並返回TRUE；否則返回FALSE。*/
if(!*T) /* 不存在關鍵字等於key的數據元素 */
return FALSE;
else
{
if EQ(key,(*T)->data) /* 找到關鍵字等於key的數據元素 */
Delete(T);
else if LT(key,(*T)->data)
DeleteBST(&(*T)->lchild,key);
else
DeleteBST(&(*T)->rchild,key);
return TRUE;
}
}
void TraverseDSTable(BSTree DT,void(*Visit)(ElemType))
{ /* 初始條件: 動態查找表DT存在，Visit是對結點操作的應用函數 */
/* 操作結果: 按關鍵字的順序對DT的每個結點調用函數Visit()一次且至多一次 */
if(DT)
{
TraverseDSTable(DT->lchild,Visit); /* 先中序遍歷左子樹 */
Visit(DT->data); /* 再訪問根結點 */
TraverseDSTable(DT->rchild,Visit); /* 最後中序遍歷右子樹 */
}
}
void Creat_BSTTable(BSTree &T)
{
int data,length;
int i;
printf("請輸入要建動態表的長度： ");
scanf("%d",&length);
printf("請輸入要建動態表： ");
for(i = 0; i < length; i++)
{
scanf("%d",&data);
InsertBST(&T,data);
}
printf ("\n");
}
#include "Head.h"
int main()
{
SSTable ST;
SSTable SS;
BSTree DT;
int Key,e,i;
printf("******************建立一個無序靜態線性表**********************： \n");
Creat_Table(ST);
printf("請輸入你要查找的元素： ");
scanf("%d", &Key);
i = Search_Seq(ST,Key);
if(i)
printf("恭喜你查找成功該元素是%d為第%d個記錄的關鍵字\n",ST.elem[i],i);
else
printf("沒找到\n");
printf("*******************建立一個有序表用二分查找*********************： \n");
Creat_BinTable(SS);
printf("請輸入你要查找的元素： ");
scanf("%d",&Key);
i = Search_Bin(SS,Key);
if(i)
printf("恭喜你查找成功該元素是%d為第%d個記錄的關鍵字\n",SS.elem[i],i);
else
printf("沒找到\n");
printf("******************建立一個二叉排序樹**********************： \n");
InitDSTable(&DT);
Creat_BSTTable(DT);
printf("中序遍歷這顆二叉排序樹的結果為： \n");
TraverseDSTable(DT,print);
printf ("\n");
printf("請輸入你要查找的元素： ");
scanf("%d", &Key);
if (SearchBST(DT,Key))
printf("恭喜你查找成功： \n");
else
printf("查找不成功： \n");
printf("請輸入你要插入的元素： ");
scanf("%d", &e);
if(InsertBST(&DT,e))
printf("成功插入一個元素後中序遍歷這顆二叉樹結果為： \n");
else
printf("插入不成功： \n");
TraverseDSTable(DT,print);
printf ("\n");
printf("請輸入你要刪除的元素： ");
scanf("%d", &Key);
if(DeleteBST(&DT,Key))
printf("成功刪除一個元素後中序遍歷這顆二叉樹結果為： \n");
else
printf("刪除不成功： \n");
TraverseDSTable(DT,print);
printf ("\n");
DestroyDSTable(&DT);
return 0;
}
㈤ C語言實現二叉搜索
這東西很多的這里給你一個#include
#include
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 (ddat) {
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 (adat)
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;
}
//-