二叉排序树的基本操作：
包含初始化，插入，删除，查找，中序遍历。。
代码如下：
//二叉排序树binary_sort_tree平均的时间复杂度为o(nlogn);初学数据结构，不足之处还请大神指点。。。
//临时变量一般为值，指针一般不适合临时比变量
#include <iostream>
using namespace std;
#define GET_ARRAY_LEN(array){ (sizeof(array) / sizeof(array[0]))}
struct my_tree
{
int data;
my_tree *left_child,*right_child;
};
my_tree* serch_position_in_tree(my_tree *test_tree,int key,my_tree * last_tree,char &flag)//查找
{
flag=0;
my_tree *p;
if (test_tree==NULL)
{
p=last_tree;//保留上一次的值,为插入操作做铺垫
return p ;
}
else if (test_tree->data==key)
{
p=test_tree;
flag=1;
return p;
}
if (test_tree->data<key)
{
serch_position_in_tree(test_tree->right_child,key,test_tree,flag);
}
else
{
serch_position_in_tree(test_tree->left_child,key,test_tree,flag);
}
}
my_tree* insert_leaf_to_tree(my_tree *test_tree,int key)//插入
{
my_tree *p=NULL;
char flag;
p=serch_position_in_tree(test_tree,key,NULL,flag);
if (flag==1)
return test_tree;
my_tree *insert_tree=new my_tree;
insert_tree->data=key;
insert_tree->left_child=NULL;
insert_tree->right_child=NULL;
if (p==NULL)
test_tree=insert_tree;
else
{
if (key>p->data)
p->right_child=insert_tree;
else p->left_child=insert_tree;
}
return test_tree;
}
void delete_my_tree(my_tree *my_test_tree)
{
if (my_test_tree->left_child==NULL)
{
my_tree *temp_tree=my_test_tree->right_child;
my_test_tree=temp_tree;
delete(temp_tree);
}
else if (my_test_tree->right_child==NULL)
{
my_tree *temp_tree=my_test_tree->left_child;
my_test_tree=temp_tree;
delete(temp_tree);
}
else//前驱
{
my_tree *temp_tree1,*temp_tree2;
temp_tree1=my_test_tree;
temp_tree2=my_test_tree->left_child;
while(temp_tree2->right_child!=NULL)
{
temp_tree1=temp_tree2;
temp_tree2=temp_tree2->right_child;
}
my_test_tree->data=temp_tree2->data;
if (temp_tree1!=my_test_tree)
temp_tree1->right_child=temp_tree2->left_child;
else temp_tree1->right_child=temp_tree2->right_child;
delete(temp_tree2);
}
}
bool delete_leaf_from_tree(my_tree *test_tree,int key)//删除
{
if (test_tree->data==key)
{
delete_my_tree(test_tree);
return true;
}
else
{
if (key>test_tree->data)
delete_leaf_from_tree(test_tree->right_child,key);
else
delete_leaf_from_tree(test_tree->left_child,key);
}
return false;
}
my_tree* init_binary_sort_tree(int a[],int n)//初始化
{
my_tree *last_tree=NULL;
for (int i=0;i<n;i++)
{
last_tree=insert_leaf_to_tree(last_tree,a[i]);
}
return last_tree;
}
void middle_serch(my_tree *test_tree)//中序遍历
{
if (test_tree==NULL)
return;
middle_serch(test_tree->left_child);
cout<<test_tree->data<<' ';
middle_serch(test_tree->right_child);
}
int main()
{
int a[]={62,58,47,35,29,37,36,51,49,56,48,50,88,73,99,93};
int n=GET_ARRAY_LEN(a);
my_tree *test_tree=init_binary_sort_tree(a,n);//按照中序遍历排进去的
delete_leaf_from_tree(test_tree,47);
middle_serch(test_tree);
return 0;
}