二叉查找树

 1 #include <iostream>
 2 #include <cstdlib>
 3 using namespace std;
 4 typedef int type;
 5 typedef struct bstreenode{
 6     type key;
 7     struct bstreenode *parent;
 8     struct bstreenode *left;
 9     struct bstreenode *right;
10 }node,*bstree;
11 node* createNode(type key,node* parent,node* left,node* right){
12     node *p=(node *)malloc(sizeof(node));
13     p->key=key;
14     p->parent=parent;
15     p->left=left;
16     p->right=right;
17     return p;
18 }
19 void insertNode(bstree tree,node* p){
20     //找位置
21     node* pos=tree;
22     cout<<(pos==NULL)<<endl;
23     while(pos!=NULL){
24         if(p->key<pos->key){//向左 
25             pos=pos->left; 
26         }else{
27             pos=pos->right;
28         }
29     }
30     //插入节点 
31     cout<<"111"<<endl;
32     node* f=pos->parent;
33     cout<<f<<endl;
34     p->parent=f;
35     if(f==NULL){
36         tree=p;
37     }else if(f->key>p->key){//左孩子 
38         f->left=p; 
39     }else{
40         f->right=p;    
41     }
42 }
43 void insertNode_out(bstree tree,type key){
44     node* p=createNode(key,NULL,NULL,NULL);
45     insertNode(tree,p);
46 }
47 
48 
49 int main(){
50     bstree tree=(node*)malloc(sizeof(node));
51     tree->left=tree->right=tree->parent=NULL; 
52     insertNode_out(tree,5);
53     insertNode_out(tree,6);
54     insertNode_out(tree,4);
55     insertNode_out(tree,7);
56     insertNode_out(tree,1);
57     insertNode_out(tree,8);
58     return 0;
59 }