二叉排序树,是一种规整的二叉树。每个节点的左子树都小于他,每个节点的右子树都大于他。
二叉树的遍历:
void InOrderTree(BTree *b){
if( !b )
return;
InOrderTree(b->lchild);
printf("%d ",b->data);
InOrderTree(b->rchild);
}
二叉树的查找:
int searchTree(BTree *b,int key,BTree *f,BTree *&p){
if(!b){
p = f;
return 0;
}
else if( key == b->data){
p = b;
return 1;
}
else if(key > b->data)
return searchTree(b->rchild,key,b,p);
else
return searchTree(b->lchild,key,b,p);
}
二叉树的插入:
bool insertTree(BTree *b,int key){
BTree *p,*s;
if(!searchTree(b,key,NULL,p)){
s = (BTree *)malloc(sizeof(BTree));
s->data = key;
s->lchild = s->rchild = NULL;
if(!b){
b = s;
}
else if(key < p->data){
p->lchild = s;
}else{
p->rchild = s;
}
return true;
}else
return false;
}
全部代码:
1 #include <stdio.h>
2 #include <stdlib.h>
3 typedef struct bTree{
4 int data;
5 struct bTree *lchild,*rchild;
6 }BTree;
7
8 void initialTree(BTree *b);
9 bool insertTree(BTree *b,int key);
10 int searchTree(BTree *b,int key,BTree *f,BTree *&p);
11 void InOrderTree(BTree *b);
12
13 int main(){
14 BTree *b = (BTree *)malloc(sizeof(BTree));
15 b->data = 5;
16 b->lchild = b->rchild = NULL;
17 initialTree(b);
18 InOrderTree(b);
19 getchar();
20 return 0;
21 }
22
23 void InOrderTree(BTree *b){
24 if( !b )
25 return;
26 InOrderTree(b->lchild);
27 printf("%d ",b->data);
28 InOrderTree(b->rchild);
29 }
30
31 void initialTree(BTree *b){
32 insertTree(b,5);
33 insertTree(b,3);
34 insertTree(b,6);
35 insertTree(b,2);
36 insertTree(b,1);
37 insertTree(b,8);
38 }
39 int searchTree(BTree *b,int key,BTree *f,BTree *&p){
40 if(!b){
41 p = f;
42 printf("++%d\n",p->data);
43 return 0;
44 }
45 else if( key == b->data){
46 p = b;
47 printf("--%d \n",p->data);
48 printf("找到元素key:%d\n",key);
49 return 1;
50 }
51 else if(key > b->data)
52 return searchTree(b->rchild,key,b,p);
53 else
54 return searchTree(b->lchild,key,b,p);
55 }
56 bool insertTree(BTree *b,int key){
57 BTree *p,*s;
58 if(!searchTree(b,key,NULL,p)){
59 printf("%d 没有出现在树中,可以插入在%d之后\n",key,p->data);
60 s = (BTree *)malloc(sizeof(BTree));
61 s->data = key;
62 s->lchild = s->rchild = NULL;
63 if(!b){
64 b = s;
65 }
66 else if(key < p->data){
67 p->lchild = s;
68 }else{
69 p->rchild = s;
70 }
71 return true;
72 }else
73 return false;
74 }
运行示例: