it 二叉搜索树插入简单模板
Description
Binary search tree: Used for searching. A binary tree where the left child contains only nodes with values less than the parent node, and where the right child only contains nodes with values greater than or equal to the parent.
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <ctime>
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std
;
const int N
= 1000000 ;
struct Node
{
int key
;
struct Node
* parents
, * left
, * right
;
} ;
struct Node
* root
, * NIL
;
void insert ( int k
)
{
struct Node
* pre
= NIL
, * now
= root
;
struct Node
* e
;
e
= ( Node
* ) malloc ( sizeof ( Node
) ) ;
e
- > key
= k
;
e
- > left
= NIL
;
e
- > right
= NIL
;
while ( now
!= NIL
) {
pre
= now
;
if ( e
- > key
< now
- > key
)
now
= now
- > left
;
else
now
= now
- > right
;
}
e
- > parents
= pre
;
if ( pre
== NIL
)
{
root
= e
;
}
else {
if ( e
- > key
< pre
- > key
) {
pre
- > left
= e
;
}
else {
pre
- > right
= e
;
}
}
return ;
}
void preorder ( Node
* u
) {
if ( u
== NIL
) return ;
printf ( "%d " , u
- > key
) ;
preorder ( u
- > left
) ;
preorder ( u
- > right
) ;
}
void inorder ( Node
* u
) {
if ( u
== NIL
) return ;
inorder ( u
- > left
) ;
printf ( "%d " , u
- > key
) ;
inorder ( u
- > right
) ;
}
void print ( Node
* u
)
{
inorder ( u
) ;
printf ( "\n" ) ;
preorder ( u
) ;
return ;
}
int main ( )
{
string cmd
;
int x
, n
= 0 ;
cin
>> n
;
rep ( i
, 1 , n
) {
cin
>> cmd
;
if ( cmd
== "insert" )
{
cin
>> x
;
insert ( x
) ;
}
else
{
print ( root
) ;
}
}
return 0 ;
}
