Problem Solving using C++

Algorithm Study using C++

二叉搜索树操作(1)----生成

二叉搜索树是专门有利于搜索(时间复杂度为logn)的二叉树。
生成一棵二叉搜索树关键是不断地插入数据到该树中,若当前的root为NULL,则当前插入的节点为root,否则比较左右树插入,直到为NULL为之。
二叉搜索树的插入代码为:
void BST_Insert(int key)
{
    构建当前节点current,初始化current,设置其value=key,左右父节点都为NULL;
   //用x,y两个指针来跟踪current放置的位置
   y=NULL;
  x=root;

  while(x)//x有下面的节点时
    {  
         y=x;
         x的key和当前参数里面的key做对比,若大于当前key,则x=left[x],否则x=right[x];
    }

  比较y和NULL的关系,若y==NULL,则root=NULL,有root=current;
  设置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;
}


posted on 2007-08-24 09:19 Kingoal Lee's Alogrithm Study using cplusplus 阅读(519) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


My Links

Blog Stats

常用链接

留言簿(1)

随笔档案

搜索

最新评论

阅读排行榜

评论排行榜