首页 > 代码库 > 二叉排序树(BST)的建立
二叉排序树(BST)的建立
给一个非递归的吧。
1 /* 2 已知,二叉树存储结构定义见bstree.h,请编写一个算法函数bstree creatBstree(int a[],int n), 3 以数组a中的数据作为输入建立一棵二叉排序树,并将建立的二叉排序树进行中序遍历。 4 (提示,a中的原始数据可从data1.txt中读入,实验代码详见lab9_05.c) 6 */ 7 8 #include "Arrayio.h" 9 #include "bstree.h" 10 #define N 100 11 bstree creatBstree(int a[],int n) 12 { /*根据输入的结点序列,建立一棵二叉排序树,并返回根结点的地址*/ 13 int i, flag; 14 bstree root, p, q; 15 root = (bstree)malloc(sizeof(bsnode)); 16 root->key = a[0]; 17 root->lchild = NULL; 18 root->rchild = NULL; 19 for (i = 1; i < n; i++) 20 { 21 p = root; 22 while (true) 23 { 24 if (a[i]<p->key) 25 { 26 if (p->lchild != NULL) { p = p->lchild; flag = 0; } 27 else {flag=0;break;} 28 } 29 else if (a[i]>p->key) 30 { 31 if (p->rchild != NULL) { p = p->rchild; flag = 1; } 32 else {flag=1;break;} 33 } 34 else 35 { 36 flag = -1; break; 37 } 38 } 39 q = (bstree)malloc(sizeof(bsnode)); 40 q->key = a[i]; 41 q->lchild = NULL; 42 q->rchild = NULL; 43 if (flag==1) 44 p->rchild = q; 45 else if (flag==0) 46 p->lchild = q; 47 } 48 return root; 49 } 50 51 int main() 52 { 53 int n,a[N]; 54 bstree p,t; 55 n=readData(a,N,"data1.txt"); 56 output(a,n); 57 t=creatBstree(a,n); /*创建二叉排序树*/ 58 printf("中序遍历:\n"); 59 inorder(t); /*中序遍历二叉排序树*/ 60 61 return 0; 62 }
1 /**************************************/ 2 /* 二叉排序树用的头文件 */ 3 /* 文件名:bstree.h */ 4 /**************************************/ 5 #include<stdio.h> 6 #include<stdlib.h> 7 typedef struct node1 /*二叉排序树结点定义*/ 8 { 9 int key; /*结点值*/ 10 struct node1 *lchild,*rchild; /*左、右孩子指针*/ 11 }bsnode; 12 typedef bsnode *bstree; 13 14 /*---中序遍历二叉排序树----*/ 15 void inorder(bstree t) 16 { if (t) { inorder(t->lchild); 17 printf("%8d",t->key); 18 inorder(t->rchild); 19 } 20 21 }
1 #include <stdio.h> 2 #include <stdlib.h> 3 #include <time.h> 4 #define MAX 500000 5 6 /*从文件中读入数据存入数组a*/ 7 int readData(int a[], int n,char *f ) /*函数返回成功读入的数据个数*/ 8 { 9 FILE *fp; 10 int i; 11 fp=fopen(f,"r"); 12 if (fp==NULL) return 0; 13 else 14 { 15 for (i=0;i<n && !feof(fp);i++) 16 fscanf(fp,"%d",&a[i]); 17 fclose(fp); 18 return i; 19 } 20 } 21 22 /*存盘函数*/ 23 void saveData(int a[],int n, char *f ) 24 { 25 FILE *fp; 26 int i; 27 fp=fopen(f,"w"); 28 if (fp==NULL) printf("文件建立失败!"); 29 else 30 { 31 for (i=0;i<n;i++) 32 { if (i%10==0) fprintf(fp,"%c",‘\n‘); 33 fprintf(fp,"%8d",a[i]); 34 } 35 fclose(fp); 36 } 37 } 38 39 40 /*输出长度为n的整型数组*/ 41 void output(int a[],int n) 42 { int i; 43 printf("\n数组的内容是:\n"); 44 for (i=0;i<n;i++) 45 { if (i%10==0) printf("\n"); 46 printf("%7d",a[i]); 47 } 48 printf("\n"); 49 }
二叉排序树(BST)的建立
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。