二叉排序树

 1 #include "stdafx.h"
 2 #include <iostream>
 3 #include <exception>
 4 #include<string>
 5 using namespace std;
 6 
 7 
 8 /*
 9 二叉排序树:又称为二叉查找树，它或者是一棵空树，或者具有如下性质:
10 1.若他的左子树不空,则左子树上所有结点的值均小于它的根结点的值.
11 2.若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值.
12 3.它的左右子树也分别为二叉排序树.
13 如中序遍历,则可获得有序序列.
14 */
15 
16 typedef struct BiTNode
17 {
18     int data;
19     struct BiTNode *lchild,*rchild;
20 }BiTNode,*BiTree;
21 
22 //二叉排序树的查找
23 //指针f指向T的双亲，其初始调用值为NULL
24 //若查找成功,则指针P指向该数据元素结点，并返回1;
25 //否者指针p指向查找路径上访问的最后一个结点并返回0;
26 int SearchBST(BiTree T,int key,BiTree f,BiTree *p)
27 {
28     if(!T)
29     {
30         *p = f;
31         return 0;
32     }
33     else if(key==T->data)
34     {
35         *p = T;
36         return 1;
37     }
38     else if(key<T->data)
39     {
40         return SearchBST(T->lchild,key,T,p);
41     }
42     else
43         return SearchBST(T->rchild,key,T,p);
44 
45 }
46 //二叉排序树的插入
47 //当二叉排序树T中不存在关键字等于key的数据元素时
48 //插入key并且返回1,否者返回0;
49 int InsertBST(BiTree *T,int key)
50 {
51     BiTree p,s;
52     if(!SearchBST(*T,key,NULL,&p))//如果没有找到该key
53     {
54         s=(BiTree)malloc(sizeof(BiTNode));
55         s->data = key;
56         s->lchild = s->rchild = NULL;
57         if(!p)
58             *T=s;
59         else if(key<p->data)
60             p->lchild=s;
61         else 
62             p->rchild=s;
63         return 1;
64     }
65     else
66         return 0;
67 }
68 
69 int _tmain(int argc, _TCHAR* argv[])
70 { 
71     
72 
73     return 0 ;
74 }