The Fourth Dimension Space

枯葉北風寒，忽然年以殘，念往昔，語默心酸。二十光陰無一物，韶光賤，寐難安；不畏形影單，道途阻且慢，哪曲折，如渡飛湍。斬浪劈波酬壯志，同把酒，共言歡！ -如夢令

統計

隨筆 - 414
文章 - 13
評論 - 521
引用 - 0

常用鏈接

留言簿(16)

隨筆檔案

文章檔案

Blogs in Computer Vision and Algorithm

CMU CV Group

友情鏈接

n皇后問題精彩分析
RMQ問題的精彩文章
開關燈問題

搜索

閱讀排行榜

評論排行榜

神奇的二叉排序樹

//////////////////////////////////////////////////////////////////////////

//

// BINARY_SORT_TREE

// GET_GUIDANCE_BY_MR_ZHANGHONG

// 2009年4月21日0:05:22

//

//////////////////////////////////////////////////////////////////////////

#include<iostream>

#include<cmath>

#include<cassert>

#include<algorithm>

#include<cstdio>

using namespace std;

struct node

{

int data;

node *lchild;

node *rchild;

};

template<class T>

void InsertBST(node *&tree,T key)

{

if(tree==NULL)

{

tree=new node;

tree->lchild=tree->rchild=NULL;

tree->data=key;

return;

}

if(key<tree->data)

{

InsertBST(tree->lchild,key);

}

else

{

InsertBST(tree->rchild,key);

}

template<class T>

////////////////////////////////////////////////////

node *SearchBST(node *tree,T key)

{

if(tree==NULL||key==tree->data)

return tree;

else

if(key<tree->data)

return SearchBST(tree->lchild,key);

else

return SearchBST(tree->rchild,key);

}//SearchBST

int delete_node(node *&p)//0代表刪除不成功，1代表刪除成功

{

node *q;

node *s;

if(p==NULL)

return 0;

if(p->rchild==NULL)

{

q=p;

p=p->lchild;

delete q;

}

else if(p->lchild==NULL)

{

q=p;

p=p->rchild;

delete q;

}

else

{

q=p;

s=p->lchild;

while(s->rchild!=NULL)

{

q=s;

s=s->rchild;

}

p->data=s->data;

if(q!=p)

q->rchild=s->lchild;

else

q->lchild=s->lchild;//注意這個if else 語句，這是精髓

delete s;

}

////////////////////以上兩個函數為可以實現下面這個刪除函數////////////////

//////////////////////////////////////////////////////////////////////////

template<class T>

bool DeleteBST(node *&tree,T key)

{

if(tree==NULL)

return false;

else if(tree->data==key)

{

delete_node(tree);

return true;

}

else if(tree->data>key)

{

DeleteBST(tree->lchild,key);

}

else DeleteBST(tree->rchild,key);

}

/*由于需要將進行刪除操作后的子樹和父親結點連起來

我認為需要用上面這個函數來完成查找+刪除功能,而

不能先調用Search函數然后再調用DeleteBST函數!*/

//////////////////////////////////////////////////////////////////////////

void print(node *tree)

{

if(tree==NULL)

return;

print(tree->lchild);

cout<<tree->data<<' ';

print(tree->rchild);

}

int main()

{

int arr[]={5,4,8,1,9,7,6,2,12,11,10,3};

int i;

node *tree=NULL;

for(i=0;i<sizeof(arr)/sizeof(int);i++)

{

InsertBST(tree,arr[i]);

}

print(tree);

cout<<endl;

bool test;

for(i=12;i>=0;i--)

{

test=DeleteBST(tree,i);

print(tree);

cout<<endl;

}

return 0;

}

posted on 2009-04-21 00:58 abilitytao 閱讀(1496) 評論(1) 編輯收藏引用

# re: 神奇的二叉排序樹 2009-04-21 11:59 true

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

The Fourth Dimension Space

導航

統計

常用鏈接

留言簿(16)

隨筆檔案

文章檔案

Blogs in Computer Vision and Algorithm

友情鏈接

搜索

最新評論

閱讀排行榜

評論排行榜

神奇的二叉排序樹

評論

只有注冊用戶登錄后才能發表評論。
【推薦】100%開源！大型工業跨平臺軟件C++源碼提供，建模，組態！



網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理