中序线索化的算法.txt

中序线索化的算法 中序线索化的算法 中序线索化的算法

//中序线索化的算法：
//////////////////////////////////////////////////
//CreateMidThread()私有成员函数
//二叉树的中序线索化
//current是遍历的当前节点的指针，pre是前驱结点指针
//////////////////////////////////////////////////
template<class T>
void MidThreadBinTree<T>::CreateMidThread(
        ThreadNode<T>* current,ThreadNode<T>*& pre)
{
    //如果当前结点为空则返回
    if(current==NULL)
        return;
    //如果当前结点不空
    else
    {
        //中序线索化左子树
        CreateMidThread(current->leftChild,pre);

        //建立当前结点的前驱线索
        if(current->leftChild==NULL)          //如果当前结点的左指针域为空
        {
            current->leftChild=pre;           //在左子树的指针域里放前驱结点pre指针   
            current->ltag=1;                  //把标志置为1,表示存放的是前驱结点的指针
        };
        //建立当前结点的后继线索
        if(pre!=NULL && pre->rightChild==NULL)//如果前驱结点pre不空,且pre右指针域为空
        {
            pre->rightChild=current;          //把当前结点的指针赋值给前驱结点pre的右指针域
            pre->rtag=1;                      //把标志置为1,表示存放的是pre的后继结点的指针
        };
        pre=current;                          //前驱结点按找中序序列向后推进一格
        
        //中序线索化右子树
        CreateMidThread(current->rightChild,pre);
    };
};
/////////////////////////CreateMidThread()函数结束

//////////////////////////////////////////////////
//CreateMidThread()共有成员函数
//中序线索化一棵二叉树
//////////////////////////////////////////////////
template<class T>
void MidThreadBinTree<T>::CreateMidThread()
{
    ThreadNode<T>* pre=NULL;      //前驱结点的指针
    
    if(root!=NULL)
    {
        CreateMidThread(root,pre);//中序线索化
        pre->rightChild=NULL;     //最后处理中序最后一个结点  
        pre->rtag=1;              //把标志清置为1
    };
};
/////////////////////////CreateMidThread()函数结束

//////////////////////////////////////////////////
//Destroy()私有成员函数
//把线索二叉树对应的结点的内存空间释放
//////////////////////////////////////////////////
template<class T>
void MidThreadBinTree<T>::Destroy(ThreadNode<T>* subTree)
{
    if(subTree!=NULL)
    {
        //释放左右子树的内存空间
        if(subTree->leftChild!=NULL 
            && subTree->ltag==0)
            Destroy(subTree->leftChild);
        if(subTree->rightChild!=NULL 
            && subTree->rtag==0)
            Destroy(subTree->rightChild);
        //释放当前结点的内存空间
        delete subTree;
    };
};
/////////////////////////////////Destroy()函数结束

//////////////////////////////////////////////////
//Exist()私有成员函数
//判断指定内容的结点在以subTree为根的二叉树中是否存在
//////////////////////////////////////////////////
template<class T>
bool MidThreadBinTree<T>::Exist(
        T item,ThreadNode<T>* subTree)
{
    //如果根结点就含有item
    if(item==subTree->data)
        return true;
    else
    {
        //递归搜索左右子树,只要其中一个含有就返回true
        return Exist(item,subTree->leftChild)
            ||Exist(item,subTree->rightChild);
    }
};
///////////////////////////////////Exist()函数结束

#endif