The Fourth Dimension Space

枯叶北风寒,忽然年以残,念往昔,语默心酸。二十光阴无一物,韶光贱,寐难安; 不畏形影单,道途阻且慢,哪曲折,如渡飞湍。斩浪劈波酬壮志,同把酒,共言欢! -如梦令

排序二叉树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 阅读(1169) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理