二叉搜索樹是專門有利于搜索(時間復(fù)雜度為logn)的二叉樹。
生成一棵二叉搜索樹關(guān)鍵是不斷地插入數(shù)據(jù)到該樹中，若當(dāng)前的root為NULL，則當(dāng)前插入的節(jié)點(diǎn)為root，否則比較左右樹插入，直到為NULL為之。
二叉搜索樹的插入代碼為:
void BST_Insert(int key)
{
構(gòu)建當(dāng)前節(jié)點(diǎn)current,初始化current,設(shè)置其value=key,左右父節(jié)點(diǎn)都為NULL;
//用x,y兩個指針來跟蹤current放置的位置
y=NULL;
x=root;
while(x)//x有下面的節(jié)點(diǎn)時
{
y=x;
x的key和當(dāng)前參數(shù)里面的key做對比，若大于當(dāng)前key，則x=left[x],否則x=right[x];
}
比較y和NULL的關(guān)系，若y==NULL,則root=NULL，有root=current;
設(shè)置parent[current]=y;
比較current的key和y的key的大小，若大，則left[y]=current,否則right[y]=current;
//插入完畢
}
使用代碼表示為:
#include <iostream>
#include <cstdlib>
using namespace std;
#ifndef NULL
#define NULL 0
#endif
#ifndef MAXSIZE
#define MAXSIZE 10
#endif
typedef struct BST//Binary Search Tree
{
int key;
//maybe there are some other satellites
struct BST* left;
struct BST* right;
struct BST* parent;
} BST;
BST* root=NULL;
void BST_Insert(int key)//add value key to the Binary Search Tree
{
BST* y=NULL;//y records the parent node
BST* x=root;//x records the current node
BST* node = new BST();
node->key = key;
node->left = NULL;
node->right = NULL;
node->parent = NULL;
while(x!=NULL)
{
y=x;
if(key<x->key)
x=x->left;
else
x=x->right;
}
node->parent=y;
if(y==NULL)
root = node;
else
{
if(key<y->key)
y->left=node;
else
y->right=node;
}
}
void BST_Delete(BST* p)
{
if(p)
{
BST_Delete(p->left);
BST_Delete(p->right);
delete p;
}
}
void BST_Build()
{
int temp;
for(int i=0;i<MAXSIZE;i++)
{
temp=rand()%MAXSIZE;
cout<<temp<<" ";
BST_Insert(temp);
}
cout<<endl;
}
void BST_Inorder_Walk(BST* p)
{
if(p)
{
BST_Inorder_Walk(p->left);
cout<<p->key<<" ";
BST_Inorder_Walk(p->right);
}
}
int main(int argc,char* argv[])
{
BST_Build();
BST_Inorder_Walk(root);
BST_Delete(root);
cout<<endl;
system("pause");
return 0;
}