main.cpp

C++编写的数据结构平衡二叉树的生成与实现

#include <iostream>
#include <stdlib.h>

using namespace std;
/*
类说明：树结点的超类 
*/
class TreeNode{
    protected:
        int _key;
    public:
        TreeNode *lchild;
        TreeNode *rchild;
        TreeNode(int key):_key(key){lchild=0;rchild=0;}
        virtual void Display(){}
         int Key(){return _key;}
};
/*
类说明：整形树结点的 
*/
class IntegerTreeNode:public TreeNode{
    int _data;
    public:
        IntegerTreeNode(int key,int value):TreeNode(key),_data(value){}
        void Display()
        {  
            cout<<"Key:"<<Key()<<"\tInteger:"<<_data<<endl;
        }    
};
/*
类说明：String树结点的 
*/
class StringTreeNode:public TreeNode{
    char * _data;
    public:
        StringTreeNode(int key,char * value):TreeNode(key){_data = value;}
        void Display()
        {
            
            cout<<"Key:"<<Key()<<"\tString:"<<_data<<endl;
        }    
};

/*
类说明：异质树 
排序树：右子树大于左子树 
*/
class SortTree
{
    TreeNode * _root;
    private:
        bool SeachNodeInner(TreeNode *curNode,TreeNode *searchNode,TreeNode **lastNode);
        void TravelLMR(TreeNode *curNode);
		bool DeleteNodeInner(TreeNode **curNode,int key);
		bool DeleteNodeSecond(TreeNode **curNode);
    public:
        void AddNode(TreeNode *newNode);
        bool SeachNodeByKey(TreeNode *newNode,TreeNode **lastNode);
        bool DeleteNode(int key);
        void Display();
};
void SortTree::TravelLMR(TreeNode *curNode)
{
    if(curNode->lchild)TravelLMR(curNode->lchild);
    if(curNode)curNode->Display();
    if(curNode->rchild)TravelLMR(curNode->rchild);
} 
/*
中序遍历 
*/
void SortTree::Display()
{
    cout<<"中序遍历如下："<<endl;
    if(_root==0){
        cout<<"NULL Tree"<<endl;
        return;
    }    
    TravelLMR(_root);
}
       
/*
内部方法 ，递归查找树节
curNode:当前遍历的节点 
searchNode:要查找的节点 
lastNode:最后遍历的节点 
*/
bool SortTree::SeachNodeInner(TreeNode *curNode,TreeNode *searchNode,TreeNode **lastNode)
{
    
	
    if(curNode->Key()==searchNode->Key())//找到键值 一样大的节点 
    {
        return true;
    }else if(searchNode->Key()>curNode->Key())//查找键值>当前遍历节点键值 
    {
        
        if(!curNode->rchild)
        {
            *lastNode = curNode;
            return false;
        }    
        return SeachNodeInner(curNode->rchild,searchNode,lastNode);//遍历左子树 
    }
    else//查找键值<当前遍历节点键值 
    {
        if(!curNode->lchild)
        {
            *lastNode = curNode;
            return false;
        }   
        return SeachNodeInner(curNode->lchild,searchNode,lastNode);//遍历右子树 
    } 
}     
/*
功能:查找树节点,别返回插入位置 
searchNode:要查找的节点 
lastNode:该节点的插入位置 
返回：是否已经查找到 
*/
bool SortTree::SeachNodeByKey(TreeNode *searchNode,TreeNode **lastNode)
{
	
    if(_root==0)//树为空 
    {
        *lastNode = _root;
        return false;
    }    
    return  SeachNodeInner(_root,searchNode,lastNode);
	
    
}
/*
按照指定key删除树节点
*/
bool SortTree::DeleteNode(int key)
{
	if(_root==0)return false;
	return DeleteNodeInner(&_root,key);
}
/*
按照指定key删除树节点的递归调用方法
*/
bool SortTree::DeleteNodeInner(TreeNode **curNode,int key)
{
	if((*curNode)==0)return false;
	if((*curNode)->Key()==key) return DeleteNodeSecond(curNode);//找到节点并删除节点
	else if((*curNode)->Key()<key )return DeleteNodeInner(&((*curNode))->rchild,key);
	else  return DeleteNodeInner(&((*curNode)->lchild),key);
}
/*
删除树节点的第二步操作 
*/
bool SortTree::DeleteNodeSecond(TreeNode **curNode)
{
	TreeNode *tempNode;
	TreeNode *tempNode2;
	if(!(*curNode)->rchild){//没有右子树，直接接上左子树即可
		tempNode = *curNode;*curNode=(*curNode)->lchild;delete tempNode;
	}else if(!(*curNode)->lchild){//没有左子树，直接接上右子树即可
		tempNode = *curNode;*curNode=(*curNode)->rchild;delete tempNode;
	}else{//既有左子树右有右子树，直接接上左子树。遍历左孩子的(右子树*)，接上右子树
		tempNode = *curNode;
		tempNode2 = (*curNode)->lchild;//遍历到左孩子
		while(tempNode2->rchild)tempNode2=tempNode2->rchild;//遍历到左孩子的(右子树*)
		tempNode2->rchild = tempNode->rchild;//接上右子树
		tempNode=tempNode->lchild;//直接接上左子树

		delete *curNode;
	}
	return true;
}
/*
添加一个树节点 
*/   
void SortTree::AddNode(TreeNode * newNode)
{
    TreeNode * lastNode=0;
    
    if(!SeachNodeByKey(newNode,&lastNode))//不存在相同健值的节点 
    {
       
        if(_root==0)
        {
            _root = newNode;
        }    
        else if(newNode->Key()>lastNode->Key())
        {
            
            lastNode->rchild = newNode;
        }
        else{
            
            lastNode->lchild = newNode;
        }        
    }else{
        cout<<"不能添加，该键值已经存在"<<endl;
        //delete newNode;
    }     
          
}       

int main(int argc, char *argv[])
{
  SortTree *sTree = new SortTree();
  TreeNode * node1 = new IntegerTreeNode(23,23); 
  TreeNode * node2 = new StringTreeNode(12,"树节点X");
  TreeNode * node3 = new IntegerTreeNode(3,234);
  TreeNode * node4 = new StringTreeNode(31,"树节点Y");
  TreeNode * node5 = new IntegerTreeNode(4,23);
  TreeNode * node6 = new StringTreeNode(5,"树节点Z");
  TreeNode * node7 = new IntegerTreeNode(7,234);
  TreeNode * node8 = new StringTreeNode(9,"树节点M");
  TreeNode * node9 = new IntegerTreeNode(23,23);
  node1->Display();
  node2->Display();
  sTree->AddNode(node1);
  sTree->AddNode(node2);
  sTree->AddNode(node3);
  sTree->AddNode(node4);
  sTree->AddNode(node5);
  sTree->AddNode(node6);
  sTree->AddNode(node7);
  sTree->AddNode(node8);
  sTree->AddNode(node9);

  sTree->Display();
  sTree->DeleteNode(3);
  sTree->Display();
  //cout<<()<<endl;
  system("PAUSE");	
  return 0;
}