二叉排序树1

用户1154259

发布于 2018-01-17 11:16:29

75200

代码可运行

文章被收录于专栏：xingoo, 一个梦想做发明家的程序员xingoo, 一个梦想做发明家的程序员

运行总次数：0

代码可运行

二叉排序树，是一种规整的二叉树。每个节点的左子树都小于他，每个节点的右子树都大于他。

二叉树的遍历：

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 }