The Fourth Dimension Space

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

統計

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

常用鏈接

留言簿(16)

隨筆檔案

文章檔案

Blogs in Computer Vision and Algorithm

CMU CV Group

友情鏈接

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

搜索

閱讀排行榜

評論排行榜

排序二叉樹BST(beta 2.0)

#include <iostream>

#include<algorithm>

#include<cmath>

using namespace std;

/////////////////////BEGIN_TEMPLATE_BALANCE_SORT_TREE_BY_ABILITYTAO_ACM/////////////////////////////

template< class T > class Tree;

template< class T >

class TreeNode

{

friend class Tree< T >;

public:

TreeNode(T d ):lchild( NULL ), data( d ),rchild( NULL )

{ }

T getData() const

{

return data;

}

private:

TreeNode< T > *lchild;

T data;

TreeNode< T > *rchild;

};

template <class T>

class Tree

{

private:

TreeNode<T> *root;

void InsertNodeHelper(TreeNode<T> *&tree,T key);

TreeNode<T> *SearchHelper(TreeNode<T> *tree,T key);

int DeleteNodeHelper(TreeNode<T> *&p);

bool DeleteNodeHelper2(TreeNode<T> *&tree,T key);

void PrintHelper(TreeNode<T> *tree);

public:

Tree();

void InsertNode(T n);

TreeNode<T> *SearchNode(T n);

bool DeleteNode(T n);

void Print();

bool IsEmpty();

};

template<class T>

Tree<T>::Tree()

{

root=NULL;

}

template<class T>

void Tree<T>::InsertNodeHelper(TreeNode<T> *&tree,T key)

{

if(tree==NULL)

{

tree=new TreeNode<T>(0);

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

tree->data=key;

return;

}

if(key<tree->data)

{

InsertNodeHelper(tree->lchild,key);

}

else

{

InsertNodeHelper(tree->rchild,key);

}

template<class T>

void Tree<T>::InsertNode(T n)

{

InsertNodeHelper(root,n);

}

template<class T>

TreeNode<T>* Tree<T>::SearchNode(T n)

{

return SearchHelper(root,n);

}

template<class T>

TreeNode<T>* Tree<T>::SearchHelper(TreeNode<T> *tree,T key)

{

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

return tree;

else

if(key<tree->data)

return SearchHelper(tree->lchild,key);

else

return SearchHelper(tree->rchild,key);

}

template<class T>

int Tree<T>::DeleteNodeHelper(TreeNode<T> *&p)//0代表刪除不成功，1代表刪除成功

{

TreeNode<T> *q;

TreeNode<T> *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 Tree<T>::DeleteNodeHelper2(TreeNode<T> *&tree,T key)

{

if(tree==NULL)

return false;

else if(tree->data==key)

{

DeleteNodeHelper(tree);

return true;

}

else if(tree->data>key)

{

DeleteNodeHelper2(tree->lchild,key);

}

else DeleteNodeHelper2(tree->rchild,key);

}

/*************************************************/

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

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

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

/*************************************************/

template<class T>

bool Tree<T>::DeleteNode(T n)

{

bool temp;

temp=DeleteNodeHelper2(root,n);

return temp;

}

template<class T>

void Tree<T>::PrintHelper(TreeNode<T> *tree)

{

if(tree==NULL)

return;

PrintHelper(tree->lchild);

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

PrintHelper(tree->rchild);

}

template<class T>

void Tree<T>::Print()

{

PrintHelper(root);

}

template<class T>

bool Tree<T>::IsEmpty()

{

return root==NULL;

}

/////////////////////////END_TEMPLATA_BY_ABILITYTAO_ACM///////////////////////////////////

int main()

{

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

int i;

Tree<int> test;

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

{

test.InsertNode(arr[i]);

}

TreeNode<int> *p=test.SearchNode(4);

test.Print();

cout<<endl;

bool temp;

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

{

temp=test.DeleteNode(i);

test.Print();

cout<<endl;

}

return 0;

}

posted on 2009-05-24 15:36 abilitytao 閱讀(1244) 評論(0) 編輯收藏引用

只有注冊用戶登錄后才能發表評論。




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

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

The Fourth Dimension Space

導航

統計

常用鏈接

留言簿(16)

隨筆檔案

文章檔案

Blogs in Computer Vision and Algorithm

友情鏈接

搜索

最新評論

閱讀排行榜

評論排行榜

排序二叉樹BST(beta 2.0)