二叉排序树1

谁借莪１个温暖的怀抱￠ 2022-01-15 01:47 80阅读 0赞

[2019独角兽企业重金招聘Python工程师标准>>> ][2019_Python_] ![hot3.png][]

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

二叉树的遍历：

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; }

全部代码：

![15165203_xNut.gif][] ![15165203_Fu6S.gif][]

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 }

运行示例：

![15165203_LOh0.png][]

转载于:https://my.oschina.net/u/204616/blog/545053

[2019_Python_]: https://my.oschina.net/u/2663968/blog/3061697
[hot3.png]: /images/20220114/915cc791dbe84a3ebb1eedf4d38e73f1.png
[15165203_xNut.gif]: http://static.oschina.net/uploads/img/201512/15165203_xNut.gif
[15165203_Fu6S.gif]: /images/20220114/7026fbeb52cb4fcda8e3522b580c76a2.png
[15165203_LOh0.png]: /images/20220114/03ae9880c26348cbbb8f27bb490665ca.png